Úplný graf

Úplný graf alebo kompletný graf je graf, v ktorom je každý vrchol grafu spojený s každým iným vrcholom grafu. Úplný graf s n vrcholmi sa zvykne označovať $K_{n}\$.

Grafy $K_{1}\$ až $K_{4}\$ sú rovinné grafy. Ostatné úplné grafy nie sú rovinné.

Úplné grafy pre 1 až 8 vrcholov, číslo za dvojbodkou je počet hrán.

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

Vlastnosti

• Počet hrán úplného grafu $K_{n}\$ je $n(n-1)/2\$.
• Každý úplný graf je silno regulárny graf.
• Chromatické číslo úplného grafu $K_{n}\$ je $n\$.
• Úplný graf $K_{n}\$ je $(n-1)$-regulárny.
• Úplný graf $K_{n}\$ má $n!\$ automorfizmov.
• Úplný graf $K_{n}\$ má práve $n^{n-2}$ rôznych kostier (tzv. Cayleyho vzorec).

Iné projekty

Commons

• Commons ponúka multimediálne súbory na tému Úplný graf