Minimalne drzewo rozpinające
W świecie Minimalne drzewo rozpinające istnieje szeroka gama opinii i podejść, które mogą generować pasjonujące debaty. Niezależnie od tego, czy ze względu na swoje znaczenie historyczne, kontrowersje, jakie generuje, wpływ na społeczeństwo czy wpływ w sferze kulturowej, Minimalne drzewo rozpinające jest tematem, który budzi zainteresowanie wielu ludzi na całym świecie. W tym artykule zbadamy różne perspektywy i aspekty związane z Minimalne drzewo rozpinające, aby zaoferować kompletną i wzbogacającą wizję na ten temat. Od powstania do ewolucji, poprzez możliwe konsekwencje i prognozy na przyszłość, Minimalne drzewo rozpinające jest tematem, który zasługuje na analizę i dyskusję w sposób otwarty i refleksyjny. Dołącz do nas w tej podróży pełnej odkryć i refleksji na temat 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
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.
| Najważniejsze pojęcia | |
|---|---|
| Wybrane klasy grafów | |
| Algorytmy grafowe | |
| problemy grafowe | |
| Inne zagadnienia |
