Tatta-Berge formula

A Tutt-Berge képlet egy gráfelméleti képlet, amely meghatározza a legnagyobb egyezés méretét egy gráfban . Tutt illesztési tételének általánosítása ; megállapította és bebizonyította Claude Berg .

A tétel kimondja, hogy a legnagyobb egyezés mérete egy gráfban : $G=(V,E)$

{\frac {1}{2}}\min _{U\subseteq V}\left(|U|-\operátornév {páratlan} (GU)+|V|\right)

ahol a páratlan számú csúcsú gráf összekapcsolt komponenseinek száma. ${\megjelenítési stílus \operátornév {páratlan} (H)}$ $H$

Magyarázat

Intuitív módon világos , hogy a csúcsok bármely részhalmaza esetén az egyetlen módja annak , hogy teljesen lefedjünk egy páratlan számú csúcsot tartalmazó komponenst , ha kiválasztunk egy élt az illesztésben , amely összeköti az egyik csúcsot a - vel . Ha egy páratlan számú csúcsú komponensnek nincs ilyen éle az illesztésben, akkor az illesztés egy része lefedi a komponens csúcsait, de mivel a csúcsok száma páratlan, legalább egy csúcs fedetlen marad. Így, ha a csúcsok egy részhalmaza kicsi, de eltávolításakor nagyszámú páratlan komponens jön létre, akkor sok olyan csúcs lesz, amelyet az illesztés nem fed le, ami azt jelenti, hogy az illesztés kicsi lesz. Ez az érvelés szigorúbbá tehető, ha figyelembe vesszük, hogy a legnagyobb egyezés mérete nem haladja meg a Tutt-Berge képlet által megadott értéket. $U$ $GU$ $GU$ $U$ $U$

A képlet azt mutatja, hogy ez a korlátozás az egyetlen akadálya a nagyobb illesztés elérésének – az optimális illesztés méretét az a részhalmaz határozza meg , amelyiknek a legnagyobb különbsége van a külső és a belső csúcsok páratlan komponensei között . Vagyis mindig van egy pontos részhalmaz, amelynek eltávolítása megfelelő számú páratlan komponenst eredményez, amelyek kielégítik a képletet. Egy ilyen halmaz megszerzésének egyik módja, ha kiválasztunk egy tetszőleges legnagyobb illesztést , és olyan csúcsokba foglaljuk, amelyeket vagy nem fed le az illesztés, vagy amelyek egy fedetlen csúcsból elérhetők egy váltakozó úton [1] , amely az illesztésből származó éllel végződik. A -ból származó csúcsokkal való illesztéssel összekapcsolt csúcsok halmazaként definiálva kiderül, hogy nem lehet szomszédos két csúcs -ból, ellenkező esetben lehetséges két fedetlen csúcsot váltakozó módon összekapcsolni, ami ellentmond a maximalitásnak [2] . Egy csúcs bármely szomszédjának a -ból kell tartoznia , különben kiterjeszthetjük a váltakozó útvonalat egy pár éllel a szomszédokhoz, ami azt eredményezi, hogy a szomszédok részévé válnak . Így -ben bármely csúcs egy csúcs komponensét alkotja, vagyis páratlan számú csúcsa van. Nem lehet más páratlan komponens, mivel az összes többi csúcs illeszkedve marad a eltávolítása után . $U$ $U$ $U$ $U$ $U$ $M$ $x$ $M$ $U$ $M$ $x$ $x$ $M$ $x$ $x$ $U$ $x$ $U$ $GU$ $x$ $U$

Összefüggés Tutt tételével

Tutt illesztési tétele a tökéletes illeszkedéssel rendelkező gráfokat olyan gráfokként írja le , amelyeknél a csúcsok bármely részhalmazának eltávolítása legfeljebb páratlan komponenseket eredményez. (A legalább páratlan komponenseket tartalmazó részhalmaz mindig üres halmazként található meg ). Ebben az esetben a Tatta-Berge képlet szerint az illesztés nagysága /2. Vagyis a legnagyobb egyezés tökéletes, és a Tutt-tétel a Tutt-Berge formula következményeként megkapható, maga a formula pedig a Tutt-tétel általánosításának tekinthető. $U$ $|U|$ $U$ $|U|$ $|V|$

Jegyzetek

↑ Az alternáló út egy olyan út, amelyben az illeszkedő élei váltakoznak, és nem szerepelnek az illesztésben ( Berge 1962 , 186. o. Az alternáló láncok elmélete)
↑ Tétel: Egy gráfillesztés akkor és csak akkor a legnagyobb, ha nincs váltakozó út, amely két különböző párosítatlan csúcsot köt össze. ( Berge 1962 , 195. o.)

Irodalom

C. Berge A gráfok elmélete. – Methuen, 1962.Reprint Dover Publications, 2001.
C. Berge. Gráfelmélet és alkalmazása. - Moszkva: Külföldi Irodalmi Kiadó, 1962.
JA Bondy, USR Murty. Gráfelmélet: haladó tanfolyam. - Springer-Verlag , 2007. - P. 428. - (Matematika diplomás szövegei). — ISBN 1-84628-969-6 .
JA Bondy, USR Murty. 5.3.4. gyakorlat, p. 80 // Gráfelmélet alkalmazásokkal . - New York: North Holland, 1976. - ISBN 0-444-19451-7 . Archiválva : 2010. április 13. a Wayback Machine -nél
Richard A. Brualdi. kombinatorikus mátrix osztályok. - Cambridge: Cambridge University Press , 2006. - V. 108. - P. 360. - (Encyclopedia of Mathematics and Its Applications). — ISBN 0-521-86565-4 .
Lovász László , MD Plummer. Párosítási elmélet. - Amszterdam: Észak-Holland, 1986. - S. 90-91. - ISBN 0-444-87916-1 .
Alexander Schrijver . Kombinatorikus optimalizálás: poliéder és hatékonyság. - Springer-Verlag , 2003. - P. 413. - ISBN 3-540-44389-4 .

Linkek

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 . A lineáris gráfok faktorizálása // The Journal of the London Mathematical Society, Ser. 1. - 1947. - T. 22 . - S. 107-111 . - doi : 10.1112/jlms/s1-22.2.107 .