Úplný graf
Z Wikipedie, otevřené encyklopedie
V teorii grafů se termínem úplný graf označuje takový neorientovaný graf, v němž jsou každé dva vrcholy spojené hranou. Označuje se Kn, kde n je počet jeho vrcholů
[editovat] Definice
Graf G = (V, E) je úplný, pokud 
. Z toho plyne, že úplný graf o n vrcholech má právě 
hran.
[editovat] Vlastnosti
- je to regulární graf stupně n - 1
- je to maximálně souvislý graf, protože jediný vrcholový řez, který z něj učiní nesouvislý graf, je celá množina vrcholů
- žádný rovinný graf nemůže obsahovat úplný graf o více než 4 vrcholech (tedy K5 a vyšší)
[editovat] Příklady
Úplné grafy na 1 až 8 vrcholech:
 K1 |
 K2 |
 K3 |
 K4 |
 K5 |
 K6 |
 K7 |
 K8 |
