Podgraf

Z Wikipedie, otevřené encyklopedie

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

Obsah 1 Podgraf 2 Indukovaný podgraf 3 Faktor 4 Kostra 5 Klika 6 Související články

[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.

[editovat] Související články

• Graf