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$