problem spotykany np. w projektowaniu ukladów elektronicznych, kiedy pewna liczbe koncówek nalezy polaczyc ze soba, minimalizujac laczna dlugosc sciezek; model teoretyczny przyjmuje postac grafu G = (V, E), przy czym V jest zbiorem koncówek, a E reprezentuje mozliwe polaczenia miedzy nimi, czyli zbiór krawedzi (u, v) grafu. Kazda krawedz ma wage w(u, v) okreslajaca koszt polaczenia. Zadanie polega na znalezieniu acyklicznego podzbioru T zbioru E laczacego potrzebne wierzcholki, takiego, ze koszt numeryczny polaczenia jest najnizszy. O drzewie T mówi sie, ze "rozpina" graf G, stad nazwa problemu: znalezienie drzewa rozpinajacego o minimalnej wadze. Zob. tez algorytmy Kruskala i Prima.
- algorytmy Kruskala i Prima, algorytmy znajdowaniα...