Minimalne drzewo rozpinające

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 formalna

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

∑ e ∈ T w ( e ) {\displaystyle \sum _{e\in T}w(e)}

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.