Tatta-Bergen kaava

Tutt-Bergen kaava on graafiteoreettinen kaava, joka määrittää kaavion suurimman vastaavuuden koon . On yleistys Tuttin sovituslauseesta ; perusti ja todisti Claude Berg .

Lauseen mukaan graafin suurimman vastaavuuden koko on: $G=(V,E)$

{\frac {1}{2}}\min _{U\subseteq V}\left(|U|-\operaattorinimi {pariton} (GU)+|V|\oikea)

missä on niiden graafin yhdistettyjen komponenttien lukumäärä, joissa on pariton määrä pisteitä. ${\näyttötyyli \operaattorin nimi {pariton} (H)}$ $H$

Selitys

On intuitiivisesti selvää, että minkä tahansa kärkien osajoukon kohdalla ainoa tapa peittää komponentti , jossa on pariton määrä pisteitä, on valita sovituksesta reuna, joka yhdistää yhden kärjen kanssa . Jos komponentilla, jolla on pariton määrä pisteitä, ei ole vastaavaa reunaa sovituksessa, osa sovituksesta peittää komponentin kärjet, mutta koska pistemäärä on pariton, vähintään yksi kärki jää peittämättä. Näin ollen, jos jokin kärkien osajoukko on pienikokoinen, mutta kun se poistetaan, syntyy suuri määrä parittomia komponentteja, niin monia pisteitä ei kata sovitus, mikä tarkoittaa, että yhteensopivuus on pieni. Tämä perustelu voidaan tehdä ankaraksi, jos otamme huomioon, että suurimman vastaavuuden koko ei ylitä Tutt-Bergen kaavan antamaa arvoa. $U$ $GU$ $GU$ $U$ $U$

Kaava osoittaa, että tämä rajoitus on ainoa este suuremman sovituksen saavuttamiselle — optimaalisen sovituksen koon määrää se osajoukko , jolla on suurin ero parittomien komponenttien lukumäärän ulkopuolella ja sisällä olevien kärkien välillä . Toisin sanoen aina on olemassa tarkka osajoukko , jonka poistaminen tuottaa oikean määrän parittomia komponentteja, jotka täyttävät kaavan. Eräs tapa saada tällainen joukko on valita mikä tahansa suurin sovitus ja sisällyttää se pisteisiin, joita sovitus ei kata tai jotka voidaan saavuttaa peittämättömästä kärjestä vuorotellen [1] , joka päättyy sovituksen reunaan. Kun se on määritelty joukoksi pisteitä, jotka yhdistetään sovittamalla pisteistä osoitteesta , käy ilmi, että kahta kärkeä kohteesta ei voi olla vierekkäin, muuten on mahdollista yhdistää kaksi peittämätöntä kärkeä vuorotellen, mikä on ristiriidassa maksimaalisuuden kanssa [2] . Minkä tahansa pisteen naapurin osoitteesta täytyy kuulua ryhmään , muuten voimme pidentää vuorottelevaa polkua parilla reunalla naapureihin, jolloin naapurit tulevat osaksi . Siten , mikä tahansa kärki muodostaa yhden kärjen komponentin, eli sillä on pariton määrä pisteitä. Muita parittomia komponentteja ei voi olla, koska kaikki muut kärjet pysyvät täsmäävinä :n poistamisen jälkeen . $U$ $U$ $U$ $U$ $U$ $M$ $X$ $M$ $U$ $M$ $X$ $X$ $M$ $x$ $X$ $U$ $x$ $U$ $GU$ $X$ $U$

Yhteys Tuttin lauseeseen

Tuttin sovituslause kuvaa täydellisesti täsmäävät graafit graafeiksi, joille minkä tahansa kärkien osajoukon poistaminen tuottaa maksimissaan parittomat komponentit. ( Tyhjänä joukkona löytyy aina osajoukko , joka sisältää vähintään parittomat komponentit ). Tässä tapauksessa Tatta-Bergen kaavan mukaan sovituksen koko on /2. Toisin sanoen suurin yhteensopivuus on täydellinen ja Tuttin lause voidaan saada Tutt-Bergen kaavan seurauksena, ja itse kaavaa voidaan pitää Tuttin lauseen yleistyksenä. $U$ $|U|$ $U$ $|U|$ $|V|$

Muistiinpanot

↑ Vaihtoehtoinen polku on polku, jossa sovitun reunan reunat vuorottelevat eivätkä sisälly sovitukseen ( Berge 1962 , s. 186 Vuorottelevien ketjujen teoria)
↑ Lause: Graafisovitus on suurin silloin ja vain silloin, kun kahta erilaista sovittamatonta kärkeä yhdistävää polkua ei ole. ( Berge 1962 , s. 195)

Kirjallisuus

C. Berge Graafisten teoria. - Methuen, 1962.Reprint Dover Publications, 2001.
C. Berge. Graafiteoria ja sen soveltaminen. - Moskova: Ulkomaisen kirjallisuuden kustantaja, 1962.
JA Bondy, USR Murty. Graafiteoria: syventävä kurssi. - Springer-Verlag , 2007. - S. 428. - (Matematiikan tutkinnon tekstit). — ISBN 1-84628-969-6 .
JA Bondy, USR Murty. Harjoitus 5.3.4, s. 80 // Graafiteoria sovelluksilla . - New York: North Holland, 1976. - ISBN 0-444-19451-7 . Arkistoitu 13. huhtikuuta 2010 Wayback Machinessa
Richard A. Brualdi. kombinatoriset matriisiluokat. - Cambridge: Cambridge University Press , 2006. - V. 108. - S. 360. - (Encyclopedia of Mathematics and Its Applications). — ISBN 0-521-86565-4 .
László Lovász , MD Plummer. Vastaamisen teoria. - Amsterdam: Pohjois-Hollanti, 1986. - S. 90-91. - ISBN 0-444-87916-1 .
Alexander Schrijver . Kombinatorinen optimointi: polyhedra ja tehokkuus. - Springer-Verlag , 2003. - S. 413. - ISBN 3-540-44389-4 .

Linkit

C. Berge Sur le couplage maximum d'un graphe //Comptes rendus hebdomadaires des séances de l'Académie des sciences. - 1958. -T. 247. -S. 258-259.
WT Tutte . Lineaaristen kaavioiden tekijät // The Journal of the London Mathematical Society, Ser. 1. - 1947. - T. 22 . - S. 107-111 . - doi : 10.1112/jlms/s1-22.2.107 .