Bergeovo lemma

Bergeovo lemma říká, že shoda M v grafu G je největší (obsahuje největší možný počet hran) právě tehdy, když neexistuje žádná komplementární cesta (cesta, která začíná a končí na volné, to znamená, že nepatří do shody, vrcholy a střídavě prochází odpovídajícími a neshodnými hranami) v M ​​.

Lema bylo dokázáno francouzským matematikem Claudem Bergem v roce 1957 (ačkoli o něm již hovořili Petersen v roce 1891 a König v roce 1931).

Důkaz

Abychom dokázali Bergeovo lemma, potřebujeme nejprve další lemma . Vezměte graf G a nechť M a M′ jsou dvě shody v G . Nechť G′ je výsledek symetrického rozdílu M a M′ . To je . G′ se bude skládat z komponent, které patří do následujících skupin:

  1. Izolovaný vrchol .
  2. Sudý cyklus , jehož hrany střídavě patří M a M′ .
  3. Cesta s odlišnými koncovými body, jejichž hrany střídavě patří M a M′ .

Lema lze dokázat poznámkou, že jakýkoli vrchol v G může být incidentní maximálně se dvěma hranami, jednou z M a jednou z M . Grafy, ve kterých má jakýkoli vrchol stupeň nejvýše 2, se musí skládat z izolovaných vrcholů , cyklů a cest . Navíc každá cesta a cyklus v G musí být obsaženy v M ​​a M. Aby se cyklus choval tímto způsobem, musí mít stejný počet hran z M a M , a tedy sudou délku.

Nyní můžeme Bergeovo lemma dokázat kontradikcí - graf G má shodu větší než M právě tehdy, když má G komplementární cestu. Je jasné, že komplementární cestu P grafu G lze použít k získání shody M′ , která je větší než vyhovující M – vezměte jako M′ symetrický rozdíl cest P a M ( M′ se skládá přesně z těchto hrany grafu G , které se objeví právě jednou v cestě P nebo v odpovídajícím M ). Z toho vyplývá důkaz opačným směrem.

Pro dopředný důkaz nechť M′ je shoda grafu G , která je větší než shoda M . Uvažujme jako D symetrický rozdíl M a M′ . Všimněte si, že D se skládá z cest a dokonce cyklů (jak bylo uvedeno v dřívějším lemmatu ). Protože M′ je větší než M , D obsahuje složku, která má více hran z M′ než z M . Takovou složkou je cesta v G , která začíná a končí hranou v M , takže je komplementární.

Důsledky

Důsledek 1

Nechť M je největší shoda a uvažujme střídavý řetězec takový, že hrany v cestě se střídají mezi tím, že patří a nepatří k M . Pokud je střídající se dráha cyklus nebo cesta sudé délky, pak novou největší shodu M′ lze najít výměnou hran mezi M a ne z M . Pokud je například střídavý řetězec , kde , a . Prohozením těchto hran se všechna n i stanou součástí nového párování a všechna m i nebudou zahrnuta do párování.

Důsledek 2

Hrana je považována za „volnou“, pokud patří k největším shodám, ale ne ke všem největším shodám. Hrana e je volná právě tehdy, když v libovolně největší shodě M hrana e patří k sudé střídavé cestě, která začíná v nekrytém vrcholu nebo patří do střídavého cyklu . Podle prvního důsledku, pokud je hrana e součástí takového střídavého řetězce, pak musí existovat nová největší shoda M , a e bude patřit buď M nebo M , a proto je volné. Naopak, je-li hrana e volná, pak e je v nějakém největším shodném M , ale ne v M′ . Protože hrana e nepatří k M a M′ , musí být přítomna v symetrickém rozdílu M a M′ . Symetrický rozdíl mezi M a M′ dává graf sestávající z izolovaných vrcholů, dokonce střídajících se cyklů a střídavých cest o sudé délce. Předpokládejme, že tomu tak není a že e patří k nějaké cestě liché délky. Pak ale jedno z párování M nebo M′ musí mít v této komponentě méně hran, což znamená, že tato komponenta jako celek je doplňkovou cestou pro toto párování. Podle původního lemmatu pak tato shoda ( M nebo M ) nemůže být největší, což je v rozporu s předpokladem, že M i M jsou největší shody. Protože tedy e nemůže patřit do žádné složky cesty s lichou délkou, musí ležet buď v cyklu sudé délky, nebo na střídavě cestě sudé délky.

Poznámky

Literatura