Úplný graf

Technology

12 hours ago

Author

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šší)