Tatta-Berge formel

Tutt-Berge- formeln  är en grafteoretisk formel som bestämmer storleken på den största matchningen i en graf . Är en generalisering av Tutts matchningssats ; etablerad och bevisad av Claude Berg .

Teoremet säger att storleken på den största matchningen i en graf är:

,

där  är antalet anslutna komponenter i grafen som har ett udda antal hörn.

Förklaring

Det är intuitivt tydligt att för varje delmängd av hörn är det enda sättet att helt täcka en komponent med ett udda antal hörn att välja en kant i matchningen som förbinder en av hörnen med . Om en komponent med ett udda antal hörn inte har någon sådan kant i matchningen, kommer en del av matchningen att täcka komponentens hörn, men eftersom antalet hörn är udda kommer åtminstone en vertex att förbli avtäckt. Således, om någon delmängd av hörn har en liten storlek, men när den tas bort skapas ett stort antal udda komponenter, kommer det att finnas många hörn som inte täcks av matchningen, vilket innebär att matchningen kommer att vara liten. Detta resonemang kan göras rigoröst om vi tar hänsyn till att storleken på den största matchningen inte överstiger värdet som ges av Tutt-Berge-formeln.

Formeln visar att denna begränsning är det enda hindret för att få en större matchning – storleken på den optimala matchningen bestäms av den delmängd som har störst skillnad mellan antalet udda komponenter utanför och hörn inuti . Det vill säga, det finns alltid en exakt delmängd vars borttagning ger rätt antal udda komponenter som uppfyller formeln. Ett sätt att få en sådan uppsättning  är att välja vilken som helst största matchning och inkludera den i hörn som antingen inte täcks av matchningen eller som kan nås från en avtäckt vertex med en alternerande bana [1] som slutar med en kant från matchningen. Efter att ha definierat som uppsättningen av hörn som är sammankopplade genom att matcha med hörn från , visar det sig att inga två hörn från kan vara intilliggande, annars är det möjligt att koppla ihop två otäckta hörn på ett alternerande sätt, vilket motsäger maximaliteten [2] . Valfri granne till en vertex från måste tillhöra , annars kan vi förlänga växelvägen till med ett par kanter till grannarna, vilket gör att grannarna blir en del av . Alltså, i , bildar vilken vertex som helst en komponent av en vertex, det vill säga den har ett udda antal hörn. Det kan inte finnas några andra udda komponenter eftersom alla andra hörn förblir matchade efter borttagningen av .

Samband med Tutts teorem

Tutts matchningssats beskriver grafer med perfekta matchningar som grafer för vilka borttagningen av någon delmängd av hörn ger maximalt udda komponenter. (En delmängd som innehåller åtminstone udda komponenter kan alltid hittas som den tomma uppsättningen ). I det här fallet, enligt Tatta-Berges formel, är storleken på matchningen /2. Det vill säga att den största matchningen är perfekt och Tutts sats kan erhållas som en konsekvens av Tutt-Berges formel, och själva formeln kan betraktas som en generalisering av Tutts sats.

Anteckningar

  1. ↑ En alternerande bana är en bana där kanter från en matchande alternerar och inte ingår i matchningen ( Berge 1962 , s. 186 Theory of alternating chains)
  2. ↑ Sats: En grafmatchning är störst om och endast om det inte finns någon alternerande väg som förbinder två olika omatchade hörn. ( Berge 1962 , s. 195)

Litteratur

Länkar