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 E_i wagę (liczbę rzeczywistą lub całkowitą).

Minimalnym drzewem rozpinającym nazywamy drzewo rozpinające T, dla którego suma wag

$\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.