Էռդոշ-Ռենյի մոդել

Գրաֆների տեսությունում` Էռդոշ-Ռենյի մոդել հասկացողությունը օգտագործվում է պատահական գրաֆների գեներացման երկու սերտորեն կապված մոդելներից որևէ մեկը մատնանշելու համար։ Նրանք անվանվել են ի պատիվ Պոլ Էռդոշի և Ալֆրեդ Ռենյիի, ովքեր առաջիններն են ներկայացրել այս մոդելներից մեկը 1959-ին; մյուս մոդելը ներդրվել է նրանցից անկախ և միաժամանակ Էդգար Գիլբերտի կողմից։ Էռդոշի և Ռենյիի ներկայացրած մոդելում նույն գագաթների բազմության վրա կառուցված և հավասար քանակությամբ կողեր ունեցող բոլոր գրաֆները հավասար հավանական են; Գիլբերտի ներկայացված մոդելում յուրաքանչյուր կող ունի ֆիքսված հավանականություն առկա լինելու կամ չլինելու՝ անկախ այլ կողերից։ Այս մոդելները կարող են օգտագործվել որպես որոշակի հատկությունների բավարարող գրաֆների գոյության ապացույցի հավանականային միջոց, և կամ ապահովել խիստ սահմանում՝ թե ինչ է նշանակում հատկությունը բավարարվում է գրեթե բոլոր գրաֆների համար։

Սահմանումը

Տարբերակում են պատահական գրաֆների Էռդոշ-Ռենյի (ER) մոդելի երկու սերտորեն կապված տարբերակ՝

• ${\textstyle G(n,M)}$ մոդելի դեպքում գրաֆը ընտրվում է պատահականորեն՝ հավասարաչափ ${\textstyle n}$ հանգույց և ${\textstyle M}$ կող ունեցող բոլոր գրաֆների բազմությունից։ Օրինակ՝ ${\textstyle G(3,2)}$ մոդելում երեք գագաթ և երկու կող ունեցող բոլոր հնարավոր երեք գրաֆները ընդգրկված են 1/3 հավանականությամբ։
• ${\textstyle G(n,p)}$ մոդելում գրաֆը կառուցվում է հանգույցների միջև պատահականորեն կապեր ստեղծելով։ Յուրաքանչյուր կող ընդգրկվում է գրաֆում ${\textstyle p}$ հավանականությամբ՝ անկախ մնացած կողերից։ Համարժեքորեն՝ բոլոր ${\textstyle n}$ հանգույց և ${\textstyle M}$ կող պարունակող գրաֆները ունեն կողերի գոյության $p^{M}(1-p)^{{n \choose 2}-M}$ հավանականությունը։

Այս մոդելի $p$ պարամետրը կարելի է ընդունել որպես կշռային ֆունկցիա՝ ${\textstyle p}$-ի 0-ից 1 աճին համընթաց ավելի հավանական է դառնում, որ մոդելը կներառի շատ կող պարունակող գրաֆները և ավելի քիչ հավանական է դառնում, որ այն կներառի քիչ կող պարունակողներին։ Մասնավորապես, ${\textstyle p=0.5}$ դեպքը համապատասխանում է այն իրավիճակին, երբ բոլոր ${\textstyle 2^{\binom {n}{2}}}$ ${\textstyle n}$-գագաթանի գրաֆները ընտրվում են հավասար հավանականությամբ։

Պատահական գրաֆների վարքը հաճախ ուսումնասիրում են այն դեպքում, երբ գագաթների թիվը՝ ${\textstyle n}$-ը, ձգտում է անվերջության։ Չնայած ${\textstyle p}$-ն և ${\textstyle M}$-ը կարող են ֆիքսված լինել այս դեպքում՝ նրանք կարող են նաև ${\textstyle n}$-ից կախված ֆունկցիաներ լինել։ Օրինակ հետևյալ պնդումը՝

${\textstyle G(n,2ln(n)/n)}$-ում գրեթե բոլոր գրաֆները կապակցված են։

նշանակում է հետևյալը՝

${\textstyle n}$-ի՝ անվերջության ձգտելուն համընթաց, ${\textstyle n}$ գագաթանի և կողերի ${\textstyle 2ln(n)/n}$ հավանականություն ունեցող գրաֆի կապակցված լինելու հավանականությունը ձգտում է 1-ի։

Երկու մոդելների համեմատությունը

$G(n,p)$-ում սպասվող կողերի քանակը հավասար է ${\binom {n}{2}}p$ և մեծ թվերի օրենքի համաձայն $G(n,p)$-ից ցանկացած գրաֆ գրեթե վստահորեն կունենա նշված քանակությամբ կողեր (կողերի քանակը անվերջության ձգտելու դեպքում)։ Հետևաբար, կոպիտ էվրիստիկան հետևյալն է՝ եթե $pn^{2}\to \infty$, ապա $n$-ը աճելիս $G(n,p)$-ն իրեն պետք է պահի ինչպես $G(n,M)$-ը $M={\binom {n}{2}}p$ համար։

Գրաֆների բազում հատկությունների համար նշվածը կատարվում է։ Եթե $P$-ն որևէ հատկություն է, որը մոնոտոն է ըստ ենթագրաֆների տեսակավորման (այն է՝ եթե $A$-ն $B$-ի ենթագրաֆ է և $A$-ն բավարարում է $P$-ին, ապա $B$-ն նույնպես բավարարում է $P$-ին), ապա հետևյալ երկու պնդումները՝

1. $P$-ն տեղի ունի $G(n,p)$-ի գրեթե բոլոր գրաֆների համար, և
2. $P$-ն տեղի ունի $G(n,{\binom {n}{2}}p)$-ի գրեթե բոլոր գրաֆների համար

համարժեք են $pn^{2}\to \infty$ դեպքում։ Օրինակ, նկարագրվածը տեղի ունի, եթե $P$-ն կապակցված լինելու հատկությունն է կամ $P$-ն Համիլտոնյան ցիկլ պարունակելու հատկությունն է։ Սակայն, պարտադիր չէ, որ այս ամենը տեղի ունենա եթե հատկությունը մոնոտոն չէ (օրինակ՝ զույգ քանակով կողեր պարունակելու հատկությունը)։

Գործնականում ավելի հաճախ օգտագործվում է $G(n,p)$ մոդելը՝ ի շնորհիվ, մասնավորապես, կողերի անկախությամբ պայմանավորված հետազոտությունների պարզության։

$G(n,p)$-ի հատկությունները

$G(n,p)$-ն միջինում ունի ${\binom {n}{2}}p$ կող։

Ցանկացած գագաթի աստիճանի բաշխումը բինոմիալ է՝

$P(\operatorname {deg} (v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},$

որտեղ $n$-ը գրաֆում գագաթների քանակն է։ Քանի որ

$P(\operatorname {deg} (v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!}}\quad {\mbox{ երբ }}n\to \infty {\mbox{ և }}np=\mathrm {const} ,$

ապա նշվածը Պուասոնի բաշխում է մեծ $n$-երի և $np=const$դեպքում։

1960 թվականի իրենց հոդվածում Էռդոշը և Ռենյին շատ ճշգրիտ կերպով նկարագրել են $G(n,p)$-ի վարքը $p$-ի տարբեր արժեքների դեպքում։ Ստորև այդ նկարագրությունները բերված են սեղմ տեսքով։

• Եթե $np<1$, ապա $G(n,p)$-ի գրաֆը գրեթե անկասկած չի պարունակի $O(log(n))$-ից մեծ կապակպցված բաղադրիչներ։
• Եթե $np=1$, ապա $G(n,p)$-ի գրաֆը գրեթե անկասկած կպարունակի խոշորագույն բաղադրիչ, որի չափը $n^{2/3}$ կարգի է։
• Եթե $np\to c>1$, որտեղ $c$-ն հաստատուն է, ապա $G(n,p)$-ի գրաֆը գրեթե անկասկած կպարունակի միակ հսկա բաղադրիչ, որում պարունակվող գագաթների քանակի հարաբերությունը բոլոր գագաթների քանակին հաստատուն է։ Բոլոր այլ բաղադրիչները պարունակելու են ոչ ավել, քան $O(log(n))$ գագաթ։
• Եթե $p<{\tfrac {(1-\epsilon )\ln n}{n}}$, ապա $G(n,p)$-ի գրաֆը գրեթե անկասկած կպարունակի իզոլացված գագաթներ և՝ որպես հետևանք, գրաֆը կլինի ոչ կապակցված։
• Եթե $p>{\tfrac {(1+\epsilon )\ln n}{n}}$, ապա $G(n,p)$-ի գրաֆը գրեթե անկասկած կլինի կապակցված։

Այսպիսով, ${\tfrac {\ln n}{n}}$-ը $G(n,p)$-ի կապակցվածության ճշգրիտ շեմն է։

Պատմություն

$G(n,p)$ մոդելը առաջին անգամ առաջարկել է Էդգար Գիլբերտը իր 1959 թվականի կապակցվածության շեմին նվիրված հոդվածում։ $G(n,M)$ մոդելը առաջարկվել է Էռդոշի և Ռենյիի կողմից իրենց 1959 թվականի հոդվածում։ Ինչպես և Գիլբերտի դեպքում, նրանց առաջին հետազոտությունները նվիրված էին $G(n,M)$-ի կապակցվածությանը, իսկ ավելի մանրամասն վերլուծությունը հետևեց 1960-ին։