Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV


2. Základní pojmy / Podgraf

Co je podgraf?

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.

Podgrafy
Obr. č. 2.7 - Podgrafy

Definice

Graf H je podgrafem grafu G, jestliže V(H) je podmnožinou V(G) a E(H) je podmnožinou E(G).
Graf H je indukovaným podgrafem grafu G, jestliže V(H) je podmnožinou V(G) a
E(H) = E(G) průnik (V(H) nad 2).


Úvod

Základní pojmy

Vybrané problémy

Procvičování