Biorąc pod uwagę dwudzielny wykres z dodatnimi wagami, niech z równym maksymalnemu dopasowaniu masy na wykresie .
Czy to prawda, że jest funkcją podmodularną?
matching
submodularity
George Octavian Rabanca
źródło
źródło
Odpowiedzi:
Definicja . Dla danego zbioru skończonego funkcja zbioru f : 2 A → R jest submodularna, jeśli dla dowolnego XZA fa: 2ZA→ R utrzymuje, że:
f ( X ) + f ( Y ) ≥ f ( X ∪ Y ) + f ( X ∩ Y ) .X, Y⊆ A
Lemat Biorąc pod uwagę dwudzielny wykres z dodatnimi wagami krawędzi, niech f : 2 A → R + będzie funkcją, która odwzorowuje S ⊆ A na wartość maksymalnego dopasowania masy w G [ S ∪ B ] . Zatem f jest podmodularny.G = ( A ∪ B , E) fa: 2ZA→ R+ S.⊆ A G [ S∪ B ] fa
Dowód. Napraw dwa zestawy i niech M ∩ i M ∪ będą dwoma dopasowaniami dla wykresów G [ ( X ∩ Y ) ∪ B ]X, Y⊆ A M.∩ M.∪ G [ ( X∩ Y) ∪ B ] i . Aby udowodnić lemat, wystarczy pokazać, że można podzielić krawędzie w M ∩ i M ∪ na dwa rozłączne dopasowania M X i M YG [ ( X∪ Y) ∪ B ] M.∩ M.∪ M.X M.Y odpowiednio dla wykresów i G [ Y ∪ B ] .G [ X∪ B ] G [ Y∪ B ]
KrawędzieM.∩ i tworzą zbiór naprzemiennych ścieżek i cykli. Niech C oznacza tę kolekcję i obserwować, że żaden cykl C zawiera wierzchołki z X ∖ Y lub Y ∖ X . Dzieje się tak, ponieważ M ∩ nie pasuje do tych wierzchołków.M.∪ do do X∖ Y Y∖ X M.∩
Pozwolić jest zestaw ścieżek C z co najmniej jednym wierzchołkiem wX∖Yi pozwolić P Y jest zestaw ścieżek C z co najmniej jednym wierzchołkiem wY∖X. Dwie takie ścieżki są przedstawione na poniższym rysunku.P.X do X∖ Y P.Y do Y∖ X
Zastrzeżenie 1. .P.X∩ P.Y= ∅
Załóżmy, że w przeciwieństwie, że istnieje ścieżka . Niech x będzie wierzchołkiem w X ∖ Y na ścieżce P i podobnie niech y będzie wierzchołkiem w Y ∖P.∈ P.X∩ P.Y x X∖ Y P. y na ścieżce P . Zauważyć, że ponieważ ani X ani y należące do X. ∩ Y nie należą one do dopasowania M ∩ z definicji, a więc są to punkty końcowe drogi P . Ponadto, ponieważ zarówno x, jakiY∖ X P. x y X∩ Y M.∩ P. x znajdują się w A , ścieżka P ma równą długość, a ponieważ jest to ścieżka naprzemienna, pierwsza lub ostatnia krawędź należy do M ∩ . Dlatego M ∩ odpowiada albo x, albo y , co jest sprzeczne z definicją i potwierdza twierdzenie.y ZA P. M.∩ M.∩ x y
Niech i M Y = ( P X ∩ M ∩ ) ∪ ( ( C ∖ P X ) ∩ M ∪ ) . Oczywiste jest, że M X ∪ M Y = M ∩ ∪ M ∪
źródło