Wikipedie

Podgraf: Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
interwiki,
Bez shrnutí editace
Řádek 2:
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 <math>V(H)V_H \subseteq V(G)V_G</math> a <math>E(H)E_H \subseteq {E(G)}E_G</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.
Řádek 8:
== Indukovaný podgraf ==
[[Soubor:Induced subgraph.svg|thumb|Původní graf a jeho indukovaný podgraf]]
Graf H je ''indukovaný podgraf'' (též ''plný podgraf'') grafu G, jestližejestli <math>V(H)že \subseteqje podgrafem V(G)</math> a pro každé dva vrcholy u, v grafu H plati: <math>E (Hu, v) =\in {E(G)E_G \caprightarrow {V(Hu,v) \choosein 2}}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, V(H)<math>V_H = V(G)V_G</math>.
 
== Kostra ==
Citováno z „https://cs.wikipedia.org/wiki/Podgraf“