Úplný graf

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 K_n, kde n je počet jeho vrcholů.

Definice[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Příklady[editovat | editovat zdroj]

Úplné grafy na 1 až 8 vrcholech: