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 ${\displaystyle n}$ noder betecknas ${\displaystyle K_{n}}$.

Egenskaper

Alla noder i en komplett graf har samma grad, ${\displaystyle n-1}$.

Grafen ${\displaystyle K_{n}}$ kan ses som en representation av en ${\displaystyle n-1}$-simplex och är övre gräns för antal kopplingar i ett nätverk med ${\displaystyle n}$ noder. Så att ${\displaystyle K_{3}}$ representerar en triangel, ${\displaystyle K_{4}}$ en tetraeder, osv.

Antalet bågar ${\displaystyle B_{n}}$ i grafen ${\displaystyle K_{n}}$ fås genom det enkla sambandet:

${\displaystyle B_{n}={n \choose 2}={\frac {n(n-1)}{2}}}$

${\displaystyle K_{1}}$ till ${\displaystyle K_{4}}$ är planära grafer, men ${\displaystyle K_{5}}$ är inte planär, enligt Kuratowskis sats.

Exempel

Nedan finns en tabell med ${\displaystyle K_{1}}$ till ${\displaystyle K_{8}}$ och deras bågantal:

${\displaystyle K_{1}:0}$	${\displaystyle K_{2}:1}$	${\displaystyle K_{3}:3}$	${\displaystyle K_{4}:6}$
${\displaystyle K_{5}:10}$	${\displaystyle K_{6}:15}$	${\displaystyle K_{7}:21}$	${\displaystyle K_{8}:28}$