Podgraf

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.


Graf H je podgraf grafu G, ak  a 

 Indukovaný podgraf 
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 
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 
Kostra grafu G je taký jeho faktor, ktorý neobsahuje kružnice a je súvislý.

 Pozri aj 
 Graf

Kategória:Teória grafov