Podgraf

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Podgraf je časť grafu, ktorá vznikne z pôvodného grafu vymazaním niektorých jeho vrcholov, všetkých hrán vedúcich do týchto vrcholov, poprípade vymazaním ďalších jeho hrán.

Pojem podgraf sa v teórii grafov používa ako istá obdoba pojmu podmnožina.

Pôvodný graf a jeho podgraf

Graf H je podgraf grafu G, ak V(H) \subseteq V(G) a E(H) \subseteq {E(G) \cap {V(H) \choose 2}}

Indukovaný podgraf[upraviť | upraviť zdroj]

Pôvodný graf a jeho indukovaný podgraf

Graf H je indukovaný podgraf grafu G, ak V(H) \subseteq V(G) a E(H) = {E(G) \cap {V(H) \choose 2}}

Indukovaný podgraf vznikne vymazaním niektorých vrcholov a iba tých hrán, ktoré do vymazaných vrcholov zasahujú.

Faktor[upraviť | upraviť zdroj]

Podgraf H je faktor grafu G, ak množina vrcholov grafu H je totožná s množinou vrcholov grafu G. V(H) = V(G)

Kostra[upraviť | upraviť zdroj]

Kostra grafu G je taký jeho faktor, ktorý neobsahuje kružnice a je súvislý.

Pozri aj[upraviť | upraviť zdroj]

Tento článok je čiastočný alebo úplný preklad článku podgraf na českej Wikipédii (číslo revízie nebolo určené).