Definujte kostru neohodnoceného souvislého grafu a popište alespoň jeden algoritmus její konstrukce a diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost.

Kostra grafu (spanning tree)

Nechť G = (V,E) je souvislý graf

→ Podgraf K grafu G nazveme kostrou grafu G, pokud V(K) = V a K je strom

• nesouvislé grafy nemají kostru, kostru má každá souvislá komponenta
• kostra souvislého grafu je tedy souvislý podgraf nad stejnou množinou vrcholů s nejmenším možným počtem hran
• souvislý graf s kružnicemi má více různých koster

Hledání kostry souvislého grafu

→ BFS/DFS s jednoduchými modifikacemi