Úplný graf

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ů

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

[editovat] 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šší)

[editovat] Příklady

Úplné grafy na 1 až 8 vrcholech:

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

Kategorie: Typy grafů

Úplný graf v jiných jazycích: Català, Deutsch, English, Esperanto, Español, Français, Magyar, Italiano, 한국어, Lietuvių, Polski, Português, Slovenščina, Српски / Srpski, Svenska, ไทย, اردو, Tiếng Việt, 中文

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/%C3%9Apln%C3%BD_graf“
Stránka byla naposledy upravena v Stránka byla naposledy editována 9. 7. 2008 v 02:55.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).