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

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

Սահմանումը

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$P(\mathrm{deg}(v)=k)=(\genfrac{}{}{0ex}{}{n-1}{k})p^k(1-p{)}^{n-1-k},$

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

$P(\mathrm{deg}(v)=k)\to \frac{(np{)}^k{\mathrm{e}}^{-np}}{k!}\text{ երբ }n\to \mathrm{\infty }\text{ և }np=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t},$

ապա նշվածը Պուասոնի բաշխում է մեծ $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<\frac{(1-ϵ)\ln n}{n}$, ապա $G(n,p)$-ի գրաֆը գրեթե անկասկած կպարունակի իզոլացված գագաթներ և՝ որպես հետևանք, գրաֆը կլինի ոչ կապակցված։
• Եթե $p>\frac{(1+ϵ)\ln n}{n}$, ապա $G(n,p)$-ի գրաֆը գրեթե անկասկած կլինի կապակցված։

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

Պատմություն

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