Podgraf

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Původní graf a jeho podgraf

Termín podgraf se v teorii grafů používá jako jistá obdoba pojmu podmnožina.

Graf H=(V_H, E_H) je podgraf grafu G=(V_G, E_G), jestliže V_H \subseteq V_G a E_H \subseteq E_G.

Jinými slovy, podgraf vznikne vymazáním některých vrcholů původního grafu, všech hran do těchto vrcholů zasahujících a případně některých dalších hran.

Indukovaný podgraf[editovat | editovat zdroj]

Původní graf a jeho indukovaný podgraf

Graf H je indukovaný podgraf (též plný podgraf) grafu G, jestli že je podgrafem G a pro každé dva vrcholy u, v grafu H plati:  (u, v) \in E_G \rightarrow (u,v) \in E_H.

Indukovaný podgraf vznikne vymazáním některých vrcholů a pouze těch hran, které do vymazaných vrcholů zasahují.

Faktor[editovat | editovat zdroj]

Podgraf H je faktor grafu G, jestliže množina vrcholů grafu H je totožná s množinou vrcholů grafu G, V_H = V_G.

Kostra[editovat | editovat zdroj]

Kostra grafu G je takový jeho faktor, který neobsahuje kružnice. Ovšem musí být zachovány existence cest v grafu. Tzn. musí být zachován počet komponent grafu (počet souvislých částí grafu).

Klika[editovat | editovat zdroj]

Klikou grafu nazýváme takový podgraf, který je úplný. Nalezení kliky dané velikosti je známým NP-úplným problémem.

Související články[editovat | editovat zdroj]