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

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

Տարբերակում են պատահական գրաֆների Էռդոշ-Ռենյի (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}$ կող պարունակող գրաֆները ունեն կողերի գոյության ${\displaystyle p^{M}(1-p)^{n \choose 2}-M}$ հավանականությունը։

Այս մոդելի ${\displaystyle 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-ի։

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Չափորոշչային վերահսկողություն Microsoft: 34814168