Array ( [0] => 14674556 [id] => 14674556 [1] => cswiki [site] => cswiki [2] => Podgraf [uri] => Podgraf [3] => [img] => [4] => [day_avg] => [5] => [day_diff] => [6] => [day_last] => [7] => [day_prev_last] => [8] => [oai] => [9] => [is_good] => [10] => [object_type] => [11] => 0 [has_content] => 0 [12] => [oai_cs_optimisticky] => ) Array ( [0] => [[Soubor:Subgraph.svg|thumb|Původní graf a jeho podgraf]] [1] => Termín '''podgraf''' se v [[teorie grafů|teorii grafů]] používá jako jistá obdoba pojmu [[podmnožina]]. [2] => [3] => Graf H=(V_H, E_H) je ''podgraf'' [[graf (teorie grafů)|grafu]] G=(V_G, E_G), jestliže platí následující podmínky: [4] => # V_H \subseteq V_G [5] => # E_H \subseteq E_G [6] => # Hrany grafu H mají oba vrcholy v H. [7] => 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. [8] => [9] => == Indukovaný podgraf == [10] => [[Soubor:Induced subgraph.svg|thumb|Původní graf a jeho indukovaný podgraf]] [11] => 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 platí: (u, v) \in E_G \rightarrow (u,v) \in E_H. [12] => [13] => Indukovaný podgraf vznikne vymazáním některých vrcholů a ''pouze'' těch hran, které do vymazaných vrcholů zasahují. [14] => [15] => == Faktor == [16] => 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'''. [17] => [18] => k-faktor grafu ke [[Regulární graf|k-regulární podgraf]], který pokrývá všechny vrcholy grafu G. 1-faktor je [[Párování grafu|perfektní párování]]. [19] => [20] => == Kostra == [21] => {{Podrobně|Kostra grafu}} [22] => 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). [23] => [24] => == Klika == [25] => {{Podrobně|Klika (teorie grafů)}} [26] => 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]]. [27] => [28] => == Související články == [29] => * [[Graf (teorie grafů)|Graf]] [30] => [31] => {{Portály|Matematika}} [32] => [[Kategorie:Grafové pojmy]] [] => )
good wiki

Podgraf

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.

More about us

About

Expert Team

Vivamus eget neque lacus. Pellentesque egauris ex.

Award winning agency

Lorem ipsum, dolor sit amet consectetur elitorceat .

10 Year Exp.

Pellen tesque eget, mauris lorem iupsum neque lacus.

You might be interested in

,'Soubor:Subgraph.svg','teorie grafů','podmnožina','graf (teorie grafů)','Soubor:Induced subgraph.svg','Regulární graf','Párování grafu','kružnice (graf)','cesta (graf)','Úplný graf','NP-úplnost','Graf (teorie grafů)'

NP-úplnost

Podmnožina