Podgraf

Původní graf a jeho podgraf

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

Graf H je podgraf grafu 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

Původní graf a jeho indukovaný podgraf

Graf H je indukovaný podgraf (též plný podgraf) grafu G, jestliže $V(H) \subseteq V(G)$ a $E(H) = {E(G) \cap {V(H) \choose 2}}$

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

Faktor

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

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

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

• Graf