V sobotu 2. listopadu proběhla mohutná oslava naší plnoletosti !!
Multimediaexpo.cz je již 18 let na českém internetu !!
V tiskové zprávě k 18. narozeninám brzy najdete nové a zásadní informace.

Podgraf

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)
m (1 revizi)
(+ Masivní vylepšení)
Řádka 1: Řádka 1:
-
{{Wikipedia-cs|Podgraf|700}}
+
[[Soubor:Subgraph.png|thumb|200px|Původní graf a jeho podgraf]]
 +
Termín '''podgraf''' se v [[teorie grafů|teorii grafů]] používá jako jistá obdoba pojmu [[podmnožina]].
 +
Graf <math>H=(V_H, E_H)</math> je ''podgraf'' [[graf (teorie grafů)|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.
 +
 +
== Indukovaný podgraf ==
 +
[[Soubor:Induced subgraph.png|thumb|200px|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: <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 (graf)|kružnice]]. Ovšem musí být zachovány existence [[cesta (graf)|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ý graf|úplný]]. Nalezení kliky dané velikosti je známým [[NP-úplnost|NP-úplným problémem]].
 +
 +
== Související články ==
 +
* [[Graf (teorie grafů)|Graf]]
 +
 +
 +
{{Článek z Wikipedie}}
[[Kategorie:Grafové pojmy]]
[[Kategorie:Grafové pojmy]]

Verze z 19. 10. 2014, 20:07

Původní graf a jeho podgraf

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:

  1. <math>V_H \subseteq V_G</math>
  2. <math>E_H \subseteq E_G</math>
  3. 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

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: <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


Citováno z „http://ww.multimediaexpo.cz/mmecz/index.php/Podgraf“