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

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

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

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

-ում գրեթե բոլոր գրաֆները կապակցված են։

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

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

Երկու մոդելների համեմատությունը 
-ում սպասվող կողերի քանակը հավասար է  և մեծ թվերի օրենքի համաձայն -ից ցանկացած գրաֆ գրեթե վստահորեն կունենա նշված քանակությամբ կողեր (կողերի քանակը անվերջության ձգտելու դեպքում)։ Հետևաբար, կոպիտ էվրիստիկան հետևյալն է՝ եթե , ապա -ը աճելիս -ն իրեն պետք է պահի ինչպես -ը  համար։

Գրաֆների բազում հատկությունների համար նշվածը կատարվում է։ Եթե -ն որևէ հատկություն է, որը մոնոտոն է ըստ ենթագրաֆների տեսակավորման (այն է՝ եթե -ն -ի ենթագրաֆ է և -ն բավարարում է -ին, ապա -ն նույնպես բավարարում է -ին), ապա հետևյալ երկու պնդումները՝
 -ն տեղի ունի -ի գրեթե բոլոր գրաֆների համար, և
 -ն տեղի ունի -ի գրեթե բոլոր գրաֆների համար
համարժեք են  դեպքում։ Օրինակ, նկարագրվածը տեղի ունի, եթե -ն կապակցված լինելու հատկությունն է կամ -ն Համիլտոնյան ցիկլ պարունակելու հատկությունն է։ Սակայն, պարտադիր չէ, որ այս ամենը տեղի ունենա եթե հատկությունը մոնոտոն չէ (օրինակ՝ զույգ քանակով կողեր պարունակելու հատկությունը)։

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

-ի հատկությունները 
-ն միջինում ունի  կող։

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

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

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

1960 թվականի իրենց հոդվածում Էռդոշը և Ռենյին շատ ճշգրիտ կերպով նկարագրել են -ի վարքը -ի տարբեր արժեքների դեպքում։ Ստորև այդ նկարագրությունները բերված են սեղմ տեսքով։
 Եթե , ապա -ի գրաֆը գրեթե անկասկած չի պարունակի -ից մեծ կապակպցված բաղադրիչներ։
 Եթե , ապա -ի գրաֆը գրեթե անկասկած կպարունակի խոշորագույն բաղադրիչ, որի չափը  կարգի է։
 Եթե , որտեղ -ն հաստատուն է, ապա -ի գրաֆը գրեթե անկասկած կպարունակի միակ հսկա բաղադրիչ, որում պարունակվող գագաթների քանակի հարաբերությունը բոլոր գագաթների քանակին հաստատուն է։ Բոլոր այլ բաղադրիչները պարունակելու են ոչ ավել, քան  գագաթ։
 Եթե , ապա -ի գրաֆը գրեթե անկասկած կպարունակի իզոլացված գագաթներ և՝ որպես հետևանք, գրաֆը կլինի ոչ կապակցված։
 Եթե , ապա -ի գրաֆը գրեթե անկասկած կլինի կապակցված։
Այսպիսով, -ը -ի կապակցվածության ճշգրիտ շեմն է։

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

Հղումներ 

Պատահական գրաֆներ