Formula Tatta-Berge

Formula Tutt-Berge este o formulă teoretică a graficului care determină dimensiunea celei mai mari potriviri dintr-un grafic . Este o generalizare a teoremei de potrivire a lui Tutt ; stabilit și dovedit de Claude Berg .

Teorema afirmă că dimensiunea celei mai mari potriviri dintr-un grafic este: $G=(V,E)$

{\frac {1}{2}}\min _{U\subseteq V}\left(|U|-\operatorname {impar} (GU)+|V|\right)

unde este numărul de componente conectate ale graficului având un număr impar de vârfuri. $\operatorname {impar} (H)$ $H$

Explicație

Este intuitiv clar că pentru orice subset de vârfuri , singura modalitate de a acoperi complet o componentă cu un număr impar de vârfuri este de a selecta o muchie în potrivirea care conectează unul dintre vârfuri cu . Dacă o componentă cu un număr impar de vârfuri nu are o astfel de muchie în potrivire, o parte din potrivire va acoperi vârfurile componentei, dar deoarece numărul de vârfuri este impar, cel puțin un vârf va rămâne neacoperit. Astfel, dacă un subset de vârfuri are o dimensiune mică, dar când este eliminat, se creează un număr mare de componente impare, atunci vor exista multe vârfuri care nu sunt acoperite de potrivire, ceea ce implică că potrivirea va fi mică. Acest raționament poate fi riguros dacă ținem cont de faptul că dimensiunea celei mai mari potriviri nu depășește valoarea dată de formula Tutt-Berge. $U$ $GU$ $GU$ $U$ $U$

Formula arată că această restricție este singurul obstacol în calea obținerii unei potriviri mai mari — dimensiunea potrivirii optime este determinată de submulțimea care are cea mai mare diferență între numărul de componente impare din exterior și vârfurile din interior . Adică, există întotdeauna un subset exact a cărui eliminare produce numărul corect de componente impare care satisfac formula. O modalitate de a obține un astfel de set este să alegeți orice potrivire cea mai mare și să o includeți în vârfuri care fie nu sunt acoperite de potrivire, fie care pot fi atinse de la un vârf neacoperit printr-o cale alternativă [1] care se termină cu o margine din potrivire. După ce am definit ca mulțime de vârfuri care sunt conectate prin potrivire cu vârfuri din , rezultă că două vârfuri din nu pot fi adiacente, altfel este posibil să se conecteze două vârfuri neacoperite în mod alternativ, ceea ce contrazice maximalitatea [2] . Orice vecin al unui vârf de la trebuie să aparțină lui , altfel putem extinde calea alternativă cu o pereche de muchii către vecini, ceea ce face ca vecinii să devină parte din . Astfel, în , orice vârf formează o componentă a unui vârf, adică are un număr impar de vârfuri. Nu pot exista alte componente impare, deoarece toate celelalte vârfuri rămân potrivite după eliminarea . $U$ $U$ $U$ $U$ $U$ $M$ $X$ $M$ $U$ $M$ $X$ $X$ $M$ $X$ $X$ $U$ $X$ $U$ $GU$ $X$ $U$

Legătura cu teorema lui Tutt

Teorema de potrivire a lui Tutt descrie graficele cu potriviri perfecte ca fiind grafice pentru care eliminarea oricărui subset de vârfuri produce un maxim de componente impare. (Un subset care conține cel puțin componente impare poate fi întotdeauna găsit ca un set gol ). În acest caz, conform formulei Tatta-Berge, dimensiunea potrivirii este /2. Adică, cea mai mare potrivire este perfectă și teorema lui Tutt poate fi obținută ca o consecință a formulei Tutt-Berge, iar formula în sine poate fi considerată ca o generalizare a teoremei lui Tutt. $U$ $|U|$ $U$ $|U|$ $|V|$

Note

↑ O cale alternativă este o cale în care marginile dintr-o potrivire alternativă și nu sunt incluse în potrivire ( Berge 1962 , p. 186 Teoria lanțurilor alternante)
↑ Teorema: O potrivire grafică este cea mai mare dacă și numai dacă nu există o cale alternativă care să conecteze două vârfuri diferite nepotrivite. ( Berge 1962 , p. 195)

Literatură

C. Berge Teoria graficelor. — Methuen, 1962.Reprint Dover Publications, 2001.
C. Berge. Teoria grafurilor și aplicarea acesteia. - Moscova: Editura de literatură străină, 1962.
JA Bondy, USR Murty. Teoria grafurilor: un curs avansat. - Springer-Verlag , 2007. - P. 428. - (Texte de absolvire a matematicii). — ISBN 1-84628-969-6 .
JA Bondy, USR Murty. Exercițiul 5.3.4, p. 80 // Teoria graficelor cu aplicații . - New York: Olanda de Nord, 1976. - ISBN 0-444-19451-7 . Arhivat pe 13 aprilie 2010 la Wayback Machine
Richard A. Brualdi. clase de matrice combinatorii. - Cambridge: Cambridge University Press , 2006. - V. 108. - P. 360. - (Encyclopedia of Mathematics and Its Applications). — ISBN 0-521-86565-4 .
László Lovász , MD Plummer. Teoria potrivirii. - Amsterdam: Olanda de Nord, 1986. - S. 90-91. - ISBN 0-444-87916-1 .
Alexander Schrijver . Optimizare combinatorie: poliedre și eficiență. - Springer-Verlag , 2003. - P. 413. - ISBN 3-540-44389-4 .

Link -uri

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 . Factorizarea graficelor liniare // The Journal of the London Mathematical Society, Ser. 1. - 1947. - T. 22 . - S. 107-111 . - doi : 10.1112/jlms/s1-22.2.107 .