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

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


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

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

  
    
      
        G
        (
        n
        ,
        p
        )
      
    
    {\textstyle G(n,p)}
   մոդելում գրաֆը կառուցվում է հանգույցների միջև պատահականորեն կապեր ստեղծելով։ Յուրաքանչյուր կող ընդգրկվում է գրաֆում 
  
    
      
        p
      
    
    {\textstyle p}
   հավանականությամբ՝ անկախ մնացած կողերից։ Համարժեքորեն՝ բոլոր 
  
    
      
        n
      
    
    {\textstyle n}
   հանգույց և 
  
    
      
        M
      
    
    {\textstyle M}
   կող պարունակող գրաֆները ունեն կողերի գոյության 
  
    
      
        
          p
          
            M
          
        
        (
        1
        −
        p
        
          )
          
            
              
                
                  (
                
                
                  n
                  2
                
                
                  )
                
              
            
            −
            M
          
        
      
    
    {\displaystyle p^{M}(1-p)^{{n \choose 2}-M}}
   հավանականությունը։Այս մոդելի 
  
    
      
        p
      
    
    {\displaystyle p}
   պարամետրը կարելի է ընդունել որպես կշռային ֆունկցիա՝ 
  
    
      
        p
      
    
    {\textstyle p}
  -ի 0-ից 1 աճին համընթաց ավելի հավանական է դառնում, որ մոդելը կներառի շատ կող պարունակող գրաֆները և ավելի քիչ հավանական է դառնում, որ այն կներառի քիչ կող պարունակողներին։ Մասնավորապես, 
  
    
      
        p
        =
        0.5
      
    
    {\textstyle p=0.5}
   դեպքը համապատասխանում է այն իրավիճակին, երբ բոլոր 
  
    
      
        
          2
          
            
              
                (
              
              
                n
                2
              
              
                )
              
            
          
        
      
    
    {\textstyle 2^{\binom {n}{2}}}
   
  
    
      
        n
      
    
    {\textstyle n}
  -գագաթանի գրաֆները ընտրվում են հավասար հավանականությամբ։
Պատահական գրաֆների վարքը հաճախ ուսումնասիրում են այն դեպքում, երբ գագաթների թիվը՝ 
  
    
      
        n
      
    
    {\textstyle n}
  -ը, ձգտում է անվերջության։ Չնայած 
  
    
      
        p
      
    
    {\textstyle p}
  -ն և 
  
    
      
        M
      
    
    {\textstyle M}
  -ը կարող են ֆիքսված լինել այս դեպքում՝ նրանք կարող են նաև 
  
    
      
        n
      
    
    {\textstyle n}
  -ից կախված ֆունկցիաներ լինել։ Օրինակ հետևյալ պնդումը՝

  
    
      
        G
        (
        n
        ,
        2
        l
        n
        (
        n
        )
        
          /
        
        n
        )
      
    
    {\textstyle G(n,2ln(n)/n)}
  -ում գրեթե բոլոր գրաֆները կապակցված են։
նշանակում է հետևյալը՝

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


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

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

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

  
    
      
        P
      
    
    {\displaystyle P}
  -ն տեղի ունի 
  
    
      
        G
        (
        n
        ,
        
          
            
              (
            
            
              n
              2
            
            
              )
            
          
        
        p
        )
      
    
    {\displaystyle G(n,{\binom {n}{2}}p)}
  -ի գրեթե բոլոր գրաֆների համարհամարժեք են 
  
    
      
        p
        
          n
          
            2
          
        
        →
        ∞
      
    
    {\displaystyle pn^{2}\to \infty }
   դեպքում։ Օրինակ, նկարագրվածը տեղի ունի, եթե 
  
    
      
        P
      
    
    {\displaystyle P}
  -ն կապակցված լինելու հատկությունն է կամ 
  
    
      
        P
      
    
    {\displaystyle P}
  -ն Համիլտոնյան ցիկլ պարունակելու հատկությունն է։ Սակայն, պարտադիր չէ, որ այս ամենը տեղի ունենա եթե հատկությունը մոնոտոն չէ (օրինակ՝ զույգ քանակով կողեր պարունակելու հատկությունը)։
Գործնականում ավելի հաճախ օգտագործվում է 
  
    
      
        G
        (
        n
        ,
        p
        )
      
    
    {\displaystyle G(n,p)}
   մոդելը՝ ի շնորհիվ, մասնավորապես, կողերի անկախությամբ պայմանավորված հետազոտությունների պարզության։


==  ==
  
    
      
        G
        (
        n
        ,
        p
        )
      
    
    {\displaystyle G(n,p)}
  -ի հատկությունները

  
    
      
        G
        (
        n
        ,
        p
        )
      
    
    {\displaystyle G(n,p)}
  -ն միջինում ունի 
  
    
      
        
          
            
              (
            
            
              n
              2
            
            
              )
            
          
        
        p
      
    
    {\displaystyle {\binom {n}{2}}p}
   կող։
Ցանկացած գագաթի աստիճանի բաշխումը բինոմիալ է՝

  
    
      
        P
        (
        deg
        ⁡
        (
        v
        )
        =
        k
        )
        =
        
          
            
              (
            
            
              
                n
                −
                1
              
              k
            
            
              )
            
          
        
        
          p
          
            k
          
        
        (
        1
        −
        p
        
          )
          
            n
            −
            1
            −
            k
          
        
        ,
      
    
    {\displaystyle P(\operatorname {deg} (v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},}
  
որտեղ 
  
    
      
        n
      
    
    {\displaystyle n}
  -ը գրաֆում գագաթների քանակն է։ Քանի որ

  
    
      
        P
        (
        deg
        ⁡
        (
        v
        )
        =
        k
        )
        →
        
          
            
              (
              n
              p
              
                )
                
                  k
                
              
              
                
                  e
                
                
                  −
                  n
                  p
                
              
            
            
              k
              !
            
          
        
        
        
          
             երբ 
          
        
        n
        →
        ∞
        
          
             և 
          
        
        n
        p
        =
        
          c
          o
          n
          s
          t
        
        ,
      
    
    {\displaystyle P(\operatorname {deg} (v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!}}\quad {\mbox{ երբ }}n\to \infty {\mbox{ և }}np=\mathrm {const} ,}
  
ապա նշվածը Պուասոնի բաշխում է մեծ 
  
    
      
        n
      
    
    {\displaystyle n}
  -երի և 
  
    
      
        n
        p
        =
        c
        o
        n
        s
        t
      
    
    {\displaystyle np=const}
  դեպքում։
1960 թվականի իրենց հոդվածում Էռդոշը և Ռենյին շատ ճշգրիտ կերպով նկարագրել են 
  
    
      
        G
        (
        n
        ,
        p
        )
      
    
    {\displaystyle G(n,p)}
  -ի վարքը 
  
    
      
        p
      
    
    {\displaystyle p}
  -ի տարբեր արժեքների դեպքում։ Ստորև այդ նկարագրությունները բերված են սեղմ տեսքով։

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


== Պատմություն ==

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


== Հղումներ ==