Dopasowanie maksymalnej kardynalności - Maximum cardinality matching

Dopasowanie maksymalnej kardynalności jest podstawowym problemem w teorii grafów . Dostajemy wykres , a celem jest znalezienie dopasowania zawierającego jak najwięcej krawędzi, to znaczy podzbiór krawędzi o maksymalnej kardynalności, tak aby każdy wierzchołek sąsiadował co najwyżej z jedną krawędzią podzbioru. Ponieważ każda krawędź pokryje dokładnie dwa wierzchołki, ten problem jest równoważny zadaniu znalezienia dopasowania, które obejmuje jak najwięcej wierzchołków. ${\ Displaystyle G}$

Ważnym szczególnym przypadkiem problemu dopasowania maksymalnej kardynalności jest sytuacja, gdy G jest grafem dwudzielnym , którego wierzchołki V są podzielone między lewe wierzchołki w X i prawe wierzchołki w Y , a krawędzie w E zawsze łączą lewy wierzchołek z prawym wierzchołkiem. W takim przypadku problem można skutecznie rozwiązać za pomocą prostszych algorytmów niż w przypadku ogólnym.

Algorytmy dla grafów dwudzielnych

Najprostszym sposobem obliczenia dopasowania maksymalnej kardynalności jest postępowanie zgodnie z algorytmem Forda-Fulkersona . Algorytm ten rozwiązuje bardziej ogólny problem obliczania maksymalnego przepływu , ale można go łatwo zaadaptować: po prostu przekształcamy wykres w sieć przepływu , dodając wierzchołek źródłowy do grafu mającego krawędź do wszystkich lewych wierzchołków w X , dodając wierzchołek ujścia mając krawędź ze wszystkich prawych wierzchołków w Y , zachowując wszystkie krawędzie między X i Y i dając pojemność 1 każdej krawędzi. Algorytm Ford-Fulkersona dokona następnie wielokrotnie znajdowanie ścieżki nadbudowy z niektórych x ∈ X pewnym y ∈ Y i aktualizowanie dopasowanie M poprzez symetryczny różnicę tą drogą z M (przy założeniu, że takie istnieje ścieżka). Ponieważ każdą ścieżkę można znaleźć w czasie, czas działania wynosi , a maksymalne dopasowanie składa się z krawędzi E, które przenoszą przepływ z X do Y . ${\ Displaystyle \ O (E)}$${\ Displaystyle \ O (VE)}$

Udoskonalenie tego algorytmu zapewnia bardziej rozbudowany algorytm Hopcrofta-Karpa , który jednocześnie wyszukuje wiele ścieżek rozszerzających. Ten algorytm działa w czasie. ${\ Displaystyle O ({\ sqrt {V}} E)}$

Algorytm Chandrana i Hochbauma dla grafów dwudzielnych działa w czasie zależnym od wielkości maksymalnego dopasowania , którym jest . Używając operacji logicznych na słowach o rozmiarze, złożoność jest dalej ulepszana do . ${\displaystyle k}$${\displaystyle |X|<|Y|}$${\ Displaystyle O \ lewo (\ min \ {| X | k, e \} + {\ sqrt {k}} \ min \ {k ^ {2}, e \} \ prawej)}$${\ Displaystyle \ lambda}$${\ Displaystyle O \ lewo (\ min \ lewo \ {| X | k {\ Frac {| X | | Y |} {\ Lambda}}, E \ prawej \} + k ^ {2} + {\ Frac {k^{2.5}}{\lambda}}\prawo)}$

Istnieją bardziej wydajne algorytmy dla specjalnych rodzajów grafów dwudzielnych:

• W przypadku rzadkich grafów dwudzielnych problem maksymalnego dopasowania można rozwiązać za pomocą algorytmu Madry'ego opartego na przepływach elektrycznych.${\ Displaystyle {\ tylda {O}} (E ^ {10/7})}$
• W przypadku płaskich grafów dwudzielnych problem można rozwiązać w czasie, gdzie n jest liczbą wierzchołków, redukując problem do maksymalnego przepływu z wieloma źródłami i ujściami.${\ Displaystyle O (n \ log ^ {3} n)}$

Algorytmy dla dowolnych grafów

Algorytm kwiat wyszukuje pasujące maksymalna liczności w ogólnych (niekoniecznie dwustronnym) wykresów. Działa w czasie . Lepszą wydajność O ( √ V E ) dla grafów ogólnych, dorównującą wydajności algorytmu Hopcrofta-Karpa na grafach dwudzielnych, można osiągnąć za pomocą znacznie bardziej skomplikowanego algorytmu Micali i Vazirani. To samo ograniczenie zostało osiągnięte przez algorytm Bluma ( de ) oraz algorytm Gabowa i Tarjana . ${\ Displaystyle O (| V | ^ {2} \ cdot | E |)}$

Alternatywne podejście wykorzystuje randomizację i opiera się na algorytmie szybkiego mnożenia macierzy . Daje to algorytm losowy dla ogólnych grafów o złożoności . W teorii jest to lepsze dla wystarczająco gęstych grafów , ale w praktyce algorytm jest wolniejszy. ${\ Displaystyle O (V ^ {2.376})}$

Inne algorytmy dla zadania są przeglądane przez Duana i Pettiego (patrz Tabela I). Jeśli chodzi o algorytmy aproksymacyjne , zwracają również uwagę, że algorytm rozkwitu oraz algorytmy Micali i Vazirani można postrzegać jako algorytmy aproksymacyjne działające w czasie liniowym dla dowolnego ustalonego ograniczenia błędu.

Zastosowania i uogólnienia

• Dzięki znalezieniu dopasowania o maksymalnej kardynalności można zdecydować, czy istnieje dopasowanie idealne .
• Problem znalezienia dopasowania o maksymalnej wadze w grafie ważonym nazywa się problemem maksymalnej wagi dopasowania , a jego ograniczenie do grafów dwudzielnych nazywa się problemem przypisania . Jeśli każdy wierzchołek może być dopasowany do kilku wierzchołków jednocześnie, to jest to uogólniony problem przypisania .
• Priorytet dopasowanie jest zwłaszcza dopasowanie maksymalna liczności w którym wierzchołki o wyższym priorytecie są dopasowane pierwsze.
• Problem znalezienia dopasowania maksymalnej kardynalności w hipergrafie jest NP-zupełny nawet dla hipergrafów trójjednorodnych.

Bibliografia