Kompletní graf

Kompletní graf
K 7 , kompletní graf se 7 vrcholy
Vrcholy	n
žebra	${\frac {n(n-1)}{2}}$
Průměr	jeden
Automorfismy	n ! ( S n )
Chromatické číslo	n
Chromatický index	n je -li n liché,jinak n − 1
Označení	K n
Mediální soubory na Wikimedia Commons

Úplný graf je jednoduchý neorientovaný graf , ve kterém každá dvojice odlišných vrcholů sousedí. Úplný graf s vrcholy má hrany a značí se . Je to běžný graf stupňů . $n$ $n(n-1)/2$ $K_n$ $n-1$

Z vrcholů a hran (n-1) -simplexu se vytvoří úplný graf .

Kompletní orientovaný graf je orientovaný graf , ve kterém je každá dvojice odlišných vrcholů spojena dvojicí oblouků (s různými směry).

Vlastnosti

Grafy od do jsou rovinné . Úplné grafy s velkým počtem vrcholů nejsou rovinné, protože obsahují podgraf , a proto nesplňují Pontrjaginovo-Kuratovského kritérium . $K_1$ $K_{4}$ $K_{5}$

Příklady

Níže jsou kompletní grafy s počtem vrcholů od 1 do 12 a počtem jejich hran.

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

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

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