Slumpgraf

En slumpgraf är inom matematik och sannolikhetsteori informellt uttryckt en "obestämd" graf, där hörnen är bestämda i förväg men där kanterna vä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ältet probabilistisk grafteori. De studeras både för sin egen skull, och därför att de har viktiga tillämpningar, både inom ren kombinatorik och inom exempelvis epidemiologi.

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 positivt mått på 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är I är en ändlig mängd ("indexmängden"), varje G_i är en enkel graf, och μ är en funktion från I till R₊, 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 grafen G_i.

I det enklaste fallet har alla G_i samma ändliga hörnmängd V, med n element för något n, medan olika G_i har olika kantmängder E_i. Varje möjlig kantmängd skall förekomma en gång, så antalet element i I må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 samma oberoende sannolikhet p, som ligger strikt mellan 0 och 1. Det betyder att om E_i innehåller m kanter, så sätter man

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

Exempel

Låt den fixa hörnmängden V vara {a,b,c,d} (så att alltså n = 4), och låt p = 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 ur V, 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 enligt multiplikationsprincipen totalt $2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2=2^{6}=64$ olika möjliga grafer, som vi kan kalla för G₁, G₂, ..., G₆₄. En av dem , säg G₄₆, har de fyra kanterna ab, bc, cd och ad, men har inte kanter mellan a och c eller mellan b och d. "Sannolikheten" för att just dessa kanter kommer med är 0,4⁴ = 0,0256, och eftersom sannolikheten för att en kant inte "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 samt binomialteoremet ger 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