Twierdzenie Berge'a

W teorii grafów twierdzenie Berge'a stwierdza, że dopasowanie M na grafie G jest maksymalne ( zawiera największą możliwą liczbę krawędzi) wtedy i tylko wtedy, gdy nie ma ścieżki rozszerzającej (ścieżka, która zaczyna się i kończy na wolnych (niedopasowanych) wierzchołkach i zmienia się między krawędziami w pasowaniu i nie w dopasowaniu) z M .

Udowodnił to francuski matematyk Claude Berge w 1957 r. (choć zaobserwowali go już Petersen w 1891 r. i Kőnig w 1931 r.).

Dowód

Aby udowodnić twierdzenie Berge'a, potrzebujemy najpierw lematu . Weźmy wykres G i niech M i M′ będą dwoma dopasowaniami w G . Niech G′ będzie wykresem wypadkowym z różnicy symetrycznej M i M′ ; tj. ( M - M' ) ∪ ( M' - M ). G′ będzie składać się z połączonych elementów, które są jednym z następujących:

Odosobniony wierzchołek .
Parzysty cykl , którego krawędzie zmieniają się między M i M′ .
Ścieżka , której krawędzie zmieniają się między M i M′ , z różnymi punktami końcowymi.

Lemat można udowodnić, obserwując, że każdy wierzchołek w G′ może przypadać co najwyżej na 2 krawędzie: jedną z M i jedną z M′ . Grafy, w których każdy wierzchołek ma stopień mniejszy lub równy 2, muszą składać się z izolowanych wierzchołków , cykli lub ścieżek . Ponadto każda ścieżka i cykl w G′ musi zmieniać się między M i M′ . Aby cykl mógł to zrobić, musi mieć równą liczbę krawędzi z M i M′ , a zatem mieć parzystą długość.

Udowodnijmy teraz przeciwieństwo twierdzenia Berge'a: G ma dopasowanie większe niż M wtedy i tylko wtedy, gdy G ma ścieżkę zwiększającą. Oczywiste jest, że rozszerzająca się ścieżka P z G może być użyta do stworzenia pasującego M′, które jest większe niż M — po prostu weź M′ jako różnicę symetryczną P i M ( M ′ zawiera dokładnie te krawędzie G , które pojawiają się dokładnie w jednym z P i M ). Stąd kierunek odwrotny.

Dla kierunku do przodu niech M′ będzie dopasowaniem w G większym niż M . Rozważmy D , symetryczną różnicę M i M′ . Zauważ, że D składa się ze ścieżek, a nawet cykli (jak zaobserwowano we wcześniejszym lemacie). Ponieważ M′ jest większe niż M , D zawiera składnik, który ma więcej krawędzi od M′ niż M . Takim składnikiem jest ścieżka w G , która zaczyna się i kończy krawędzią z M′ , więc jest to ścieżka rozszerzająca.

Wnioski

Wniosek 1

Niech M będzie maksymalnym dopasowaniem i rozważmy naprzemienny łańcuch taki, że krawędzie na ścieżce zmieniają się między byciem i niebyciem w M . Jeśli łańcuch naprzemienny jest cyklem lub ścieżką o parzystej długości, rozpoczynającą się w niedopasowanym wierzchołku, to nowe pasujące maksimum M ′ można znaleźć, zamieniając krawędzie znalezione w M , a nie w M . Na przykład, jeśli naprzemienny łańcuch to ( m ₁ , n ₁ , m ₂ , n ₂ , ...), gdzie m _i ∈ M i n _i ∉ M , zamiana ich sprawi, że wszystkie n _{i będą} częścią nowego dopasowania i spraw, aby wszystkie m _i nie były częścią dopasowania.

Wniosek 2

Krawędź jest uważana za „swobodną”, jeśli należy do maksymalnego dopasowania, ale nie należy do wszystkich maksymalnych dopasowań. Krawędź e jest wolna wtedy i tylko wtedy, gdy w dowolnym maksimum pasującym M , krawędź e należy do parzystej naprzemiennej ścieżki rozpoczynającej się w niedopasowanym wierzchołku lub do naprzemiennego cyklu . Zgodnie z pierwszym wnioskiem, jeśli krawędź e jest częścią takiego naprzemiennego łańcucha, to musi istnieć nowe maksymalne dopasowanie, M′ , a e istniałoby albo w M , albo w M′ , a zatem byłoby wolne. I odwrotnie, jeśli krawędź e jest swobodna, to e znajduje się w pewnym pasującym maksimum M , ale nie w M′ . Ponieważ e nie jest częścią zarówno M, jak i M′ , musi nadal istnieć po uwzględnieniu symetrycznej różnicy M i M ′ . Symetryczna różnica M i M ′ skutkuje grafem składającym się z izolowanych wierzchołków, nawet naprzemiennych cykli i naprzemiennych ścieżek. Załóżmy przeciwnie, że e należy do jakiejś składowej ścieżki o nieparzystej długości. Ale wtedy jedno z M i M ′ musi mieć o jedną krawędź mniej niż inne w tym komponencie, co oznacza, że komponent jako całość jest ścieżką rozszerzającą w odniesieniu do tego dopasowania. Zatem zgodnie z pierwotnym lematem to dopasowanie (czy to M , czy M′ ) nie może być dopasowaniem maksymalnym, co jest sprzeczne z założeniem, że zarówno M , jak i M′ są maksymalne. Tak więc, ponieważ e nie może należeć do żadnej składowej ścieżki o nieparzystej długości, musi albo znajdować się w zmiennym cyklu, albo naprzemiennej ścieżce o parzystej długości.

Berge, Claude (15 września 1957), „Dwa twierdzenia w teorii grafów” (PDF) , Proceedings of the National Academy of Sciences of the United States of America , 43 (9): 842–844, Bibcode : 1957PNAS ... 43..842B , doi : 10.1073/pnas.43.9.842 , PMC 534337 , PMID 16590096 .
West, Douglas B. (2001), Wprowadzenie do teorii grafów (wyd. 2), Pearson Education, Inc., s. 109–110, ISBN 81-7808-830-4 .
Berge, Claude (1973), Wykresy i hipergrafy , North-Holland Publishing Company, s. 122–125, ISBN 0-444-10399-6 .