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

Definice

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