Teorie grafů

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


3. Vybrané problémy / Počty koster grafu

Pro počet koster grafu neplatí žádné jednoduché univerzální pravidlo - většinou si musíme všechny možnosti představit podobně jako obdobné příklady v kombinatorice.

Platí však několik speciálních pravidel podle toho, o jaký graf se jedná:

Počty koster úplného grafu (Cayleyho formule)

Pomocí Cayleyho formule můžeme určit počet stromů na daných n vrcholech - tedy počet koster úplného grafu.

Pro každé n je větší nebo rovno 3 je počet stromů na daných n vrcholech roven nn-2.

Počty koster kružnice

Pokud je graf kružnicí, je počet koster grafu roven |V| (|V| = |E|, můžeme vynechat vždy právě jednu hranu).

Příklad různých koster kružnice
Obr. č. 3.1 - Příklad různých koster kružnice

Počty koster stromu

Pokud je graf stromem, má právě jednu kostru (samotný graf je kostrou).

Příklad

Budeme-li chtít zjistit, kolik různých koster má následující graf (obr. č. 3.2), můžeme si jej rozdělit na jednotlivé podgrafy a výsledek pak získáme vynásobením počtů koster jednotlivých podgrafů (kombinatorické pravidlo součinu).

Příklad výpočtu počtu koster pomocí podgrafů
Obr. č. 3.2 - Příklad výpočtu počtu koster pomocí podgrafů

Na obr. č. 3.2 máme u prvního podgrafu (podgrafy jsou odděleny přerušovanými čarami) 3 možnosti, jak zvolit kostru (jde o kružnici). V druhém podgrafu je pouze jedna možnost výběru hrany (pokud bychom tuto jedinou hranu nevybrali, graf by přestal být souvislým a tím by porušil definici kostry). V třetím podgrafu máme opět 3 možnosti výběru.

Výsledkem je tedy součin 3×1×3 = 9 - máme tedy 9 různých koster grafu.

Všechny různé kostry daného grafu
Obr. č. 3.3 - Všechny různé kostry daného grafu

Úlohy na procvičování


Úvod

Základní pojmy

Vybrané problémy

Procvičování