Lema lui Berge

Lema lui Berge afirmă că o potrivire M într-un grafic G este cea mai mare (conține cel mai mare număr posibil de muchii) dacă și numai dacă nu există o cale complementară (o cale care începe și se termină pe liber, adică nu aparține potrivirilor, vârfuri și trece alternativ prin muchiile care se potrivesc și care nu se potrivesc) în M ​​.

Lema a fost demonstrată de matematicianul francez Claude Berge în 1957 (deși fusese deja discutată de Petersen în 1891 și König în 1931).

Dovada

Pentru a demonstra lema lui Berge, avem nevoie mai întâi de o altă lemă . Luați un grafic G și să fie M și M′ două potriviri în G . Fie G′ rezultatul luării diferenței simetrice a lui M și M′ . Adică . G′ va consta din componente care aparțin următoarelor grupe:

  1. Top izolat .
  2. Un ciclu par ale cărui muchii aparțin alternativ lui M și M′ .
  3. O cale cu capete distincte ale căror margini aparțin alternativ lui M și M′ .

Lema poate fi demonstrată notând că orice vârf din G poate fi incident la cel mult două muchii, una de la M și una de la M . Graficele în care orice vârf are gradul cel mult 2 trebuie să fie formate din vârfuri izolate , cicluri și căi . Mai mult, fiecare cale și ciclu din G trebuie să fie conținute în M ​​și M la rândul lor . Pentru ca un ciclu să se comporte astfel, trebuie să aibă un număr egal de muchii de la M și M și, prin urmare, o lungime egală.

Acum putem demonstra Lema lui Berge prin contradicție - un grafic G are o potrivire mai mare decât M dacă și numai dacă G are o cale complementară. Este clar că calea complementară P a graficului G poate fi folosită pentru a obține o potrivire M′ care este mai mare decât potrivirea M - doar luați ca M′ diferența simetrică a căilor P și M ( M′ constă exact din acelea muchii ale graficului G care apar exact o dată în traseul P , sau în potrivirea M ). De aici rezultă dovada în sens invers.

Pentru demonstrația directă, fie M′ o potrivire a graficului G care este mai mare decât potrivirea M . Se consideră D diferența simetrică a lui M și M′ . Rețineți că D constă din căi și chiar cicluri (după cum s-a menționat în lema anterioară ). Deoarece M′ este mai mare decât M , D conține o componentă care are mai multe muchii din M′ decât din M . O astfel de componentă este o cale în G care începe și se termină cu o muchie în M ​​, deci este complementară.

Consecințele

Corolarul 1

Fie M cea mai mare potrivire și luați în considerare un lanț alternant astfel încât marginile din cale să alterneze între aparținând și nu aparținând lui M . Dacă calea alternativă este un ciclu sau o cale de lungime uniformă, atunci noua cea mai mare potrivire M′ poate fi găsită prin schimbul de muchii între M și nu din M . De exemplu, dacă lanțul alternativ este , unde și . Schimbarea acestor margini va face ca toate n i să facă parte din noua potrivire, iar toate m i nu vor fi incluse în potrivire.

Consecința 2

O margine este considerată „liberă” dacă aparține celei mai mari potriviri, dar nu și tuturor celor mai mari potriviri. O muchie e este liberă dacă și numai dacă, într-o potrivire M arbitrară cea mai mare, muchia e aparține unui drum alternant par care începe la un vârf neacoperit sau aparține unui ciclu alternant . După primul corolar, dacă marginea e face parte dintr-un astfel de lanț alternant, atunci trebuie să existe o nouă mai mare potrivire M și e va aparține fie lui M , fie lui M și, prin urmare, este liber. Dimpotrivă, dacă muchia e este liberă, atunci e se află în M , dar nu în M′ . Deoarece muchia e nu aparține atât lui M cât și M′ , ea trebuie să fie prezentă în diferența simetrică a lui M și M′ . Diferența simetrică dintre M și M′ oferă un grafic format din vârfuri izolate, chiar cicluri alternante și chiar trasee alternante de lungime. Să presupunem că acesta nu este cazul și că e aparține unei căi de lungime impară. Dar atunci una dintre potrivirile M sau M′ trebuie să aibă mai puține muchii în această componentă, ceea ce înseamnă că această componentă în ansamblu este o cale complementară pentru această potrivire. După lema originală, atunci această potrivire ( M sau M ) nu poate fi cea mai mare, ceea ce contrazice presupunerea că atât M , cât și M sunt cele mai mari potriviri. Astfel, deoarece e nu poate aparține niciunei componente de cale de lungime impară, trebuie să fie fie într-un ciclu de lungime pară, fie pe o cale alternativă de lungime pară.

Note

Literatură