Podgraf

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

Původní graf a jeho podgraf

Graf $H=(V_{H},E_{H})$ je podgraf grafu $G=(V_{G},E_{G})$, jestliže platí následující podmínky:

1. $V_{H}\subseteq V_{G}$
2. $E_{H}\subseteq E_{G}$
3. Hrany grafu $H$ mají oba vrcholy v $H$.

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 je podgrafem G a pro každé dva vrcholy u, v grafu H platí: $(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

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}$. Faktor též nazýváme hranovým podgrafem.

k-faktor grafu je k-regulární podgraf, který pokrývá všechny vrcholy grafu G. 1-faktor je perfektní párování.

Kostra

Podrobnější informace naleznete v článku Kostra grafu.

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

Podrobnější informace naleznete v článku Klika (teorie grafů).

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

Portály: Matematika