Dopasowanie ułamkowe

W teorii grafów dopasowanie ułamkowe jest uogólnieniem dopasowania , w którym intuicyjnie każdy wierzchołek można podzielić na ułamki dopasowane do różnych sąsiednich wierzchołków.

Definicja

Biorąc pod uwagę wykres G = ( V , E ), ułamkowe dopasowanie w G jest funkcją, która przypisuje każdej krawędzi e w E ułamek f ( e ) w [0, 1] taki, że dla każdego wierzchołka v w V , suma ułamków krawędzi przylegających do v wynosi co najwyżej 1:

{\ Displaystyle \ forall v \ in V: \ suma _ {e \ ni v} f (e) \ równoważnik 1}

Dopasowanie w tradycyjnym sensie jest szczególnym przypadkiem dopasowania ułamkowego, w którym ułamek każdej krawędzi wynosi 0 lub 1: f ( e ) = 1, jeśli e jest w dopasowaniu, i f ( e ) = 0, jeśli to nie jest. Z tego powodu w kontekście dopasowań ułamkowych zwykłe dopasowania są czasami nazywane dopasowaniami całkowitymi .

to liczba $G$ w dopasowaniu, a dopasowana liczba wykresu to rozmiar dopasowania w Analogicznie rozmiar dopasowania ułamkowego jest sumą ułamków wszystkich krawędzi. Ułamkowa liczba dopasowania grafu G jest największym rozmiarem dopasowania ułamkowego w G . Często jest oznaczany przez ${\ Displaystyle \ nu ^ {*} (G)}$ . Ponieważ dopasowanie jest szczególnym przypadkiem dopasowania ułamkowego, dla każdego wykresu G występuje taka liczba całkowa dopasowania G , która jest mniejsza lub równa ułamkowej liczbie dopasowania G ; w symbolach:

{\ Displaystyle \ nu (G) \ równoważnik \ nu ^ {*} (G).}

Wykres, na którym nazywa się stabilnym wykresem .

{\ Displaystyle \ nu (G) = \ nu ^ {*} (G)}

Każdy graf dwudzielny jest stabilny; oznacza to, że w każdym grafie dwudzielnym ułamkowa liczba dopasowania jest liczbą całkowitą i jest równa całkowitej liczbie dopasowania.

Na ogólnym wykresie ${\ Displaystyle \ nu (G)> {\ Frac {2} {3}} \ nu ^ {*} (G).}$ Ułamkowa pasująca liczba jest liczbą całkowitą lub pół-całkowitą.

Prezentacja matrycy

W przypadku wykresu dwudzielnego G = ( X + Y , E ) dopasowanie ułamkowe można przedstawić jako macierz z | X | rzędy i | Y | kolumny. Wartość wpisu w wierszu x i kolumnie y jest ułamkiem krawędzi ( x , y ).

Idealne dopasowanie ułamkowe

Dopasowanie ułamkowe nazywamy idealnym , jeśli suma wag przylegających do każdego wierzchołka wynosi dokładnie 1. Rozmiar idealnego dopasowania to dokładnie | V |/2.

W grafie dwudzielnym G = ( X + Y , E ) ułamkowe dopasowanie nazywamy X-doskonałym , jeśli suma wag przylegających do każdego wierzchołka X wynosi dokładnie 1. Rozmiar X -doskonałego dopasowania ułamkowego wynosi dokładnie | X |.

Dla wykresu dwudzielnego G = ( X + Y , E ), następujące są równoważne:

G dopuszcza X -doskonałe dopasowanie całkowe,
G dopuszcza X -doskonałe dopasowanie ułamkowe i
G spełnia warunek twierdzenia Halla o małżeństwie .

Pierwszy warunek implikuje drugi, ponieważ dopasowanie całkowe jest dopasowaniem ułamkowym. Drugi implikuje trzeci, ponieważ dla każdego podzbioru W z X suma wag w pobliżu wierzchołków W wynosi | W |, więc sąsiadujące z nimi krawędzie koniecznie sąsiadują z co najmniej | W | wierzchołki Y . Zgodnie z twierdzeniem Halla o małżeństwie ostatni warunek implikuje pierwszy. ^{[ potrzebne lepsze źródło ]}

Na wykresie ogólnym powyższe warunki nie są równoważne — największe dopasowanie ułamkowe może być większe niż największe dopasowanie całkowe. Na przykład cykl 3 dopuszcza idealne dopasowanie ułamkowe o rozmiarze 3/2 (ułamek każdej krawędzi to 1/2), ale nie dopuszcza idealnego dopasowania całkowego - największe dopasowanie całkowe ma rozmiar 1.

Aspekty algorytmiczne

Największe dopasowanie ułamkowe na wykresie można łatwo znaleźć za pomocą programowania liniowego lub alternatywnie za pomocą algorytmu maksymalnego przepływu . W grafie dwudzielnym możliwe jest przekonwertowanie maksymalnego dopasowania ułamkowego na maksymalne dopasowanie całkowe o tym samym rozmiarze. Prowadzi to do prostego algorytmu czasu wielomianowego do znajdowania maksymalnego dopasowania na grafie dwudzielnym.

Jeśli G jest grafem dwudzielnym z | X | = | Y | = n , a M jest idealnym dopasowaniem ułamkowym, to macierzowa reprezentacja M jest macierzą podwójnie stochastyczną - suma elementów w każdym wierszu i każdej kolumnie wynosi 1. Algorytm Birkhoffa można wykorzystać do rozłożenia macierzy na sumę wypukłą co najwyżej n ² -2 n +2 macierze permutacji. Odpowiada to rozłożeniu M na wypukłą sumę co najwyżej n ² -2 n +2 doskonałych dopasowań.

Dopasowanie ułamkowe o maksymalnej liczności

Ułamkowe dopasowanie maksymalnej liczności (tj. maksymalnej sumy ułamków) można znaleźć za pomocą programowania liniowego . $wykorzystujący$ silnie wielomianowy algorytm , w czasie

Dopasowanie ułamkowe o maksymalnej wadze

Załóżmy, że każda krawędź na wykresie ma wagę. Ułamkowe dopasowanie maksymalnej wagi na wykresie można znaleźć za pomocą programowania liniowego . Na grafie dwudzielnym możliwe jest przekonwertowanie ułamkowego dopasowania maksymalnej wagi na dopasowanie całkowe maksymalnej wagi o tym samym rozmiarze w następujący sposób:

Niech f będzie dopasowaniem ułamkowym.
Niech H będzie podgrafem G zawierającym tylko krawędzie e z ułamkiem niecałkowitym, 0< f ( e ) <1.
Jeśli H jest puste, to koniec.
jeśli H ma cykl, to musi być parzystej długości (ponieważ graf jest dwudzielny), więc możemy skonstruować nowe dopasowanie ułamkowe f ₁ , przenosząc mały ułamek ε z krawędzi parzystych na nieparzyste i nowe dopasowanie ułamkowe f ₂ poprzez przeniesienie ε z krawędzi nieparzystych na krawędzie parzyste. Ponieważ f jest średnią z f ₁ i f ₂ , waga f jest średnią między wagą f ₁ i f ₂ . Ponieważ f ma maksymalną wagę, wszystkie trzy dopasowania muszą mieć tę samą wagę. Istnieje wybór ε , dla którego co najmniej jeden z f ₁ lub f ₂ ma mniej ułamków niecałkowitych. Kontynuowanie w ten sam sposób prowadzi do całkowitego dopasowania tej samej wagi.
Załóżmy, że H nie ma cyklu i niech P będzie najdłuższą ścieżką w H . Ułamek każdej krawędzi przylegającej do pierwszego lub ostatniego wierzchołka w P musi wynosić 0 (jeśli wynosi 1 - pierwsza / ostatnia krawędź w P narusza warunek dopasowania ułamkowego; jeśli jest w (0,1) - to P nie jest najdłuższy). Dlatego możemy skonstruować nowe dopasowania ułamkowe f ₁ i f ₂ , przenosząc ε z krawędzi nieparzystych na parzyste lub odwrotnie. Ponownie f ₁ i f ₂ muszą mieć maksymalną wagę, a przynajmniej jeden z nich ma mniej ułamków niecałkowitych.

Ułamkowy pasujący polytope

Biorąc pod uwagę wykres G = ( V , E ), ułamkowy pasujący polytope G jest wypukłym polytopem , który reprezentuje wszystkie możliwe ułamkowe dopasowania G . Jest to polytope w R ^{| E |} - | E |-wymiarowa przestrzeń euklidesowa. Każdy punkt ( x ₁ ,..., x _|E| ) w polytope reprezentuje dopasowanie, w którym ułamek każdej krawędzi e wynosi x _e . Polytope jest zdefiniowany przez | E | ograniczenia nieujemności ( x _e ≥ 0 dla wszystkich e w E ) i | V | ograniczenia wierzchołkowe (suma x _e dla wszystkich krawędzi e sąsiadujących z wierzchołkiem v wynosi co najwyżej 1). W grafie dwudzielnym wszystkie wierzchołki ułamkowego pasującego polytopu są całe.

Zobacz też

Kolorowanie ułamkowe