Minimalne drzewo rozpinające
Wiele problemów z teorii wykresów nazywanych jest drzewem minimalnej rozpiętości. W teorii grafu, drzewo jest sposobem na połączenie wszystkich wierzchołków razem, tak aby istniała dokładnie jedna ścieżka od jednego wierzchołka, do każdego innego wierzchołka drzewa. Jeśli wykres przedstawia kilka miast połączonych drogami, można wybrać kilka dróg, tak aby do każdego miasta można było dojechać z każdego innego, ale aby nie było więcej niż jednej drogi dojazdu z jednego miasta do drugiego.
Wykres może mieć więcej niż jedno drzewo przęsłowe, podobnie jak może być więcej niż jeden sposób wyboru dróg między miastami.
Większość czasu, wykresy są ważone; każde połączenie pomiędzy dwoma miastami ma swoją wagę: może kosztować coś, aby podróżować po danej drodze, lub jedno połączenie może być dłuższe niż drugie, oznacza to, że podróż na tym połączeniu zajmuje więcej czasu. W języku teorii wykresów połączenia te nazywane są krawędziami.
Drzewo o minimalnej rozpiętości to drzewo. Różni się ono od innych drzew tym, że minimalizuje łączne ciężary przylegające do krawędzi. W zależności od tego, jak wykres wygląda, może być więcej niż jedno drzewo rozpiętości minimalnej. Na wykresie, na którym wszystkie krawędzie mają taką samą wagę, każde drzewo jest drzewem o minimalnej rozpiętości. Jeśli wszystkie krawędzie mają różne ciężary (to znaczy: nie ma dwóch krawędzi o tej samej wadze), to istnieje dokładnie jedno drzewo rozpiętości minimalnej.
Minimalna rozpiętość drzewa planarnego wykresu. Każda krawędź jest oznaczona swoją wagą, która w tym przypadku jest w przybliżeniu proporcjonalna do jej długości.
Znalezienie minimalnej rozpiętości drzewa
Pierwsza próba
Stworzenie algorytmu, który odkryje drzewo o minimalnej rozpiętości, może być bardzo proste:
funkcja MST(G,W) : T = { } podczas gdy T nie tworzy drzewa rozpiętości: E, która jest bezpieczna dla T T = związek T {(u,v) } powrót TW tym przypadku "bezpieczne" oznacza, że włączenie krawędzi nie tworzy cyklu na wykresie. Cykl oznacza rozpoczęcie od punktu, przejście do kilku innych punktów i ponowne zakończenie w punkcie początkowym bez dwukrotnego użycia tej samej krawędzi.
Historia
Czeski uczony Otakar Borůvka opracował w 1926 r. pierwszy znany algorytm znajdowania drzewa o minimalnej rozpiętości przęseł. Chciał on rozwiązać problem znalezienia efektywnego pokrycia Moraw prądem. Dziś ten algorytm jest znany jako algorytm Borůvki. Dwa inne algorytmy są dziś powszechnie stosowane. Jeden z nich został opracowany przez Vojtěcha Jarníka w 1930 roku, a w 1957 roku zastosował go Robert Clay Prim. Edsger Wybe Dijkstra odkrył go ponownie w 1959 roku i nazwał algorytmem Prim. Drugi algorytm nazywa się algorytm Kruskala i został opracowany przez Josepha Kruskala w 1956 roku. Wszystkie trzy algorytmy są chciwe i działają w wielomianowym czasie.
Najszybszy dotychczasowy algorytm drzewa o minimalnej rozpiętości został opracowany przez Bernarda Chazelle. Algorytm opiera się na miękkiej stercie, przybliżonej kolejce priorytetów. Jej czas działania to O(m α(m,n)), gdzie m to liczba krawędzi, n to liczba wierzchołków, a α to klasyczna funkcjonalna odwrotność funkcji Ackermanna. Funkcja α rośnie bardzo powoli, tak że dla wszystkich praktycznych celów może być uważana za stałą nie większą niż 4; dlatego też algorytm Chazelle'a przybiera bardzo zbliżony czas liniowy.
Jaki jest najszybszy możliwy algorytm dla tego problemu? Jest to jedno z najstarszych otwartych pytań w informatyce. Wyraźnie widać, że istnieje liniowa dolna granica, ponieważ musimy przynajmniej zbadać wszystkie wagi. Jeśli wagi brzegowe są liczbami całkowitymi o ograniczonej długości bitowej, to znane są algorytmy deterministyczne o liniowym czasie działania. Dla ogólnych wag istnieją algorytmy randomizowane, których oczekiwany czas działania jest liniowy.
Do problemu można podejść również w sposób rozproszony. Jeśli każdy węzeł jest uważany za komputer i żaden węzeł nie wie nic poza własnymi łączami, można jeszcze obliczyć rozproszone drzewo minimalnej rozpiętości.
Pytania i odpowiedzi
P: Czym jest minimalne drzewo rozpinające w teorii grafów?
O: Minimalne drzewo rozpinające to drzewo, które w teorii grafów minimalizuje całkowite wagi przypisane do krawędzi.
P: Czym jest drzewo w teorii grafów?
Drzewo to sposób łączenia wszystkich wierzchołków w teorii grafów, tak aby istniała tylko jedna ścieżka z dowolnego wierzchołka do dowolnego innego wierzchołka drzewa.
P: Jaki jest cel wybierania dróg w scenariuszu teorii grafów przedstawiającym miasta?
O: Celem wyboru dróg w scenariuszu teorii grafów, który reprezentuje miasta, jest umożliwienie dotarcia do każdego miasta z każdego innego miasta, ale z nie więcej niż jednym możliwym sposobem podróżowania z jednego miasta do drugiego.
P: Czy graf może mieć więcej niż jedno drzewo rozpinające?
O: Tak, graf może mieć więcej niż jedno drzewo rozpinające.
P: Jaka jest różnica między minimalnym drzewem rozpinającym a innymi drzewami w teorii grafów?
O: Minimalne drzewo rozpinające minimalizuje całkowite wagi przypisane do krawędzi, podczas gdy inne drzewa nie mają tej cechy.
P: Czym są krawędzie w teorii grafów?
O: Krawędzie to połączenia między dwoma wierzchołkami w teorii grafów.
P: Czy w grafie może istnieć więcej niż jedno minimalne drzewo rozpinające z krawędziami o różnych wagach?
O: Tak, w zależności od tego, jak wygląda graf, może istnieć więcej niż jedno minimalne drzewo rozpinające.
