Minimalne drzewo rozpinające
Niniejszy artykuł jest częścią cyklu teoria grafów.
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
Minimalne drzewo rozpinające (ang. MST, minimum spanning tree) – drzewo rozpinające danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo rozpinające o mniejszej sumie wag krawędzi.
Definicja formalnaEdytuj
Dany jest graf ważony G(V, E, w), gdzie V – zbiór wierzchołków, E – zbiór krawędzi, w – funkcja przypisująca krawędzi Ei wagę (liczbę rzeczywistą lub całkowitą).
Minimalnym drzewem rozpinającym nazywamy drzewo rozpinające T, dla którego suma wag
jest najmniejsza z możliwych. Dla niektórych grafów można wskazać wiele drzew rozpinających spełniających tę własność.
Istnieją trzy deterministyczne algorytmy o złożoności liniowo-logarytmicznej znajdujące dla zadanego grafu minimalne drzewo rozpinające. Są to:
- algorytm Borůvki (błędnie nazywany algorytmem Sollina),
- algorytm Prima (nazywany też algorytmem Dijkstry-Prima),
- algorytm Kruskala.