Teorie grafů

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


2. Základní pojmy / Kostra grafu

Kostrou grafu budeme rozumět libovolný podgraf, který hranami spojuje všechny vrcholy původního grafu a zároveň sám neobsahuje žádnou kružnici (→ jde o strom).

Definice kostry

Nechť G = (V,E) je graf. Libovolný strom (V,E'), kde E' je podmnožinouE, nazveme kostrou grafu.

Příklady

Pokud původní graf (graf, ke kterému hledáme kostru) obsahuje kružnici, pak máme více možností, jak kostru zvolit.

Příklad různých koster stejného grafu
Obr. č. 2.31 - Příklad různých koster stejného grafu

Hledání minimální kostry
Počty koster grafu


Úvod

Základní pojmy

Vybrané problémy

Procvičování