V teorii grafů se termínem úplný graf označuje takový neorientovaný graf, v němž jsou každé dva různé vrcholy spojené hranou. Označuje se , kde je počet jeho vrcholů.
Definice Graf G = (V, E) je úplný, pokud . Z toho plyne, že úplný graf o n vrcholech má právě hran.
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 a vyšší)
Příklady Úplné grafy s vrcholy, kde nabývá hodnot od 1 do 12, jsou zobrazeny níže spolu s počty jejich hran:
Externí odkazy
Kategorie:Typy grafů