Úplný graf

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 $K_{n}$ , kde $n$ je počet jeho vrcholů.

Definice

Graf G = (V, E) je úplný, pokud $|E|={\left|V\right| \choose 2}$ . Z toho plyne, že úplný graf o n vrcholech má právě ${\frac {n(n-1)}{2}}$ 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 $K_{5}$ a vyšší)

Příklady

Úplné grafy na 1 až 8 vrcholech:

K₁
K₂
K₃
K₄
K₅
K₆
K₇
K₈

Externí odkazy

Obrázky, zvuky či videa k tématu úplný graf na Wikimedia Commons