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

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

## Սահմանումը
Տարբերակում են պատահական գրաֆների Էռդոշ-Ռենյի (ER) մոդելի երկու սերտորեն կապված տարբերակ՝
* G(n, M) մոդելի դեպքում գրաֆը ընտրվում է պատահականորեն՝ հավասարաչափ n հանգույց և M կող ունեցող բոլոր գրաֆների բազմությունից։ Օրինակ՝ G(3, 2) մոդելում երեք գագաթ և երկու կող ունեցող բոլոր հնարավոր երեք գրաֆները ընդգրկված են 1/3 հավանականությամբ։
* G(n, p) մոդելում գրաֆը կառուցվում է հանգույցների միջև պատահականորեն կապեր ստեղծելով։ Յուրաքանչյուր կող ընդգրկվում է գրաֆում p հավանականությամբ՝ անկախ մնացած կողերից։ Համարժեքորեն՝ բոլոր n հանգույց և M կող պարունակող գրաֆները ունեն կողերի գոյության p^M (1-p)^ n-գագաթանի գրաֆները ընտրվում են հավասար հավանականությամբ։

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

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

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

n-ի՝ անվերջության ձգտելուն համընթաց, n գագաթանի և կողերի 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-ին), ապա հետևյալ երկու պնդումները՝
# P-ն տեղի ունի G(n,p)-ի գրեթե բոլոր գրաֆների համար, և
# P-ն տեղի ունի G(n,\binom{n}{2}p)-ի գրեթե բոլոր գրաֆների համար
համարժեք են pn^2 \to \infty դեպքում։ Օրինակ, նկարագրվածը տեղի ունի, եթե P-ն կապակցված լինելու հատկությունն է կամ P-ն Համիլտոնյան ցիկլ պարունակելու հատկությունն է։ Սակայն, պարտադիր չէ, որ այս ամենը տեղի ունենա եթե հատկությունը մոնոտոն չէ (օրինակ՝ զույգ քանակով կողեր պարունակելու հատկությունը)։

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

## <math>G(n,p)</math>-ի հատկությունները
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, ապա 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, ապա 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-ին։

## Հղումներ

Կատեգորիա:Պատահական գրաֆներ