yaadruchchika graph

ganita saastramlo, yaadruchchika graph anedi graphlapy sambhaavyata pampineelanu soochinche saadhaarana padam. yaadruchchika graphlanu kevalam sambhaavyata pampinhee dwara ledhaa vaatini utpatti chese yaadruchchika prakriya dwara vivarinchavacchu. yaadruchchika graphla siddhaantam graph siddhaantam mariyu sambhaavyata siddhaantam madhya koodali vadda undhi. ganita drukpatham nundi, "vilakshanhamaina" graphla lakshanaala gurinchi prasnalaku samadhanam ivvadaaniki yaadruchchika graphlu upayoginchabadataayi. sanklishta netvarklanu roopondinchaalsina anni rangaalalo daani aacharanaatmaka anuvartanaalu kanipistaayi-aneka yaadruchchika graph namuunaalu eee vidhamgaa telisinavi, vividha praantaalalo edurkone vividha rakaala sanklishta netvarklanu pratibimbistaayi. ganitasastra sandarbhamlo, "yaadruchchika graph" anedi daadaapu pratyaekamgaa erdos-raenee yaadruchchika graph namuunaanu suuchistumdi. itara sandarbhaallo, edainaa graph namuunaanu "yaadruchchika graph" gaa suuchimchavachchu.
namuunaalu.
n" vivikta sheershaala samititoe praarambhinchi, yaadrucchikamgaa vaati madhya varusa anchulanu jodinchadam dwara yaadruchchika graph pondabadutundi. graph yokka nirdishta lakshanam yea dasalo talette avakaasam undho nirnayinchadam eee rangamlo adhyayanam yokka lakshyam. vividha yaadruchchika graph namuunaalu graphlapy vividha sambhaavyata pampineelanu utpatti chestaayi. atyanta saadhaaranamgaa adhyayanam cheyabadinadi edger gilbert pratipaadinchinadi, dheenini "g" ("n", "p") anie suuchistaaru, dheenilo saadhyamayye prati anchu sambhaavyata 0 <"p" <1 thoo swatantramgaa sambhavistundi. "m" anchulatho "edainaa oka nirdishta" yaadruchchika graphnu pondhe sambhaavyata sangnaamaana suutram _ 2 thoo suutram _ 1.
daggari sambandham unna namuunaa, erdos-raenee modal "g" ("n", "m") nuu suuchistumdi, idhi khachitamgaa "m" anchulatho unna anni graphlaku samaana sambhaavyatanu ketayistundi. 0 ≤ "m" ≤ "n" thoo, "g" ("n", "m") suutram _ 3 muulakaalanu kaligi untundi mariyu prati moolakam sambhaavyata suutram _ 4 thoo sambhavistundi. taruvaati namuunaanu yaadruchchika graph prakriya suutram _ 5 yokka oka nirdishta samayamlo ("m") snapshotga chudavachu, idhi "n" sheershaalato praarambhamayye yaadruchchika prakriya mariyu anchulu laevu, mariyu prati dasalo tappipoyina anchula samiti nundi ekareetigaa enchukunna oka kotta anchunu jodistundi.
badulugaa manam anantamaina sheershaala samititoe praarambhinchi, saadhyamayye prati anchunu sambhaavyata 0 <"p" <1 thoo swatantramgaa jaraganiste, appudu manaku anantamaina yaadruchchika graph anie piluvabade vastuvu "g" vastundi. p" anedi 0 ledhaa 1 ayinappudu chinna sandarbhaallo tappa, atuvanti "g" daadaapu khachitamgaa eee krindi lakshanaanni kaligi untundih
edainaa "n" + "m" muulakaala suutram _ 6 ichinatlayithe, "v" loe oka sheersham "c" untundi, idhi suutram _ 7 yokka pratidaaniki prakkane untundi mariyu suutram _ 8 kii prakkane undadu.
okavela sheersham ganinchadaginadi ayithe, isomorphism varaku, eee lakshanamtho oke graph matrame undani, avi radeo graph anie telindi. anduvalla edainaa lekkinchadagina anantamaina yaadruchchika graph daadaapu khachitamgaa radeo graph, eee kaaranamgaa konnisaarlu dheenini yaadruchchika graph anie pilustaaru. ayithe, lekkinchaleni graphlaku saaruupya phalitam nijam kaadu, veetilo paina perkonna lakshanaanni santruptipariche aneka (nanisomarphic) graphlu unnaayi.
gilbert yokka yaadruchchika graph namuunaanu saadhaaraneekarinche maroka namuunaa yaadruchchika chukka-utpatti namuunaa. yaadruchchika chukka-utpatti graph prati sheershamto nijamaina vektarnu anubandhistundi. edainaa sheershaala "u" mariyu "v" madhya anchu "uv" yokka sambhaavyata anedi vaati sambandhita vahakalu yokka chukka utpatti u·v yokka kontha vidhi.
network sambhaavyata maatrika anchu sambhaavyata dwara yaadruchchika graphlanu roopondistundi, idhi icchina anchu suutram _ 10 nirdishta kaala vyavadhilo undani sambhaavyata suutram _ 9 nuu suuchistumdi. eee namuunaa nirdesinchabadina mariyu daari mallinchani, baruvunna mariyu baruvu laeni, mariyu sthiramaina ledhaa dynamic graphla nirmaanaaniki vistarinchadaginadi.
m" "pn" kosam, "n" anedi saadhyamaina anchula garishta sankhya, rendu vistrutamgaa upayoginche namuunaalu, "g" ("n", "m") mariyu "g" ("n", "p"), daadaapu parasparam maarchukogalavu.
yaadruchchika saadhaarana graphlu oka pratyeka kesunu yerparustaayi, saadhaaranamgaa yaadruchchika graphla nundi bhinnamgaa unde lakshanaalatoo.
okasari manaku yaadruchchika graphla namuunaa unte, graphlapy prati function yaadruchchika chararaasigaa maarutundi. eee namuunaa yokka adhyayanam anedi oka aasti sambhavinchagaladaa ledhaa kaneesam sambhaavyatanu anchanaa veyadam.
paribhasha.
yaadruchchika graphla sandarbhamlo 'daadaapu prati' anae padam khaaliilu mariyu sambhaavyatala kramaanni suuchistumdi, antey "dosha sambhaavyatalu" sunnaki untaayi.
aastulu.
yaadruchchika graphla siddhaantam yaadruchchika graphla yokka vilakshana lakshanaalanu adhyayanam chestundi, avi oka nirdishta pampinhee nundi geesina graphlaku adhika sambhaavyatanu kaligi untaayi. udaaharanaku, suutram _ 11 mariyu suutram _ 12 yokka icchina viluvanu adagavacchu, suutram _ 13 anusandhaaninchabadina sambhaavyata emiti. atuvanti prasnalanu adhyayanam cheyadamlo, parisoedhakulu tarachugaa yaadruchchika graphla yokka lakshanarahita pravartanapai drushti pedataaru-formula _ 11 chaalaa peddadigaa perige vividha sambhaavyatalu kalusukunna viluvalu. percolation siddhaantam yaadruchchika graphla anusandhananni, mukhyamgaa anantamaina pedda vaati anusandhananni vargeekaristundi.
percolation anedi graph yokka drudatvaaniki sambandhinchinadi (dheenini network anie kooda pilustaaru). suutram _ 11 nodes yokka yaadruchchika graph mariyu sagatu degree suutram _ 16 icchina taruvaata, manamu yaadrucchikamgaa nodes yokka binna suutram _ 17 nuu teesivesi, binna suutram _ 12 matrame vadilivestaamu. oka klishtamaina percolation threashold suutram _ 19 undhi, dheeni krinda network vichchinnamavutundi, ayithe suutram _ 20 paina oka pedda anusandhaaninchabadina bhaagam undhi.
sthaanikeekarinchina percolation anedi oka node daani poruguvaaru, tadupari sameepa poruguvaaru modalaina vaarini tolaginchadaanni suuchistumdi. network nundi node yokka suutram _ 17 yokka kontha bhaagam tolaginchabade varaku. degreela formula _ 19 yokka poison pampinheetho yaadruchchika graph kosam yaadruchchika tolagimpu kosam sarigga choopabadindi.
yaadruchchika graphlu sambhaavyata paddhatiloo vistrutamgaa upayoginchabadataayi, ikkada konni lakshanaalatoo graphla unikini niroopinchadaaniki prayatnistaaru. yaadruchchika graphlo oka aasti uniki tarachugaa, sjemereddy regularity lemma dwara, daadaapu anni graphlalo aaa aasti unikini suuchistumdi.
yaadruchchika saadhaarana graphlalo, suutram _ 23 anedi suutram _ 25 thoo suutram _ 24-kramabaddhamaina graphla samiti, antey suutram _ 11 mariyu suutram _ 27 anevi sahaja sankhyalu, suutram _ 28, mariyu suutram _ 29 samamga untaayi.
suutram _ 31 looni graph suutram _ 30 yokka degree kramam setlaloni anchula sankhyapai matrame aadharapadi untundi.
yaadruchchika graphlo anchulu, suutram _ 33, suutram _ 34 daadaapu prati suutram _ 34 kaneesam 1 degreeni kaligi undela chusukovadaniki taginanta peddadi ayithe, appudu daadaapu prati suutram _ 34 anusandhaaninchabadi untundi mariyu suutram _ 11 sarri ayithe, daadaapu prati suutram _ 34 khachitamaina saripolikanu kaligi untundi. mukhyamgaa, daadaapu prati yaadruchchika graphlo chivari vivikta sheersham adrusyamaina kshanam, graph anusandhaaninchabadutundi.
daadaapu prati graph prakriya, anchu kaneesa degreeni sambhaavyata penchadam ledhaa suutram _ 39 anchula kante konchem ekkuva unna yaadruchchika graph mariyu sambhaavyata sambhaavyata daggaragaa undatam, graph puurti saripolikanu kaligi undela chestundi, garishtamgaa oka sheersham minaha.
konni sthiramaina suutram _ 40 kosam, suutram _ 11 sheershaalu mariyu kaneesam suutram _ 42 anchulatho daadaapu prati label cheyabadina graph hamiltonian. sambhaavyata sambhaavyata moggu chuupadamtoe, kaneesa degreeni degreeni penche nirdishta anchu graph hamiltonianga chestundi.
yaadruchchika graph yokka lakshanaalu graph parivartanala krinda maaravacchu ledhaa asthiramgaa undavacchu. mashagi eah. modalainavi.udaaharanaku, yaadruchchika graphlanu vaati anchu-dwandwa graphlu (ledhaa line graphlu) gaa marche parivartana daadaapu oke degree pampinheetho graphla samishtini utpatti chestundani, conny degree sahasambandhaalu mariyu gananeeyamgaa adhika clustering gunakam kaligi untundani niroopinchabadindi.
rangu.
v" ("g") = {1, anae sheershamto "n" kramamlo yaadruchchika graph "g" ivvabadindi..., n"}, rangula sankhyapai atyaasagala algorithm dwara, sheershaalanu 1,2, rangulatho rangu veyavachu... (sheersham 1 rangu 1, sheersham 2 sheersham 1 prakkane lekapothe 1 rangu, lekapothe adhi 2 rangu modalainavi.).
chromatic bahupadi anie piluvabade aneka "q" rangulanu icchina yaadruchchika graphla yokka saraina rangula sankhya ippativaraku teliyadu. n" paaraamitulatoe yaadruchchika graphla chromatic bahupadi yokka sunnaala scaling mariyu anchula sankhya "m" ledhaa connection sambhaavyata "p" symbolic namuunaa saripolika aadhaaramgaa oka algorithamnu upayoginchi anubhaavikamgaa adhyayanam cheyabadindi.
yaadruchchika chetlu.
yaadruchchika chettu anedi yaadruchchika prakriya dwara erpadina chettu ledhaa vrukshasambandhamaina chettu. n" mariyu parimaanam "m" ("n") yokka yaadruchchika graphla yokka pedda shrenilo "k" kramamlo chettu bhagala sankhya pampinhee asymptoticalga poison. yaadruchchika chetla rakaalalo ekareeti vistarinchina chettu, yaadruchchika kaneesa vistarinchina chettu, yaadruchchika binary chettu, trep, yaadruchchika chettunu vaegamgaa anveshinchadam, brounian chettu mariyu yaadruchchika adavi unnaayi.
sharatulatho kuudina yaadruchchika graphlu.
sambhaavyata space formula _ 43 paie nirvachinchina icchina yaadruchchika graph modalnu pariganinchandi mariyu formula _ 44 anedi prati graphku "m" lakshanaala vector suutram _ 45 loe ketayinche nijamaina viluva gala functionga undanivvandi. 
sthira suutram _ 46 kosam, "sharatulatho kuudina yaadruchchika graphlu" anevi namuunaalu, dheenilo sambhaavyata kolata suutram _ 47 anni graphlaku sunna sambhaavyatanu ketayistundi, antey 'suutram _ 48.
pratyeka sandarbhaalu "sharatulatho ekareeti yaadruchchika graphlu", ikkada suutram _ 47 nirdishta lakshanaalanu kaligi unna anni graphlaku samaana sambhaavyatanu ketayistundi. conditioning samacharam anchula sankhya "m" kanavasaram lenappudu, conny itara ekapaksha graph property formula _ 50 ayinappudu, vaatini erdos-renee modal "g" ("n", "m") yokka saadhaaraneekaranagaa chudavachu. eee sandarbhamlo chaalaa takkuva vislaeshanhaatmaka phalitaalu andubaatulo unnaayi mariyu sagatu lakshanaala anubhavika pampineelanu pondadaaniki anukarana avasaram. 
charitra.
yaadruchchika graph namuunaanu mottamodata mottamodata helen haall gennings mariyu jacob moreno upayoginchaaru, ikkada vaari network detaloni paraspara linkula bhaganni yaadruchchika namuunaatoe polchadam adhyayanam cheyadamlo "avakaasam saamaajika shaastram" (oka nirdesita erdos-raenee namuunaa) pariganinchabadindi. pariganinchabadindi rae solomonaf mariyu anatol rapoport dwara "yaadruchchika vala" anae paerutoe maroka upayogam, sthiramaina avt-degree mariyu itara sheershaalaku yaadrucchikamgaa enchukunna jodimpulato nirdesita graphla namuunaanu upayoginchadam jarigindi.
yaadruchchika graphla yokka erdos-renee namuunaanu modata paal erdos mariyu alfred renee vaari 1959 paperlo "yaadruchchika graphlapy" mariyu swatantramgaa gilbert thana paper "yaadruchchika graphlu" loe nirvachinchaaru.

