Bergen lemma

Bergen lemmassa todetaan, että yhteensopiva M graafissa G on suurin (sisältää suurimman mahdollisen määrän reunoja) silloin ja vain, jos ei ole komplementaarista polkua (polku, joka alkaa ja päättyy vapaalle, eli ei kuulu sovituksiin, kärjet ja kulkee vuorotellen yhteensopivien ja ei-sopivien reunojen läpi) M -muodossa .

Lemman todisti ranskalainen matemaatikko Claude Berge vuonna 1957 (vaikka Petersen olivat jo käsitelleet sitä vuonna 1891 ja König vuonna 1931).

Todiste

Bergen lemman todistamiseksi tarvitsemme ensin toisen lemman . Otetaan kuvaaja G ja olkoon M ja M′ kaksi yhteensopivuutta G :ssä . Olkoon G′ tulos ottamalla M :n ja M′ :n symmetrinen ero . Se on . G′ koostuu komponenteista, jotka kuuluvat seuraaviin ryhmiin:

  1. Eristetty toppi .
  2. Parillinen sykli , jonka reunat kuuluvat vuorotellen M :ään ja M′ .
  3. Polku , jolla on erilliset päätepisteet, joiden reunat vuorotellen kuuluvat M :ään ja M′ .

Lemma voidaan todistaa toteamalla, että mikä tahansa G : n kärki voi osua korkeintaan kahteen reunaan, yksi M :stä ja toinen M :stä . Kuvaajat , joissa minkä tahansa kärjen aste on enintään 2 , on koostuttava eristetyistä pisteistä , sykleistä ja poluista . Lisäksi jokaisen polun ja syklin G :ssä tulee sisältyä vuorotellen M :iin ja M :iin . Jotta sykli käyttäytyisi tällä tavalla, sillä on oltava yhtä monta reunaa M :stä ja M :stä ja siksi tasainen pituus.

Nyt voimme todistaa Bergen lemman ristiriitaisesti - kuvaajan G vastaavuus on suurempi kuin M , jos ja vain jos G :llä on komplementaarinen polku. On selvää, että graafin G komplementaarista polkua P voidaan käyttää sopivan M′:n saamiseksi , joka on suurempi kuin vastaava M ′ – ota M′ vain polkujen P ja M symmetrinen ero ( M′ koostuu täsmälleen niistä graafin G reunat, jotka esiintyvät täsmälleen kerran polulla P tai vastaavassa M ). Tästä seuraa todiste päinvastaiseen suuntaan.

Olkoon M′ graafin G täsmäytys , joka on suurempi kuin vastaava M . Tarkastellaan D :ksi M :n ja M′: n symmetristä eroa . Huomaa, että D koostuu poluista ja parillisista jaksoista (kuten aikaisemmassa lemassa todettiin ). Koska M′ on suurempi kuin M , D sisältää komponentin, jolla on enemmän reunoja M′: sta kuin M :sta . Tällainen komponentti on polku G :ssä , joka alkaa ja päättyy M :n reunaan , joten se on täydentävä.

Seuraukset

Seuraus 1

Olkoon M suurin yhteensopivuus ja harkitse vuorottelevaa ketjua siten, että polun reunat vuorottelevat M :ään kuuluvien ja kuulumattomien välillä . Jos vaihtuva polku on sykli tai parillisen pituinen polku , niin uusi suurin yhteensopivuus M′ voidaan löytää vaihtamalla reunat M:n välillä eikä M:n välillä . Jos esimerkiksi vaihtuva ketju on , missä ja . Näiden reunojen vaihtaminen tekee kaikista n i :stä uuden sovituksen, ja kaikkia m i :itä ei sisällytetä sovitukseen.

Seuraus 2

Reunaa pidetään "vapaana", jos se kuuluu suurimpaan vastaavuuteen, mutta ei kaikkiin suurimpiin vastaavuuksiin. Reuna e on vapaa silloin ja vain, jos mielivaltaisessa suurimmassa sovituksessa M , reuna e kuuluu parilliseen vuorottelevaan polkuun, joka alkaa peittämättömästä kärjestä tai kuuluu vuorottelevaan sykliin . Ensimmäisen seurauksen mukaan, jos reuna e on osa tällaista vuorottelevaa ketjua, täytyy olla uusi suurin yhteensopivuus M , ja e kuuluu joko M :lle tai M :lle ja on siksi vapaa. Päinvastoin, jos reuna e on vapaa, niin e on jossain suurimmassa vastaavassa M :ssä, mutta ei M′: ssa . Koska reuna e ei kuulu sekä M :lle että M′: lle, sen on oltava läsnä M :n ja M′ :n symmetrisessä erossa . Symmetrinen ero M :n ja M′: n välillä antaa graafin , joka koostuu eristetyistä pisteistä, parillisista vuorottelevista sykleistä ja parillisista vuorottelevista poluista. Oletetaan, että näin ei ole ja että e kuuluu johonkin parittoman pituiseen polkuun. Mutta sitten yhdellä sovituksista M tai M′ on oltava vähemmän reunoja tässä komponentissa, mikä tarkoittaa, että tämä komponentti kokonaisuudessaan on täydentävä polku tälle sovitukselle. Alkuperäisen lemman mukaan tämä vastaavuus ( M tai M ) ei voi olla suurin, mikä on ristiriidassa sen oletuksen kanssa, että sekä M että M ovat suurimmat vastaavuudet. Näin ollen, koska e ei voi kuulua mihinkään parittoman pituiseen polun komponenttiin, sen täytyy joko sijaita parillisen pituisen syklin sisällä tai vuorotellen parillisen pituisella polulla.

Muistiinpanot

Kirjallisuus