Matematyka dyskretna - Drzewa spinające
Drzewo rozpinające połączonego, niekierowanego grafu $ G $ jest drzewem, które zawiera co najmniej wszystkie wierzchołki $ G $. Wykres może mieć wiele drzew rozpinających.
Przykład
Minimalne drzewo rozpinające
Drzewo opinające z przypisaną wagą mniejszą lub równą wadze każdego możliwego drzewa opinającego ważonego, połączonego i nieukierunkowanego wykresu $ G $, nazywane jest minimalnym drzewem opinającym (MST). Waga drzewa opinającego to suma wszystkich wag przypisanych do każdej krawędzi drzewa opinającego.
Przykład
Algorytm Kruskala
Algorytm Kruskala to zachłanny algorytm, który znajduje minimalne drzewo rozpinające dla połączonego wykresu ważonego. Znajduje drzewo tego wykresu, które zawiera każdy wierzchołek, a całkowita waga wszystkich krawędzi w drzewie jest mniejsza lub równa każdemu możliwemu drzewu rozpinającemu.
Algorytm
Step 1 - Ułóż wszystkie krawędzie danego wykresu $ G (V, E) $ w porządku rosnącym zgodnie z ich wagą krawędzi.
Step 2 - Wybierz najmniejszą ważoną krawędź z wykresu i sprawdź, czy tworzy cykl z utworzonym do tej pory drzewem rozpinającym.
Step 3 - Jeśli nie ma cyklu, dołącz tę krawędź do drzewa opinającego, w przeciwnym razie odrzuć ją.
Step 4 - Powtarzaj krok 2 i krok 3, aż $ (V-1) $ liczba krawędzi pozostanie w drzewie opinającym.
Problem
Załóżmy, że chcemy znaleźć minimalne drzewo rozpinające dla następującego wykresu G przy użyciu algorytmu Kruskala.
Solution
Z powyższego wykresu konstruujemy następującą tabelę -
Nr krawędzi | Para wierzchołków | Grubość krawędzi |
---|---|---|
E1 | (a, b) | 20 |
E2 | (a, c) | 9 |
E3 | (a, d) | 13 |
E 4 | (pne) | 1 |
E5 | (być) | 4 |
E6 | (b, f) | 5 |
E7 | (Płyta CD) | 2 |
E8 | (d, e) | 3 |
E9 | (d, f) | 14 |
Teraz przestawimy tabelę w porządku rosnącym ze względu na wagę krawędzi -
Nr krawędzi | Para wierzchołków | Grubość krawędzi |
---|---|---|
E 4 | (pne) | 1 |
E7 | (Płyta CD) | 2 |
E8 | (d, e) | 3 |
E5 | (być) | 4 |
E6 | (b, f) | 5 |
E2 | (a, c) | 9 |
E3 | (a, d) | 13 |
E9 | (d, f) | 14 |
E1 | (a, b) | 20 |
Ponieważ na ostatnim rysunku mamy wszystkie 5 krawędzi, zatrzymujemy algorytm i jest to minimalne drzewo rozpinające, a jego całkowita waga wynosi $ (1 + 2 + 3 + 5 + 9) = 20 $.
Algorytm Prima
Algorytm Prima, odkryty w 1930 roku przez matematyków, Vojtecha Jarnika i Roberta C. Prima, to zachłanny algorytm, który znajduje minimalne drzewo rozpinające dla połączonego grafu ważonego. Znajduje drzewo tego wykresu, które zawiera każdy wierzchołek, a całkowita waga wszystkich krawędzi w drzewie jest mniejsza lub równa każdemu możliwemu drzewu rozpinającemu. Algorytm Prima jest szybszy na gęstych grafach.
Algorytm
Zainicjuj minimalne drzewo opinające jednym wierzchołkiem, wybranym losowo z wykresu.
Powtarzaj kroki 3 i 4, aż wszystkie wierzchołki zostaną uwzględnione w drzewie.
Wybierz krawędź, która łączy drzewo z wierzchołkiem jeszcze nie znajdującym się w drzewie, tak aby waga krawędzi była minimalna, a włączenie krawędzi nie tworzyło cyklu.
Dodaj wybraną krawędź i wierzchołek, który łączy z drzewem.
Problem
Załóżmy, że chcemy znaleźć minimalne drzewo rozpinające dla następującego wykresu G za pomocą algorytmu Prim.
Solution
Tutaj zaczynamy od wierzchołka „a” i kontynuujemy.
To jest minimalne drzewo rozpinające, a jego całkowita waga wynosi $ (1 + 2 + 3 + 5 + 9) = 20 $.