Dopasowywanie (teoria grafów) - Matching (graph theory)

W matematycznej dyscyplinie teorii grafów , dopasowany lub niezależny zbiór krawędzi w grafie nieskierowanym to zbiór krawędzi bez wspólnych wierzchołków . Znalezienie dopasowania w grafie dwudzielnym można traktować jako problem przepływu w sieci .

Definicje

Biorąc pod uwagę wykres G = ( V , E ) dopasowanie M w G jest zestaw parami niesąsiadujących ze sobą krawędziami, z których żaden nie jest pętli ; to znaczy, że żadne dwie krawędzie nie mają wspólnych wierzchołków.

Wierzchołek jest dopasowywany (lub nasycony ), jeśli jest punktem końcowym jednej z krawędzi w dopasowaniu. W przeciwnym razie wierzchołek nie ma sobie równych .

Dopasowanie ilość jest dopasowanie M grafu G , które nie jest podzbiorem inne zgodne. Dopasowanie M grafu G jest maksymalne, jeśli każda krawędź w G ma niepuste przecięcie z co najmniej jedną krawędzią w M . Poniższy rysunek przedstawia przykłady maksymalnych dopasowań (kolor czerwony) na trzech wykresach.

Dopasowanie maksymalna (znany również jako maksymalne dopasowanie liczności) jest dopasowanie zawierająca największą liczbę krawędzi. Może być wiele maksymalnych dopasowań. Dla numeru wykresu ma wielkość dopasowaną do maksimum. Każde maksymalne dopasowanie jest maksymalne, ale nie każde maksymalne dopasowanie jest maksymalnym dopasowaniem. Poniższy rysunek przedstawia przykłady maksymalnych dopasowań na tych samych trzech wykresach. ${\ Displaystyle \ nu (G)}$ ${\ Displaystyle G}$

Idealne dopasowanie jest dopasowanie który pasuje do wszystkich wierzchołków grafu. Oznacza to, że dopasowanie jest idealny, jeśli każdy wierzchołek jest wykresem padającego na krawędzi dopasowywania. Każde idealne dopasowanie jest maksymalne, a więc maksymalne. W niektórych publikacjach używa się terminu „ kompletne dopasowanie” . Na powyższym rysunku tylko część (b) pokazuje idealne dopasowanie. Idealnym dopasowaniem jest również pokrycie krawędzi o minimalnym rozmiarze . Zatem rozmiar maksymalnego dopasowania nie jest większy niż rozmiar minimalnego pokrycia krawędzi: $ν(G) \leq ρ(G)$ . Wykres może zawierać idealne dopasowanie tylko wtedy, gdy ma parzystą liczbę wierzchołków.

Prawie idealne dopasowanie jest taka, w której dokładnie jeden wierzchołek ma sobie równych. Oczywiście wykres może zawierać prawie idealne dopasowanie tylko wtedy, gdy wykres ma nieparzystą liczbę wierzchołków, a dopasowania prawie idealne to dopasowania maksymalne. Na powyższym rysunku część (c) pokazuje prawie idealne dopasowanie. Jeśli żadnemu wierzchołkowi nie towarzyszy jakieś prawie idealne dopasowanie, wtedy wykres nazywa się czynnikiem krytycznym .

Biorąc pod uwagę pasujące M , ścieżka przemienna jest ścieżką, która zaczyna się od niedopasowanego wierzchołka i której krawędzie należą naprzemiennie do dopasowania, a nie do dopasowania. Ścieżka rozszerzanie jest ścieżka przemienny, który rozpoczyna i kończy się z wolnych (niedopasowane) wierzchołków. Lemat Bergego mówi, że dopasowanie M jest maksimum wtedy i tylko wtedy, gdy nie ma ścieżki rozszerzającej względem M .

Wywołane dopasowanie jest dopasowanie to zestaw krawędziowego indukowanego podgrafu .

Nieruchomości

W każdym grafie bez izolowanych wierzchołków suma liczby pasującej i liczby pokrywającej krawędź jest równa liczbie wierzchołków. Jeśli istnieje idealne dopasowanie, to zarówno numer dopasowania, jak i numer okładki krawędzi to $| V | / 2$ .

Jeśli $A$ i $B$ są dwoma maksymalnymi dopasowaniami, to $| | \leq 2| B |$ i $| B | \leq 2| |$ . Aby to zobaczyć, zauważ, że każda krawędź w $B \ A$ może sąsiadować co najwyżej z dwiema krawędziami w $A \ B,$ ponieważ $A$ jest dopasowaniem; ponadto każda krawędź w $A \ B$ sąsiaduje z krawędzią w $B \ A$ przez maksymalnie $B$ , stąd

{\ Displaystyle | A \ setminus B | \ leq 2 | B \ setminus A |.}

Dalej wnioskujemy, że

{\ Displaystyle | A | = | A \ cap B | + | A \ setminus B | \ leq 2 | B \ cap A | +2 | B \ setminus A | = 2 | B |.}

W szczególności pokazuje to, że każde maksymalne dopasowanie jest przybliżeniem 2 maksymalnego dopasowania, a także przybliżeniem 2 minimalnego maksymalnego dopasowania. Ta nierówność jest ciasna: na przykład, jeśli $G$ jest ścieżką z 3 krawędziami i 4 wierzchołkami, rozmiar minimalnego maksymalnego dopasowania to 1, a rozmiar maksymalnego dopasowania to 2.

Charakterystykę spektralną liczby dopasowania grafu podają Hassani Monfared i Mallik w następujący sposób: Niech będzie grafem na wierzchołkach i będzie odmiennymi niezerowymi liczbami czysto urojonymi, gdzie . Następnie dla numeru od jest tylko wtedy, gdy (a) nie jest prawdziwym skosu symetrycznych macierzy z wykresu i wartości własnych i zer, oraz (b) Wszystkie rzeczywiste skosu symetrycznych macierzy z wykresu co najwyżej niezerowe wartości własnych . Zauważ, że (prosty) graf rzeczywistej symetrycznej lub skośnie symetrycznej macierzy porządku ma wierzchołki i krawędzie podane przez niezerowe wpisy poza przekątną . ${\ Displaystyle G}$ ${\ Displaystyle n}$ ${\ Displaystyle \ lambda _ {1}> \ lambda _ {2}> \ ldots > \ lambda _ {k} > 0}$ $k$ $2k\leq n$ ${\ Displaystyle G}$ $k$ ${\ Displaystyle A}$ ${\ Displaystyle G}$ ${\ Displaystyle \ pm \ lambda _ {1}, \ pm \ lambda _ {2}, \ ldots, \ pm \ lambda _ {k}}$ $n-2k$ ${\ Displaystyle G}$ $2k$ ${\ Displaystyle A}$ ${\ Displaystyle n}$ ${\ Displaystyle n}$ ${\ Displaystyle A}$

Dopasowanie wielomianów

Funkcja generująca liczbę dopasowań k krawędzi w grafie nazywana jest wielomianem dopasowującym. Niech G będzie grafem i m _k będzie liczbą k skojarzeń -edge. Jeden pasujący wielomian G to

{\ Displaystyle \ suma _ {k \ geq 0} m_ {k} x ^ {k}.}

Inna definicja podaje pasujący wielomian jako

{\ Displaystyle \ suma _ {k \ geq 0} (-1) ^ {k} m_ {k} x ^ {n-2k}}

gdzie n to liczba wierzchołków na wykresie. Każdy typ ma swoje zastosowania; więcej informacji znajdziesz w artykule na temat dopasowywania wielomianów.

Algorytmy i złożoność obliczeniowa

Dopasowanie maksymalnej kardynalności

Podstawowym problemem optymalizacji kombinatorycznej jest znalezienie maksymalnego dopasowania . Ten problem ma różne algorytmy dla różnych klas grafów.

W nieważonym grafie dwudzielnym problem optymalizacji polega na znalezieniu dopasowania o maksymalnej kardynalności . Problem ten został rozwiązany przez algorytm Hopcroft-Karp w czasie $O (\sqrt V e)$ czasu, a są bardziej skuteczne algorytmy randomizowane , algorytmy zbliżanie i algorytmy specjalnych klas diagramów takich jak dwudzielnych płaskich wykresy , jak opisano w głównym artykule .

Dopasowanie maksymalnej wagi

W ważonym dwudzielnym wykresie problemem optymalizacji jest znalezienie dopasowania o maksymalnej wadze; podwójnym problemem jest znalezienie dopasowania o minimalnej wadze. Ten problem jest często nazywany maksymalnym ważonym dopasowaniem dwuczęściowym lub problemem przypisania . Algorytm węgierski rozwiązuje problemu przydziału i jest jednym z początków algorytmów optymalizacyjnych kombinatorycznych. Wykorzystuje zmodyfikowane wyszukiwanie najkrótszej ścieżki w algorytmie ścieżki rozszerzającej. Jeśli na tym etapie zostanie użyty algorytm Bellmana-Forda , czas działania algorytmu węgierskiego staje się , lub koszt krawędzi może zostać przesunięty z potencjałem osiągnięcia czasu działania za pomocą algorytmu Dijkstry i sterty Fibonacciego . ${\ Displaystyle O (V ^ {2} E)}$ ${\ Displaystyle O (V ^ {2} \ log {V} + VE)}$

W niedwuczęściowym wykresie ważonym problem maksymalnego dopasowania wagi można rozwiązać w czasie za pomocą algorytmu rozkwitu Edmondsa . ${\ Displaystyle O (V ^ {2} E)}$

Maksymalne dopasowania

Maksymalne dopasowanie można znaleźć za pomocą prostego algorytmu zachłannego . Maksymalne dopasowanie jest również maksymalnym dopasowaniem, a zatem możliwe jest znalezienie największego maksymalnego dopasowania w czasie wielomianowym. Jednak nie jest znany algorytm czasu wielomianowego do znajdowania minimalnego maksymalnego dopasowania , czyli maksymalnego dopasowania, które zawiera najmniejszą możliwą liczbę krawędzi.

Maksymalne dopasowanie z k krawędziami jest zestawem dominującym krawędzi z k krawędziami. I odwrotnie, jeśli otrzymamy minimalny zbiór dominujących krawędzi z k krawędziami, możemy skonstruować maksymalne dopasowanie z k krawędziami w czasie wielomianowym. Dlatego problem znalezienia minimalnego maksymalnego dopasowania jest zasadniczo równy problemowi znalezienia minimalnego dominującego zbioru krawędzi. Wiadomo, że oba te dwa problemy optymalizacyjne są NP-trudne ; wersje decyzyjne tych problemów są klasycznymi przykładami problemów NP-zupełnych . Oba problemy można aproksymować ze współczynnikiem 2 w czasie wielomianowym: po prostu znajdź dowolne maksymalne dopasowanie M .

Problemy z liczeniem

Liczba dopasowań na wykresie jest znana jako indeks Hosoya wykresu. Obliczenie tej wielkości jest #P-zupełne , nawet dla grafów dwudzielnych. Jest również #P-zupełne liczenie doskonałych dopasowań , nawet w grafach dwudzielnych , ponieważ obliczenie stałej dowolnej macierzy 0–1 (kolejny problem #P-zupełny) jest tym samym, co obliczenie liczby doskonałych dopasowań w grafie dwudzielnym mając daną macierz jako macierz stronniczości . Istnieje jednak w pełni wielomianowy schemat aproksymacji z randomizacją w czasie do zliczania liczby dopasowań dwudzielnych. Godne uwagi twierdzenie Kastelyna stwierdza, że liczba doskonałych dopasowań w grafie planarnym może być obliczona dokładnie w czasie wielomianowym za pomocą algorytmu FKT .

Liczba doskonałych dopasowań w pełnym grafie K _n (z parzystym n ) jest podana przez silnię podwójną ( n − 1)!!. Liczby dopasowań w pełnych wykresach, bez ograniczania dopasowań jako idealnych, są podane przez numery telefonów .

Znalezienie wszystkich maksymalnie dopasowanych krawędzi

Jednym z podstawowych problemów dopasowanie teorii jest znalezienie w danym wykresie wszystkie krawędzie, które mogą być wydłużone do maksymalnego dopasowania na wykresie (takie krawędzie są nazywane maksymalnie-dopasowywalny krawędzie lub dozwolony krawędzi). Algorytmy dla tego problemu obejmują:

W przypadku grafów ogólnych algorytm deterministyczny w czasie i algorytm zrandomizowany w czasie . ${\ Displaystyle O(VE)}$ ${\ Displaystyle {\ tylda {O}} (V ^ {2.376})}$
W przypadku grafów dwudzielnych, jeśli zostanie znalezione jedno maksymalne dopasowanie, algorytm deterministyczny działa w czasie . ${\ Displaystyle O (V + E)}$

Dwustronne dopasowanie online

Problem opracowania internetowego algorytmu dopasowywania został po raz pierwszy rozważony przez Richarda M. Karpa , Umesh Vazirani i Vijay Vazirani w 1990 roku.

W trybie online węzły po jednej stronie wykresu dwudzielnego przychodzą pojedynczo i muszą być natychmiast dopasowane do drugiej strony wykresu lub odrzucone. Jest to naturalne uogólnienie problemu sekretarki i ma zastosowanie do internetowych aukcji reklam. Najlepszy algorytm online dla nieważonej przypadku maksymalizacji z losowym modelu przybycia, osiąga współczynnik konkurencyjnej o $0,696$ .

Charakterystyki

Twierdzenie Kőniga mówi, że w grafach dwudzielnych maksymalne dopasowanie jest równe wielkości minimalnego pokrycia wierzchołków . Dzięki temu wynikowi, problemy minimalnego pokrycia wierzchołków, maksymalnego zbioru niezależnego i maksymalnej dwuczłonowości wierzchołków mogą być rozwiązywane w czasie wielomianowym dla grafów dwudzielnych.

Twierdzenie Halla o małżeństwie zapewnia charakterystykę grafów dwudzielnych, które mają idealne dopasowanie, a twierdzenie Tutte zapewnia charakterystykę grafów arbitralnych.

Aplikacje

Dopasowanie w ogólnych wykresach

Struktura Kekule się z aromatycznym związkiem składa się z odpowiednim dopasowaniu ich szkielet węglowy , pokazując rozmieszczenie podwójnych wiązań w strukturze chemicznej . Struktury te noszą imię Friedricha Augusta Kekulé von Stradonitz , który wykazał, że benzenowi (w ujęciu teoretycznym wykresu cykl 6-wierzchołkowy) można nadać taką strukturę.
Wskaźnik Hosoya oznacza liczbę niepusty skojarzeń plus jeden; jest stosowany w chemii obliczeniowej i chemii matematycznej do badań związków organicznych.

Dopasowywanie w grafach dwudzielnych

Problem maturalny polega na wyborze minimalnego zestawu zajęć z podanych wymagań do matury.
Problem transportu Hitchcocka obejmuje dopasowanie dwudzielne jako podproblem.
Problem izomorfizmu poddrzewa obejmuje dopasowanie dwudzielne jako podproblem.

Zobacz też

Dopasowywanie w hipergrafach - uogólnienie dopasowywania w grafach.
Dopasowanie ułamkowe .
Dekompozycja Dulmage-Mendelsohna , podział wierzchołków grafu dwudzielnego na podzbiory tak, że każda krawędź należy do idealnego dopasowania wtedy i tylko wtedy, gdy jego punkty końcowe należą do tego samego podzbioru
Kolorowanie krawędzi , podział krawędzi grafu na dopasowania
Dopasowanie wykluczenia , minimalna liczba krawędzi do usunięcia, aby zapobiec istnieniu idealnego dopasowania
Dopasowanie tęczy , dopasowanie w dwudzielnym wykresie z kolorami krawędzi bez powtarzających się kolorów
Wykres skośno-symetryczny , rodzaj wykresu, który może być używany do modelowania wyszukiwania ścieżek naprzemiennych w celu dopasowania
Stabilne dopasowanie , dopasowanie, w którym żadne dwa elementy nie preferują siebie nawzajem od swoich dopasowanych partnerów
Vertex niezależny zestaw , zbiór wierzchołków (zamiast krawędzi), z których żadne dwa nie sąsiadują ze sobą
Problem stabilnego małżeństwa (znany również jako problem stabilnego dopasowania)

Bibliografia

Dalsza lektura

Lovász, László ; Plummer, MD (1986), Teoria dopasowywania , Annals of Discrete Mathematics, 29 , North-Holland, ISBN 0-444-87916-1, numer MR 0859549
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein (2001), Wprowadzenie do algorytmów (wyd. drugie), MIT Press i McGraw-Hill, rozdział 26, s. 643-700, ISBN 0-262-53196-8CS1 maint: wiele nazwisk: lista autorów ( link )
Andras Frank (2004). O węgierskiej metodzie Kuhna – Hołd z Węgier (PDF) (Raport techniczny). Grupa Badawcza Egerváry'ego.
Michael L. Fredman i Robert E. Tarjan (1987), „Stoły Fibonacciego i ich zastosowania w ulepszonych algorytmach optymalizacji sieci”, Journal of the ACM , 34 (3): 595-615, doi : 10.1145/28869.28874 , S2CID 7904683 .
SJ Cyvin i Ivan Gutman (1988), Struktury Kekule w węglowodorach benzenowych , Springer-Verlag
Marek Karpiński i Wojciech Rytter (1998), Fast Parallel Algorithms for Graph Matching Problems , Oxford University Press, ISBN 978-0-19-850162-6

Zewnętrzne linki

Biblioteka grafów z implementacją maksymalnej kardynalności opartej na Hopcroft-Karp i Push-Relabel

Languages

In other projects