Podgraf

Z Multimediaexpo.cz

Původní graf a jeho podgraf

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

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

$V_{H} \subseteq V_{G}$
$E_{H} \subseteq E_{G}$
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.

Obsah

[skrýt]

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

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 plati: $(u, v) \in E_{G} \to (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.

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

[zobrazit] Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010
Informace o článku. Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii