Berges sats

Den här artikeln handlar om teoremet i grafteori. För Berges maxsats, se Maximumsats .

I grafteorin säger Berges sats att en matchande M i en graf G är maximal (innehåller största möjliga antal kanter) om och endast om det inte finns någon förstärkningsbana ( en väg som börjar och slutar på fria (omatchade) hörn, och växlar mellan kanter i och inte i matchningen) med M .

Det bevisades av den franske matematikern Claude Berge 1957 (även om det redan observerats av Petersen 1891 och Kőnig 1931).

Bevis

För att bevisa Berges teorem behöver vi först ett lemma . Ta en graf G och låt M och M′ vara två matchningar i G . Låt G′ vara den resulterande grafen från att ta den symmetriska skillnaden mellan M och M′ ; dvs ( M - M' ) ∪ ( M' - M ). G′ kommer att bestå av anslutna komponenter som är något av följande:

1. En isolerad vertex .
2. En jämn cykel vars kanter växlar mellan M och M′ .
3. En bana vars kanter växlar mellan M och M′ , med distinkta ändpunkter.

Lemmat kan bevisas genom att observera att varje vertex i G′ kan falla in mot högst 2 kanter: en från M och en från M′ . Grafer där varje vertex har grad mindre än eller lika med 2 måste bestå av antingen isolerade hörn , cykler och banor . Dessutom måste varje stig och cykel i G′ växla mellan M och M′ . För att en cykel ska kunna göra detta måste den ha lika många kanter från M och M′ och därför ha jämn längd.

Låt oss nu bevisa motsatsen till Berges sats: G har en matchning som är större än M om och endast om G har en ökande väg. Uppenbarligen kan en förstärkningsbana P av G användas för att producera en matchande M′ som är större än M - ta bara M′ för att vara den symmetriska skillnaden mellan P och M ( M′ innehåller exakt de kanter av G som visas i exakt en av P och M ). Följaktligen följer den omvända riktningen.

För framåtriktningen, låt M′ vara en matchning i G större än M . Betrakta D , den symmetriska skillnaden mellan M och M′ . Observera att D består av stigar och jämna cykler (som observerats av det tidigare lemmat). Eftersom M′ är större än M , innehåller D en komponent som har fler kanter från M′ än M . En sådan komponent är en bana i G som börjar och slutar med en kant från M′ , så det är en förstärkande bana.

Följderna

Följd 1

Låt M vara en maximal matchning och betrakta en alternerande kedja så att kanterna i banan växlar mellan att vara och inte vara i M . Om den alternerande kedjan är en cykel eller en bana med jämn längd som börjar på en omatchad vertex, så kan en ny maximal matchande M′ hittas genom att byta kanter som finns i M och inte i M . Till exempel, om den alternerande kedjan är ( m ₁ , n ₁ , m ₂ , n ₂ , ...), där m _i ∈ M och n _i ∉ M , skulle byte av dem göra alla n _i en del av den nya matchningen och gör alla m _i inte en del av matchningen.

Följd 2

En kant anses vara "fri" om den tillhör en maximal matchning men inte tillhör alla maximala matchningar. En kant e är fri om och endast om, i en godtycklig maximal matchning M , kant e tillhör en jämn alternerande bana som börjar vid en omatchad vertex eller till en alternerande cykel . Av den första följden, om kanten e är en del av en sådan alternerande kedja, måste en ny maximal matchning, M' , existera och e skulle existera antingen i M eller M' , och därför vara fri. Omvänt, om kanten e är fri, så är e i någon maximal matchande M men inte i M′ . Eftersom e inte är en del av både M och M′ måste den fortfarande existera efter att ha tagit den symmetriska skillnaden mellan M och M′ . Den symmetriska skillnaden mellan M och M′ resulterar i en graf som består av isolerade hörn, till och med alternerande cykler och alternerande banor. Antag tvärtom att e tillhör någon vägkomponent med udda längd. Men då måste en av M och M′ ha en färre kant än den andra i den här komponenten, vilket betyder att komponenten som helhet är en förstärkande väg med avseende på den matchningen. Enligt det ursprungliga lemmat kan alltså matchning (oavsett om M eller M′ ) inte är en maximal matchning, vilket motsäger antagandet att både M och M′ är maximala. Så eftersom e inte kan tillhöra någon vägkomponent med udda längd, måste den antingen vara i en alternerande cykel eller en alternerande väg med jämn längd.

•    Berge, Claude (15 september 1957), "Two theorems in graph theory" (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), Introduction to Graph Theory (2nd ed.), Pearson Education, Inc., s. 109–110, ISBN 81-7808-830-4 .
•   Berge, Claude (1973), Graphs and Hypergraphs , North-Holland Publishing Company, s. 122–125, ISBN 0-444-10399-6 .