Rozkład Dulmage-Mendelsohna

W teorii grafów rozkład Dulmage'a -Mendelsohna polega na podziale wierzchołków grafu dwudzielnego na podzbiory, z tą właściwością, że dwa sąsiednie wierzchołki należą do tego samego podzbioru wtedy i tylko wtedy, gdy są ze sobą sparowane w idealnym dopasowaniu wykres. Został nazwany na cześć AL Dulmage'a i Nathana Mendelsohna , którzy opublikowali go w 1958 roku. Uogólnieniem dowolnego wykresu jest rozkład Edmondsa-Gallai przy użyciu algorytmu Blossoma .

Budowa

Rozkład Dulmage-Mendelshon można skonstruować w następujący sposób. (jest przypisywany temu, kto z kolei przypisuje go).

₀ Niech G będzie grafem dwudzielnym, M pasującym o maksymalnej liczności w G , a V zbiorem wierzchołków G niedopasowanych przez M („wolne wierzchołki”). Następnie G można podzielić na trzy części:

Dekompozycja EOU

• ₀ E - wierzchołki parzyste - wierzchołki osiągalne z V przez M -przemienną ścieżkę o parzystej długości.
• ₀ O - nieparzyste wierzchołki - wierzchołki osiągalne z V przez M -przemienną ścieżkę o nieparzystej długości.
• ₀ U - the unreachable vertices - wierzchołki nieosiągalne z V przez M -przemienną ścieżkę.

₀₀₀ Ilustracja jest pokazana po lewej stronie. Pogrubione linie to krawędzie M. Słabe linie to inne krawędzie G . Czerwone kropki to wierzchołki V . Zauważ, że V jest zawarte w E , ponieważ jest osiągalne z V ścieżką o długości 0.

Na podstawie tego rozkładu krawędzie w G można podzielić na sześć części zgodnie z ich punktami końcowymi: EU, EE, OO, OU, EO, UU . Ten rozkład ma następujące właściwości:

1. Zbiory E , O , U są parami rozłączne. Dowód : U jest rozłączne z E i O z definicji. Aby udowodnić, że E i O są rozłączne, załóżmy, że jakiś wierzchołek v ma zarówno zmienną ścieżkę o parzystej długości do niedopasowanego wierzchołka u ₁ , jak i zmienną ścieżkę o nieparzystej długości do niedopasowanego wierzchołka u ₂ . Następnie połączenie tych dwóch ścieżek daje ścieżkę rozszerzającą od u ₁ przez v do u ₂ . Jest to jednak sprzeczne z założeniem, że M jest dopasowaniem o maksymalnej liczności.
2. Zbiory E , O , U nie zależą od dopasowania o maksymalnej liczności M (tj. każde dopasowanie o maksymalnej liczności definiuje dokładnie ten sam rozkład).
3. G zawiera tylko krawędzie OO, OU, EO i UU .
4. Każde dopasowanie maksymalnej liczności w G zawiera tylko krawędzie EO i UU .
5. Każde dopasowanie maksymalnej liczności w G nasyca wszystkie wierzchołki w O i wszystkie wierzchołki w U .
6. Rozmiar dopasowania o maksymalnej liczności w G to | O | + | U | / 2.
7. Jeśli G ma doskonałe dopasowanie, to wszystkie wierzchołki G są w U .

Alternatywna definicja

Gruby rozkład

Niech G = ( X+Y , E ) będzie grafem dwudzielnym i niech D będzie zbiorem wierzchołków w G , które nie są dopasowane w co najmniej jednym maksymalnym dopasowaniu G . Wtedy D jest z konieczności niezależnym zbiorem . Tak więc G można podzielić na trzy części:

1. Wierzchołki w D ∩ X i ich sąsiedzi;
2. Wierzchołki w D ∩ Y i ich sąsiedzi;
3. Pozostałe wierzchołki.

Każde maksymalne dopasowanie w G składa się z dopasowań w pierwszej i drugiej części, które pasują do wszystkich sąsiadów D , wraz z doskonałym dopasowaniem pozostałych wierzchołków. Jeśli G ma doskonałe dopasowanie, to trzeci zestaw zawiera wszystkie wierzchołki G.

Drobny rozkład

Trzeci zestaw wierzchołków w dekompozycji zgrubnej (lub wszystkie wierzchołki w grafie z doskonałym dopasowaniem) można dodatkowo podzielić na podzbiory, wykonując następujące kroki:

• Znajdź idealne dopasowanie G .
• Utwórz skierowany graf H , którego wierzchołki są dopasowanymi krawędziami w G . Dla każdej niedopasowanej krawędzi ( x,y ) w G dodaj skierowaną krawędź w H od dopasowanej krawędzi x do dopasowanej krawędzi y .
• Znajdź silnie połączone składowe powstałego wykresu.
• Dla każdego składnika H utwórz podzbiór rozkładu Dulmage'a-Mendelsohna składający się z wierzchołków w G , które są punktami końcowymi krawędzi składnika.

Aby zobaczyć, że ten podział na podzbiory charakteryzuje krawędzie należące do idealnych dopasowań, załóżmy, że dwa wierzchołki x i y w G należą do tego samego podzbioru dekompozycji, ale nie są już dopasowane przez początkowe idealne dopasowanie. Wtedy istnieje silnie spójna składowa w H zawierająca krawędź x,y . Ta krawędź musi należeć do prostego cyklu w H (z definicji silnej łączności), który koniecznie odpowiada naprzemiennemu cyklowi w G (cykl, którego krawędzie zmieniają się między dopasowanymi i niedopasowanymi krawędziami). Ten naprzemienny cykl może być wykorzystany do zmodyfikowania początkowego idealnego dopasowania w celu wytworzenia nowego dopasowania zawierającego krawędź x,y .

Krawędź x,y grafu G należy do wszystkich doskonałych dopasowań G wtedy i tylko wtedy, gdy x i y są jedynymi członkami swojego zbioru w rozkładzie. Taka krawędź istnieje wtedy i tylko wtedy, gdy pasująca liczba wykluczeń grafu wynosi jeden.

Rdzeń

Jako kolejny składnik rozkładu Dulmage-Mendelsohna, Dulmage i Mendelsohn zdefiniowali rdzeń wykresu jako sumę jego maksymalnych dopasowań. Pojęcie to należy jednak odróżnić od rdzenia w sensie homomorfizmów grafów oraz od k -rdzeni utworzonej przez usunięcie wierzchołków niskiego stopnia.

Aplikacje

Dekompozycja ta została wykorzystana do podziału siatek w analizie elementów skończonych oraz do wyznaczenia określonych, niedookreślonych i przeokreślonych równań w układach równań nieliniowych. Został również użyty w algorytmie dopasowywania rang do maksimum .

Wariant asymetryczny

Istnieje inna dekompozycja grafu dwudzielnego, która jest asymetryczna - rozróżnia wierzchołki po jednej stronie grafu i wierzchołki po drugiej stronie. Można go użyć do znalezienia dopasowania o maksymalnej liczności bez zazdrości w nieważonym grafie dwudzielnym, a także dopasowania o maksymalnej liczności przy minimalnym koszcie w ważonym grafie dwudzielnym.

Linki zewnętrzne

• Dobre wyjaśnienie jego zastosowania do układów równań nieliniowych jest dostępne w tym artykule: [1]
• Implementacja algorytmu typu open source jest dostępna jako część biblioteki rzadkiej macierzy: SPOOLES
• Grafowo-teoretyczne aspekty rozwiązywania ograniczeń w projekcie SST: [2]