Podgraf
Appearance
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/de/Subgraph.svg/220px-Subgraph.svg.png)
Graf H je podgraf grafu G, ak a
Indukovaný podgraf[upraviť | upraviť zdroj]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Induced_subgraph.svg/220px-Induced_subgraph.svg.png)
Graf H je indukovaný podgraf grafu G, ak a
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é).