Komplet graf

Komplet graf
K 7 , komplet graf med 7 toppunkter
Toppe	n
ribben	${\frac {n(n-1)}{2}}$
Diameter	en
Automorfismer	n ! ( S n )
Kromatisk tal	n
Kromatisk indeks	n hvis n er ulige,ellers n − 1
Betegnelse	K n
Mediefiler på Wikimedia Commons

En komplet graf er en simpel urettet graf , hvor hvert par af distinkte hjørner er tilstødende. En komplet graf med hjørner har kanter og er angivet med . Er en regulær gradgraf . $n$ $n(n-1)/2$ $K_n$ $n-1$

En komplet graf dannes ud fra hjørnerne og kanterne af (n-1) -simplex .

En komplet rettet graf er en rettet graf , hvor hvert par af distinkte hjørner er forbundet med et par buer (med forskellige retninger).

Egenskaber

Graferne fra til er plane . Komplette grafer med et stort antal hjørner er ikke plane, da de indeholder en undergraf og derfor ikke opfylder Pontryagin-Kuratovsky-kriteriet . $K_1$ $K_{4}$ $K_{5}$

Eksempler

Nedenfor er komplette grafer med antallet af hjørner fra 1 til 12 og antallet af deres kanter.

K1 : 0	K2 : 1	K3 : 3	K4 : 6

K5 : 10	K6 : 15	K7 : 21	K8 : 28

K9 : 36	K10 : 45	K11 : 55	K12 : 66