Algorytm Kruskala

1.Opis algorytmu

Algorytm Kruskala jest algorytmem znajdującym, minimalne drzewo rozpinające dla drzewa T(V,E). Dla wszystkich krawędzi istniejących w grafie układa je w kolejności od najmniejszej do największej względem ich wartości. Następnie tworzy najmniejsze drzewo rozpinające dodając do niego po kolei krawędzie jeśli ta nie tworzy nam w nim cyklu (inaczej jest zbędna). Algorytm się kończy po zakończeniu sprawdzania ostatniej krawędzi.  

T(V,E) - Drzewo

Tm(V,Em)- Minimalne drzewo rozpinające 

|E| - ilość krawędzi

{e1,e2,..,e|E|} ∈ E- zbiór wszystkich krawędzi drzewa

Wagi: {e1≤e2≤...≤e|E|}

Dla każdego kolejnego i ∈ (1,2,...,|E|) jeśli ei nie tworzy cyklu to ei∈Em

2. Przykłady

3.Zastosowania algorytmu Kruskala:

Projektowanie sieci (telefoniczne, elektryczne, hydrauliczne, telewizyjne, komputerowe)

Standardowe zastosowanie dotyczy problemu takiego jak projektowanie sieci telefonicznej. Przykład: masz firmę z kilkoma biurami, chcesz wydzierżawić linie telefoniczne, aby połączyć je ze sobą, a firma telefoniczna pobiera różne kwoty za połączenie różnych par miast. Potrzebujesz zestawu linii łączących wszystkie biura przy minimalnym koszcie całkowitym. Powinno to być drzewo rozpinające, ponieważ jeśli sieć nie jest drzewem, zawsze możesz usunąć niektóre krawędzie i zaoszczędzić pieniądze.

Algorytm aproksymacyjny dla problemów NP - zupełnych

Traveling salesperson problem - mniej oczywistym zastosowaniem jest wykorzystanie algorytmu Kruskala do przybliżonego rozwiązania problemu komiwojażera. Najprościej mówiąc problem polega na tym, aby znaleźć najkrótszą ścieżkę, która odwiedza każdy punkt przynajmniej raz. Należy pamiętać, że w przypadku ścieżki odwiedzającej wszystkie punkty dokładnie raz mamy specjalny rodzaj drzewa.

Aplikacje pośrednie (chodzi tutaj bardziej o wykorzystanie minimalnego drzewa rozpinającego w innych specjalistycznych algorytmach)

• Nauka istotnych funkcji weryfikacji twarzy w czasie rzeczywistym
• Ograniczenie przechowywania danych w sekwencjonowaniu aminokwasów w białku
• Model lokalizacji interakcji cząstek w turbulentnych przepływach płynu
• Protokół autokonfiguracji do mostkowania Ethernet w celu uniknięcia cykli w sieci
• Dithering (dodawanie białego szumu do nagrania cyfrowego w celu zmniejszenia zniekształceń)
• Problem najkrótszej ścieżki (Dijkstra)
• Śledzenie i weryfikacja twarzy w czasie rzeczywistym (tj. Lokalizowanie ludzkich twarzy w strumieniu wideo)

Autorzy: Hubert Talar, Maciej Kasprzyk, Mateusz Rus, Paweł Hanusik