Twierdzenie Mengera

W matematycznej dyscyplinie teorii grafów twierdzenie Mengera mówi, że w grafie skończonym rozmiar minimalnego zbioru przekrojów jest równy maksymalnej liczbie rozłącznych ścieżek, które można znaleźć między dowolną parą wierzchołków . Udowodniona przez Karla Mengera w 1927 roku, charakteryzuje łączność grafu . Jest to uogólnione przez twierdzenie o max-flow min-cut , które jest ważoną wersją krawędziową i które z kolei jest szczególnym przypadkiem silne twierdzenie o dualności dla programów liniowych.

Łączność brzegowa

Wersja twierdzenia Mengera o łączeniu krawędzi jest następująca:

Niech G będzie skończonym grafem nieskierowanym, a x i y dwoma różnymi wierzchołkami. Wtedy rozmiar minimalnego cięcia krawędzi dla x i y (minimalna liczba krawędzi, których usunięcie rozłącza x i y ) jest równy maksymalnej liczbie niezależnych od krawędzi par ścieżek od x do y .
Rozszerzony na wszystkie pary: graf jest połączony k -krawędziowo (pozostaje połączony po usunięciu mniej niż k krawędzie) wtedy i tylko wtedy, gdy każda para wierzchołków ma k rozłącznych krawędziowo ścieżek pomiędzy nimi.

Łączność wierzchołków

Oświadczenie o łączności wierzchołków twierdzenia Mengera jest następujące:

Niech G będzie skończonym grafem nieskierowanym, a x i y dwoma nieprzylegającymi wierzchołkami. Wtedy rozmiar minimalnego cięcia wierzchołków dla x i y (minimalna liczba wierzchołków, różnych od x i y , których usunięcie rozłącza x i y ) jest równa maksymalnej liczbie parami wewnętrznie rozłącznych ścieżek od x do y .
Rozszerzony na wszystkie pary: wykres jest k -spójny z wierzchołkami (ma więcej niż k wierzchołków i pozostaje połączony po usunięciu mniej niż k wierzchołków) wtedy i tylko wtedy, gdy każda para wierzchołków ma co najmniej k wewnętrznie rozłącznych ścieżek pomiędzy wierzchołkami.

Wszystkie te stwierdzenia (zarówno w wersji krawędziowej, jak i wierzchołkowej) pozostają prawdziwe w grafach skierowanych (przy rozważaniu ścieżek skierowanych).

Krótki dowód

Większość dowodów bezpośrednich rozważa bardziej ogólne stwierdzenie, które umożliwia udowodnienie tego przez indukcję. Wygodne jest również stosowanie definicji, które obejmują niektóre zdegenerowane przypadki. Poniższy dowód dla grafów nieskierowanych działa bez zmian dla grafów skierowanych lub multigrafów, pod warunkiem, że przyjmiemy ścieżkę jako średnią ścieżkę skierowaną.

Dla zbiorów wierzchołków A,B ⊂ G (niekoniecznie rozłącznych) ścieżka AB jest ścieżką w G z początkowym wierzchołkiem w A , końcowym wierzchołkiem w B , i bez wewnętrznych wierzchołków w A lub B . Dopuszczamy ścieżkę z pojedynczym wierzchołkiem w A ∩ B i zerowymi krawędziami. AB -separator o rozmiarze k jest zbiorem S o k wierzchołkach (które mogą przecinać A i B ) takie, że G-S nie zawiera ścieżki AB . Łącznik AB o rozmiarze k jest sumą k rozłącznych wierzchołków AB -ścieżek.

Twierdzenie: Minimalny rozmiar separatora AB jest równy maksymalnemu rozmiarowi złącza AB .

Innymi słowy, jeśli żadne k −1 wierzchołków nie odłącza A od B , to istnieje k rozłącznych ścieżek od A do B . Ten wariant implikuje powyższe stwierdzenie o łączności wierzchołków: dla x,y ∈ G w poprzedniej sekcji, zastosuj obecne twierdzenie do G −{ x,y } z A = N(x) , B = N(y) , sąsiedni wierzchołki x,y . Następnie zbiór wierzchołków rozłączających x i y to to samo, co separator AB , a usunięcie wierzchołków końcowych w zbiorze niezależnych ścieżek xy daje złącze AB .

Dowód twierdzenia: Indukcja po liczbie krawędzi w G . Dla G bez krawędzi minimalnym separatorem AB jest A ∩ B , który sam jest łącznikiem AB składającym się ze ścieżek o jednym wierzchołku.

Dla G mającego krawędź e , możemy założyć przez indukcję, że Twierdzenie zachodzi dla G−e . Jeśli G-e ma minimalny separator AB o rozmiarze k , to w G-e , a zatem w G, istnieje łącznik AB o rozmiarze k .

Ilustracja do dowodu.

W przeciwnym razie niech S będzie AB -separatorem G-e o rozmiarze mniejszym niż k , tak że każda AB -ścieżka w G zawiera wierzchołek S lub krawędź e . Rozmiar S musi wynosić k-1 , ponieważ gdyby był mniejszy, S wraz z dowolnym punktem końcowym e byłby lepszym AB -separatorem G . W G-S istnieje droga AB przez e , ponieważ sam S jest zbyt mały, aby być AB -separatorem G . Niech v 1 będzie wcześniejszym, a v 2 późniejszym wierzchołkiem e na takiej ścieżce. Wtedy v 1 jest osiągalne z A , ale nie z B w G−S − e , podczas gdy v 2 jest osiągalne z B , ale nie z A.

Niech S 1 = S ∪ {v 1 } i rozważmy minimum AS 1 -separator T w G−e . Ponieważ v 2 nie jest osiągalne z A w G-S 1 , T jest także AS 1 -separatorem w G . Wtedy T jest także AB -separatorem w G (ponieważ każda AB -ścieżka przecina S 1 ). Stąd ma rozmiar co najmniej k . Poprzez indukcję, G-e zawiera złącze AS 1 C 1 o rozmiarze k . Ze względu na jego rozmiar, punkty końcowe ścieżek w nim muszą być dokładnie S 1 .

Podobnie, przyjmując, że S 2 = S ∪ {v 2 } , minimalny separator S 2 B ma rozmiar k i istnieje łącznik S 2 B C 2 o rozmiarze k , ze ścieżkami, których punktami początkowymi są dokładnie S 2 .

Ponadto, ponieważ S 1 rozłącza G , każda ścieżka w C 1 jest wewnętrznie rozłączna z każdą ścieżką w C 2 , i możemy zdefiniować złącze AB o rozmiarze k w G poprzez łączenie ścieżek ( k-1 ścieżek przechodzących przez S i jednej ścieżki biegnącej przez e=v 1 v 2 ). CO BYŁO DO OKAZANIA

Inne dowody

Skierowana wersja krawędziowa twierdzenia z łatwością implikuje inne wersje. Aby wywnioskować wersję skierowanego wierzchołka grafu, wystarczy podzielić każdy wierzchołek v na dwa wierzchołki v 1 , v 2 , przy czym wszystkie krawędzie wejściowe idą do v 1 , wszystkie krawędzie wychodzące idą od v 2 , a dodatkowa krawędź od v 1 do v 2 . Skierowane wersje twierdzenia implikują natychmiast wersje nieskierowane: wystarczy zastąpić każdą krawędź grafu nieskierowanego parą krawędzi skierowanych (digon).

Z kolei wersja z krawędzią skierowaną wynika z jej ważonego wariantu, twierdzenia o maksymalnym przepływie i minimalnym cięciu . Jego dowody są często dowodami poprawności dla algorytmów maksymalnego przepływu. Jest to również szczególny przypadek jeszcze bardziej ogólnego (mocnego) twierdzenia o dualności dla programów liniowych .

Sformułowanie, które dla skończonych digrafów jest równoważne z powyższym sformułowaniem, to:

Niech A i B będą zbiorami wierzchołków skończonego digrafu G . Wtedy istnieje rodzina P rozłącznych AB - ścieżek i zbiór rozdzielający AB , który składa się z dokładnie jednego wierzchołka z każdej ścieżki w P.

W tej wersji twierdzenie dość łatwo wynika z twierdzenia Kőniga : w grafie dwudzielnym minimalny rozmiar pokrycia jest równy maksymalnemu rozmiarowi dopasowania.

Robi się to w następujący sposób: zamień każdy wierzchołek v w oryginalnym digrafie D na dwa wierzchołki v' , v'' , a każdą krawędź uv na krawędź u'v'' ; dodatkowo uwzględnij krawędzie v'v'' dla każdego wierzchołka v , który nie znajduje się ani w A , ani w B . W rezultacie otrzymujemy graf dwudzielny, którego jedna strona składa się z wierzchołków v' , a druga z wierzchołków v'' .

Stosując twierdzenie Kőniga otrzymujemy pasujące M i okładkę C tego samego rozmiaru. W szczególności dokładnie jeden punkt końcowy każdej krawędzi M znajduje się w C . Dodaj do C wszystkie wierzchołki a'' dla a w A i wszystkie wierzchołki b' dla b w B . Niech P będzie zbiorem wszystkich AB -ścieżek złożonych z krawędzi uv w D takich, że u'v'' należy do M. Niech Q w pierwotnym grafie składa się ze wszystkich wierzchołków v takich, że zarówno v', jak i v'' należą do C . Łatwo sprawdzić, że Q jest zbiorem rozdzielającym AB , że każda ścieżka w rodzinie P zawiera dokładnie jeden wierzchołek z Q i że każdy wierzchołek w Q leży na ścieżce z P , zgodnie z życzeniem.

Nieskończone wykresy

Twierdzenie Mengera obowiązuje dla grafów nieskończonych iw tym kontekście ma zastosowanie do minimalnego przekroju między dowolnymi dwoma elementami, które są albo wierzchołkami, albo końcami grafu ( Halin 1974 ). Następujący wynik Rona Aharoniego i Eli Bergera był pierwotnie hipotezą zaproponowaną przez Paula Erdősa i zanim został udowodniony, był znany jako hipoteza Erdősa-Mengera . Jest to równoważne twierdzeniu Mengera, gdy wykres jest skończony.

Niech A i B będą zbiorami wierzchołków w (prawdopodobnie nieskończonym) digrafie G . Wtedy istnieje rodzina P rozłącznych ścieżek A - B i zbiór rozdzielający, który składa się z dokładnie jednego wierzchołka z każdej ścieżki w P.

Zobacz też

Dalsza lektura

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Menger%27s_theorem&oldid=1136249214 ”