Tatta-Berge formel

Tutt-Berge formlen  er en grafteoretisk formel, der bestemmer størrelsen af ​​den største match i en graf . Er en generalisering af Tutts matchende teorem ; etableret og bevist af Claude Berg .

Sætningen siger, at størrelsen af ​​den største match i en graf er:

,

hvor  er antallet af forbundne komponenter i grafen med et ulige antal hjørner.

Forklaring

Det er intuitivt klart, at for enhver delmængde af toppunkter er den eneste måde at dække en komponent fuldstændigt med et ulige antal hjørner ved at vælge en kant i matchningen, der forbinder et af hjørnerne med . Hvis en komponent med et ulige antal hjørner ikke har en sådan kant i matchningen, vil en del af matchningen dække komponentens hjørner, men da antallet af toppunkter er ulige, vil mindst ét ​​toppunkt forblive afdækket. Således, hvis en delmængde af toppunkter har en lille størrelse, men når den fjernes, skabes et stort antal ulige komponenter, så vil der være mange hjørner, der ikke er dækket af matchningen, hvilket indebærer, at matchningen vil være lille. Denne begrundelse kan gøres streng, hvis vi tager i betragtning, at størrelsen af ​​den største matchning ikke overstiger værdien givet af Tutt-Berge-formlen.

Formlen viser, at denne begrænsning er den eneste hindring for at opnå en større matchning - størrelsen af ​​den optimale matchning bestemmes af den delmængde , der har den største forskel mellem antallet af ulige komponenter udenfor og hjørner indeni . Det vil sige, at der altid er en nøjagtig delmængde , hvis fjernelse producerer det korrekte antal ulige komponenter, der opfylder formlen. En måde at få et sådant sæt  på er at vælge en hvilken som helst største matchning og inkludere den i toppunkter, der enten ikke er dækket af matchningen eller kan nås fra et udækket toppunkt af en vekslende sti [1] , der ender med en kant fra matchningen. Efter at have defineret som det sæt af toppunkter, der er forbundet ved at matche med toppunkter fra , viser det sig, at ikke to toppunkter fra kan være tilstødende, ellers er det muligt at forbinde to udækkede toppunkter på en vekslende måde, hvilket modsiger maksimaliteten [2] . Enhver nabo til et toppunkt fra skal tilhøre , ellers kan vi forlænge vekselvejen til med et par kanter til naboerne, hvilket gør at naboerne bliver en del af . I , danner et hvilket som helst toppunkt således en komponent af et toppunkt, det vil sige, at det har et ulige antal hjørner. Der kan ikke være andre ulige komponenter, da alle andre hjørner forbliver matchede efter fjernelse af .

Forbindelse med Tutts sætning

Tutts matchende sætning beskriver grafer med perfekte matchninger som grafer, for hvilke fjernelse af en hvilken som helst delmængde af hjørner giver maksimalt ulige komponenter. (En delmængde , der indeholder mindst ulige komponenter, kan altid findes som det tomme sæt ). I dette tilfælde, ifølge Tatta-Berge-formlen, er størrelsen af ​​matchningen /2. Det vil sige, at den største matchning er perfekt, og Tutts sætning kan opnås som en konsekvens af Tutt-Berge formlen, og selve formlen kan betragtes som en generalisering af Tutts sætning.

Noter

  1. ↑ En alternerende sti er en sti, hvor kanter fra en matchende veksler og ikke er inkluderet i matchningen ( Berge 1962 , s. 186 Theory of alternating chains)
  2. ↑ Sætning: En grafmatchning er størst, hvis og kun hvis der ikke er en vekslende sti, der forbinder to forskellige umatchede hjørner. ( Berge 1962 , s. 195)

Litteratur

Links