Ú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ť .

Grafy rovinné grafy. Ostatné úplné grafy nie sú rovinné.

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

Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg
Complete graph K5.svg Complete graph K6.svg Complete graph K7.svg Complete graph K8.svg

VlastnostiUpraviť

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

Iné projektyUpraviť

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