Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV
Podgraf grafu G je graf H, který vznikl odebráním některých vrcholů a hran z původního grafu G.
Při odebrání vrcholu je nutné vymazat všechny hrany vedoucí do (z) tohoto vrcholu. Pokud byly odebrány jen tyto hrany, nazývá se podgraf indukovaný. Pokud byly odebrány i jiné hrany, jde obecně o podgraf.
Obr. č. 2.7 - Podgrafy
Graf H je podgrafem grafu G, jestliže V(H) V(G) a E(H) E(G).
Graf H je indukovaným podgrafem grafu G, jestliže V(H) V(G) a
.