Ú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