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ů (uzlů) grafu H je totožná s množinou vrcholů grafu G. UH = UG
[editovat] Kostra
Kostra grafu G je takový jeho faktor, který neobsahuje kružnice.

