Slumpgraf

Enslumpgrafär inommatematikochsannolikhetsteoriinformellt uttryckt en "obestämd"graf,därhörnenär bestämda i förväg men därkanternaväljs slumpmässigt. Detta gör att grafen kan sägas ha vissa egenskaper, som att vara sammanhängande, med en viss "sannolikhet".Slumpgrafer studeras inom det förhållandevis moderna forskningsfältetprobabilistisk grafteori.De studeras både för sin egen skull, och därför att de har viktiga tillämpningar, både inom renkombinatorikoch inom exempelvisepidemiologi.

Formella definitioner

Rent formellt kan det vara bättre att uppfatta "en" slumpgraf inte som en enda obestämd graf utan som antingen en hel (oftast ändlig) familj grafer tillsammans med ett positivtmåttpå familjen, med totalmåttet 1, eller som ett val av ett element i familjen, valt med den sannolikhet som ges av det tilldelade måttet.

Med andra ord kan en slumpgraf definieras som ett par${\bigl (}(G_{i})_{i\in I},\mu {\bigr )}$,därIär en ändlig mängd ( "indexmängden" ), varjeG_iär enenkel graf,och μ är enfunktionfrånItillR₊,mängden av positiva reella par, med den extra egenskapen att

$\sum _{i\in I}\mu (i)=1\;.\,$

Man tolkar här μ(i) som sannolikheten för att välja grafenG_i.

I det enklaste fallet har allaG_isamma ändligahörnmängdV,mednelement för någotn,medan olikaG_ihar olikakantmängderE_i.Varje möjlig kantmängd skall förekomma en gång, så antalet element iImåste vara$2^{n \choose 2}$.Man tänker sig att varje tänkbar kant (det vill säga varje tvådelmängd av hörn) förekommer med sammaoberoendesannolikhetp,som ligger strikt mellan 0 och 1. Det betyder att omE_iinnehållermkanter, så sätter man

$\mu (i)=p^{m}\cdot (1-p)^{{n \choose 2}-m}\;.\,$

Exempel

Låt den fixa hörnmängdenVvara {a,b,c,d} (så att alltsån= 4), och låtp= 0,4. Det betyder att "chansen" för att det finns en kant mellan två olika slumpvis valda hörn är 40%. Det finns totalt${4 \choose 2}=6$oordnade urval av två hörn urV,och för varje sådant val kan det finnas eller inte finnas en kant mellan de två hörnen. Därför finns det enligtmultiplikationsprincipentotalt$2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2=2^{6}=64$olika möjliga grafer, som vi kan kalla förG₁,G₂,...,G₆₄.En av dem, sägG₄₆,har de fyra kanternaab,bc,cdochad,men har inte kanter mellanaochceller mellanbochd."Sannolikheten" för att just dessa kanter kommer med är 0,4⁴= 0,0256, och eftersom sannolikheten för att en kantinte"råkar finnas" är 1-0,4 = 0,6, är sannolikheten för de två icke-kanterna 0,6²= 0,36. Alltså sätter man

$\mu (46)=0{,}0256\cdot 0{,}36=0{,}009216\;.\,$

Av dessa 64 grafer saknar 1 kanter, har 6 en kant var, 15 två kanter var, 20 tre kanter var 15 fyra kanter var, 6 fem kanter var, och slutligen 1 samtliga möjliga sex kanter. Detta samtbinomialteoremetger att mycket riktigt

$\sum _{i=1}^{64}\mu (i)=1\cdot 0{,}6^{6}+6\cdot 0{,}4^{1}\cdot 0{,}6^{5}+15\cdot 0{,}4^{2}\cdot 0{,}6^{4}+20\cdot 0{,}4^{3}\cdot 0{,}6^{3}+15\cdot 0{,}4^{4}\cdot 0{,}6^{2}+6\cdot 0{,}4^{5}\cdot 0{,}6^{1}+1\cdot 0{,}4^{6}=(0{,}4+0{,}6)^{6}=1^{6}=1\;.\,$

Se även

• Probabilistisk grafteori