Podgraf
Z Wikipedie, otevřené encyklopedie
Termín podgraf se v teorii grafů používá jako jistá obdoba pojmu podmnožina.
Obsah |
[editovat] Podgraf
Graf H je podgraf grafu G, jestliže
a 
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
[editovat] Indukovaný podgraf
Graf H je indukovaný podgraf (též plý podgraf) grafu G, jestliže
a 
Indukovaný podgraf vznikne vymazáním některých vrcholů a pouze těch hran, které do vymazaných vrcholů zasahují.
[editovat] 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)
[editovat] Kostra
Kostra grafu G je takový jeho faktor, který neobsahuje kružnice.
[editovat] Klika
Klikou grafu nazýváme takový podgraf, který je úplný. Nalezení kliky dané velikosti je známým NP-úplným problémem.

