Matroid
(1) Własność wymiany: biorąc dwa zbiory niezależne o różnej liczbie elementów jesteśmy w stanie dodać do mniejszego z nich taki element z większego, że otrzymany zbiór także będzie należał do rodziny zbiorów niezależnych. W tym przypadku zbiorami niezależnymi są lasy rozpinające
(2) Reprezentacja problemu minimalnego drzewa rozpinającego za pomocą matroidu (kliknij ilustrację, aby powiększyć)
(3) Przykład niespełnionej własności wymiany przy próbie przedstawiania problemu komiwojażera za pomocą matroidu. Zbiory 3 i 4 są podzbiorami poprawnych rozwiązań, więc musiałyby być zbiorami niezależnymi. Nie da się jednak do zbioru 3 dodać elementu zbioru 4 w taki sposób, aby uzyskać inny zbiór niezależny
Matroid – struktura matematyczna składająca się z niepustego zbioru elementów E i takiej rodziny jego podzbiorów I, że spełnione są następujące warunki:
- Jeśli jakiś zbiór należy do I, to wszystkie jego podzbiory także należą do I.
- Jeśli weźmiemy dowolne dwa zbiory należące do I o różnej liczbie elementów, to jesteśmy w stanie dodać do mniejszego z nich taki element z większego (spośród tych, które nie należą do mniejszego), że utworzony w ten sposób zbiór także będzie należał do I.
Drugi warunek, zwany własnością wymiany, formalnie może być zapisany jako:
$$⋀↙{A,B∊I}↙{ |A|>|B| }⋁↙{t∊(A-B)} B∪\{t\} ∈ I$$Co istotne, rodzina zbiorów I nie musi zawierać wszystkich możliwych podzbiorów zbioru E. Ważne tylko, aby była spełniona własność wymiany. Przykładowo, dla E={a,b,c,d} prawidłową rodziną I, może być zarówno { {a,b}, {b,c}, {a}, {b}, {c}, ∅}, jak i { {a}, {b}, {c}, {d}, ∅}. Trywialnym przypadkiem poprawnego matroidu jest taki, w którym rodzina I zawiera jedynie zbiór pusty.
Wybrane pojęcia
Zbiory należące do I określane są jako zbiory niezależne. Zbiór niezależny o największej liczbie elementów to baza matroidu. Matroid może mieć wiele baz. W pierwszym wspomnianym wcześniej przykładzie bazami są zbiory {a,b} i {b,c}, w drugim zaś zbiory {a}, {b}, {c}, {d}.
Jeśli każdy element zbioru E ma przyporządkowaną dodatnią liczbę (wagę), to taki matroid jest określany jako matroid ważony. Każdemu zbiorowi niezależnemu również można wtedy przyporządkować wagę, będącą sumą wag wszystkich należących do niego elementów. Dla matroidów grafowych (tzn. takich, w których elementy zbioru E są krawędziami grafu), wagą może być długość krawędzi.
Więcej pojęć związanych z matroidami można znaleźć w książce [1].
Matroidy a algorytmy zachłanne
Matroidy ważone mają duże zastosowanie przy ocenie skuteczności algorytmów zachłannych. Udowodniono, że jeśli problem obliczeniowy da się przedstawić za pomocą matroidu ważonego, to algorytm zachłanny zawsze zwróci rozwiązanie optymalne (dowód jest dostępny w książce [2]). W takim przypadku, jeśli do naszego rozwiązania będziemy zawsze dodawać ten spośród dostępnych elementów zbioru E, który ma największą wagę, to otrzymamy bazę matroidu o największej wadze spośród wszystkich baz. Przykładem takiego algorytmu jest algorytm Kruskala.
Bibliografia
- R.J. Wilson, Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301150662.
- T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
Liczba głosów: 0.
Dodano: 24 kwietnia 2020 13:50, ostatnia edycja: 24 kwietnia 2020 18:28.
Zobacz też
Wyznaczanie najkrótszej ścieżki – zagadnienie polegające na wyszkaniu w grafie takiej ścieżki łączącej dwa wierzchołki, której suma wag krawędzi jest jak najmniejsza.
W przypadku pesymistycznym do wyznaczenia optymalnej ścieżki z wierzchołka A do wierzchołka B konieczne jest wyznaczenie najkrótszych ścieżek z wierzchołka A do wszystkich pozostałych wierzchołków w grafie. Zagadnienie takie jest określane jako poszukiwanie najkrótszych ścieżek z jednego źródła. Do rozwiązywania tego zagadnienia można wykorzystać następujące algorytmy:
Nieco innym zagadnieniem jest poszukiwanie najkrótszych ścieżek pomiędzy każdą parą wierzchołków. W tym celu można wykorzystać algorytmy wymienione powyżej (wykonując je wielokrotnie, za każdym razem przyjmując inny wierzchołek źródłowy) lub algorytmy poszukujące od razu wszystkich ścieżek, takie jak:
Aby znalezienie najkrótszej ścieżki było możliwe, graf nie może zawierać ujemnych cykli osiągalnych z wierzchołka źródłowego. Jeśli taki cykl istnieje, to poruszając się nim „w kółko” cały czas zmniejszamy długość ścieżki. Dopuszczalne jest natomiast występowanie krawędzi o ujemnej wadze, choć nie wszystkie algorytmy dopuszczają ten przypadek.
Jeśli poszukujemy ścieżek o najmniejszej liczbie krawędzi (np. wtedy, gdy wszystkie krawędzie mają taką samą, dodatnią wagę), to zamiast powyższych algorytmów możemy skorzystać z prostego przeszukiwania grafu wszerz.
Wyznaczanie maksymalnego przepływu – problem obliczeniowy polegający na wyznaczeniu maksymalnego przepływu w sieci przepływowej.
Sieć przepływowa jest skierowanym grafem prostym. Każdy łuk (krawędź skierowana w grafie) ma swoją nieujemną wagę, która oznacza maksymalny dopuszczalny przepływ w tym łuku. Na potrzeby tego artykułu nazwijmy rzeczy przepływające przez sieć danymi. Jeden z wierzchołków sieci jest źródłem, z którego wypływają przesyłane dane. Inny z wierzchołków to ujście, do którego te dane wpływają. Zakłada się ponadto, że dla każdego z pozostałych wierzchołków istnieje ścieżka ze źródła do ujścia przechodząca przez ten wierzchołek.
Przepływem w sieci nazywamy przyporządkowanie każdemu łukowi pewnej wartości, która oznacza liczbę danych aktualnie przesyłanych przez ten łuk. Wartości te muszą spełniać następujące warunki:
- Wartość przyporządkowana krawędzi musi być mniejsza lub równa jej wadze (warunek przepustowości).
- Do każdego wierzchołka (poza źródłem i ujściem) musi wpływać tyle samo danych, ile z niego wypływa (warunek zachowania przepływu).
Omawiany problem polega na dobraniu takiego przepływu, aby liczba danych wypływających ze źródła (i zarazem wpływających do ujścia) była jak największa.
Algorytm Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.
Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.