Multimediaexpo.cz je již 18 let na českém internetu !!
Podgraf
Z Multimediaexpo.cz
Termín podgraf se v teorii grafů používá jako jistá obdoba pojmu podmnožina.
Graf <math>H=(V_H, E_H)</math> je podgraf grafu <math>G=(V_G, E_G)</math>, jestliže platí následující podmínky:
- <math>V_H \subseteq V_G</math>
- <math>E_H \subseteq E_G</math>
- Hrany grafu <math>H</math> mají oba vrcholy v <math>H</math>.
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 |
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: <math> (u, v) \in E_G \rightarrow (u,v) \in E_H</math>.
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, <math>V_H = V_G</math>. 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
| 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. |