Komplett graf

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 $K_{n}$ .

Egenskaper

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} = (\binom{n}{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

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$

$K_{5} : 10$	$K_{6} : 15$	$K_{7} : 21$	$K_{8} : 28$

Komplett graf

Egenskaper

Exempel

Navigeringsmeny

Sök