Komplett graf

Från Wikipedia
Hoppa till: navigering, sök

En komplett graf är i det matematiska området grafteori en enkel graf där varje par av distinkta noder har en båge mellan sig. En komplett graf med  n noder betecknas ofta  K_n .

Egenskaper[redigera | redigera wikitext]

Alla noder i en komplett graf har samma grad, n-1.

Grafen  K_n kan ses som en representation av en  n-1-simplex och är övre gräns för antal kopplingar i ett nätverk med  n noder. Så att  K_3 representerar en triangel, K_4 en tetraeder, osv.

Antalet bågar  B_n i grafen  K_n fås genom det enkla sambandet:

B_n = {n \choose 2} = \frac{n(n-1)}{2}

 K_1 till  K_4 är planära grafer, men  K_5 är inte planär, enligt Kuratowskis sats.

Exempel[redigera | redigera wikitext]

Nedan finns en tabell med  K_1 till  K_8 och deras bågantal:

K_1: 0 K_2: 1 K_3: 3 K_4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg
K_5: 10 K_6: 15 K_7: 21 K_8: 28
Complete graph K5.svg Complete graph K6.svg Complete graph K7.svg Complete graph K8.svg