Otwórz menu główne

Definicja formalnaEdytuj

Dany jest graf ważony G(V, E, w), gdzie V – zbiór wierzchołków, E – zbiór krawędzi, wfunkcja 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: