Santa Claus — modified 2021-12-05 23:57 (395 days ago) — edit — reply
Kostra stromu je samotný strom, protože strom je minimálně souvislý. Přidáním cyklu do stromu vytvoříme možnost zkonstruovat více koster. Přidáním hrany do stromu vznikne kružnice, protože strom je maximální bez kružnic. Následně můžeme z tohoto cyklu jakoukoliv hranu odebrat a získáme kostru. Graf s dvěma kostrami nemůže existovat, protože nemůže existovat cyklus délky dva.
V každém souvislém grafu buď
- Je cyklus (délky ), poté můžeme zkonstruovat alespoň tři kostry, odebráním vždy jedné hrany cyklu.
- Není cyklus, poté se jedná o strom a je to jediná kostra.
Pro graf s n kostrami stačí použít kružnici délky n, z ní můžeme odebrat vždy maximálně jednu hranu, abychom nenarušili souvislost, a máme tedy n možnosti a n koster.