Drzewo Rozpinające
Drzewo rozpinające to struktura, która obejmuje wszystkie wierzchołki grafu G, a jego krawędzie są podzbiorem krawędzi tego grafu. Kluczowym krokiem w konstrukcji drzewa rozpinającego jest usunięcie krawędzi, które tworzą cykle w grafie.
Rząd Acykliczności Grafu
Minimalna liczba krawędzi, które należy usunąć, aby graf stał się acykliczny, nazywana jest rzędem acykliczności grafu lub liczbą cyklometryczną.
Metody Znajdowania Drzewa Rozpinającego
Drzewo rozpinające można skonstruować przy użyciu różnych algorytmów, w tym:
- Algorytm DFS (Depth-First Search)
- Algorytm Dijkstry
Te techniki pozwalają na efektywne wyznaczenie struktury drzewa rozpinającego w danym grafie.
