Podgraf

Z Wikipedie, otevřené encyklopedie

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

Obsah

[editovat] Podgraf

Původní graf a jeho podgraf
Původní graf a jeho podgraf

Graf H je podgraf grafu G, jestliže V(H) \subseteq V(G) a E(H) \subseteq {E(G) \cap {E(H) \choose 2}}

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

Původní graf a jeho indukovaný podgraf
Původní graf a jeho indukovaný podgraf

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

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.

[editovat] Podívejte se také na

V jiných jazycích