Vzorec Tatta-Berge

Tutt-Bergeův vzorec je graf-teoretický vzorec, který určuje velikost největší shody v grafu . Je zobecněním Tuttovy věty o shodě ; založil a dokázal Claude Berg .

Věta říká, že velikost největší shody v grafu je: $G=(V,E)$

{\frac {1}{2}}\min _{U\subseteq V}\left(|U|-\jméno operátora {odd} (GU)+|V|\right)

kde je počet spojených složek grafu s lichým počtem vrcholů. $\operatorname {odd} (H)$ $H$

Vysvětlení

Je intuitivně jasné, že pro jakoukoli podmnožinu vrcholů je jediným způsobem, jak úplně pokrýt komponentu s lichým počtem vrcholů, vybrat v párování hranu, která spojuje jeden z vrcholů s . Pokud komponenta s lichým počtem vrcholů nemá při párování žádnou takovou hranu, část párování pokryje vrcholy komponenty, ale protože je počet vrcholů lichý, zůstane alespoň jeden vrchol nepokrytý. Pokud tedy některá podmnožina vrcholů má malou velikost, ale když je odstraněna, vytvoří se velké množství lichých složek, pak bude mnoho vrcholů, které shoda nepokryje, což znamená, že shoda bude také malá. Tato úvaha může být rigorózní, vezmeme-li v úvahu, že velikost největší shody nepřesahuje hodnotu danou Tutt-Bergeovým vzorcem. $U$ $GU$ $GU$ $U$ $U$

Vzorec ukazuje, že toto omezení je jedinou překážkou pro získání větší shody — velikost optimální shody je určena podmnožinou , která má největší rozdíl mezi počtem lichých složek vně a vrcholy uvnitř . To znamená, že vždy existuje přesná podmnožina, jejíž odstranění vytvoří správný počet lichých složek, které splňují vzorec. Jedním ze způsobů, jak získat takovou množinu, je vybrat libovolnou největší shodu a zahrnout ji do vrcholů, které buď nejsou pokryty shodou, nebo se k nim lze dostat z nepokrytého vrcholu střídavou cestou [1] , která končí hranou ze shody. Po definování jako množiny vrcholů, které jsou spojeny párováním s vrcholy z , se ukazuje, že žádné dva vrcholy z nemohou sousedit, jinak je možné spojit dva nepokryté vrcholy střídavě, což odporuje maximálnosti [2] . Každý soused vrcholu z musí patřit do , jinak můžeme prodloužit střídavou cestu do o pár hran k sousedům, což způsobí, že se sousedé stanou součástí . Tedy v , libovolný vrchol tvoří součást jednoho vrcholu, to znamená, že má lichý počet vrcholů. Nemohou existovat žádné další liché komponenty, protože všechny ostatní vrcholy zůstanou po odstranění . $U$ $U$ $U$ $U$ $U$ $M$ $X$ $M$ $U$ $M$ $X$ $X$ $M$ $X$ $X$ $U$ $X$ $U$ $GU$ $X$ $U$

Souvislost s Tuttovou větou

Tuttův párovací teorém popisuje grafy s dokonalými párováními jako grafy, pro které odstranění jakékoli podmnožiny vrcholů vytváří maximum lichých složek. (Podmnožinu , která obsahuje alespoň liché komponenty, lze vždy nalézt jako prázdnou množinu ). V tomto případě je podle vzorce Tatta-Berge velikost párování /2. To znamená, že největší shoda je dokonalá a Tuttův teorém lze získat jako důsledek Tutt-Bergeho vzorce a samotný vzorec lze považovat za zobecnění Tuttova teorému. $U$ $|U|$ $U$ $|U|$ $|V|$

Poznámky

↑ Střídavá cesta je cesta, ve které se hrany ze shody střídají a nejsou zahrnuty do shody ( Berge 1962 , s. 186 Teorie alternujících řetězců)
↑ Věta: Shoda grafu je největší právě tehdy, když neexistuje žádná střídavá cesta spojující dva různé neshodné vrcholy. ( Berge 1962 , s. 195)

Literatura

C. Berge Teorie grafů. — Methuen, 1962.Reprint Dover Publications, 2001.
C. Berge. Teorie grafů a její aplikace. - Moskva: Nakladatelství zahraniční literatury, 1962.
JA Bondy, USR Murty. Teorie grafů: pokročilý kurz. - Springer-Verlag , 2007. - S. 428. - (Absolventské texty z matematiky). — ISBN 1-84628-969-6 .
JA Bondy, USR Murty. Cvičení 5.3.4, str. 80 // Teorie grafů s aplikacemi . - New York: Severní Holandsko, 1976. - ISBN 0-444-19451-7 . Archivováno 13. dubna 2010 na Wayback Machine
Richard A. Brualdi. kombinatorické maticové třídy. - Cambridge: Cambridge University Press , 2006. - V. 108. - S. 360. - (Encyklopedie matematiky a její aplikace). — ISBN 0-521-86565-4 .
László Lovász , MUDr. Plummer. Teorie shody. - Amsterdam: North-Holland, 1986. - S. 90-91. - ISBN 0-444-87916-1 .
Alexander Schrijver . Kombinatorická optimalizace: mnohostěny a účinnost. - Springer-Verlag , 2003. - S. 413. - ISBN 3-540-44389-4 .

Odkazy

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 . Faktorizace lineárních grafů // The Journal of the London Mathematical Society, Ser. 1. - 1947. - T. 22 . - S. 107-111 . - doi : 10.1112/jlms/s1-22.2.107 .