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 ofta $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 = {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

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$