Opravovatelia

Matúš [email protected]

List je vrchol v strome, z ktorého vychádza len jedna hrana.

Hranami musíme pospájať len listy, inak by po odobratí hrany, ktorá vychádza z listu ostal nesúvislý graf.

Samotný dôkaz vykonáme sporom. Predpokladajme, že nevieme pospájať $2n$ listov pomocou $n$ hrán tak, že po odobratí akejkoľvek hrany bude výsledný graf súvislý. Každé popárovanie $2n$ listov $n$ hranami nám určí množinu hrán takých, že po odobratí ktorejkoľvek hrany z tejto množiny získame nesúvislý graf. Rozmyslite si, že táto množina nikdy neobsahuje hrany vedúce do niektorého z listov. Nech $M$ je minimálna takáto množina hrán (ak zoberieme do úvahy všetky možné popárovania v danom grafe). Ukážeme si teraz, že z popárovania listov, ktoré nám určuje množinu $M$, vieme vytvoriť nové popárovanie, ktoré bude mať menšiu takúto množinu, čo bude v spore s minimalitou množiny $M$.

Nech hrana $e = v_1v_2$ patrí $M$. Potom odobratím hrany $e$ znesúvislíme pôvodný graf. Nech $P$ je to popárovanie, ktoré generuje množinu $M$. Po odobratí hrany $e$ dostaneme $2$ grafy. Nech $L_1$ sú listy, ktoré sú v tom istom grafe ako vrchol $v_1$. O týchto listoch vieme, že musia byť popárované medzi sebou, lebo inak by sme po odobratí hrany $e$ vedeli prejsť z $v_1$ do vrchola $v_2$, čo nevieme. Rovnako to isté vieme o listoch, čo sú v grafe s vrcholom $v_2$. Nazvime ich listy $L_2$.

Vyberme si teraz dva listy $x,\, y$ z $L_1$ a dva listy $a,\, b$ z $L_2$ také, že $xy$ aj $ab$ sú hranami z tých $n$ hrán (teda vrcholy $x,\, y$ a $a,\, b$ sú spojené hranou).

Skonštruujme teraz nové párovanie $P’$ z párovania $P$ nasledovne: ponecháme v ňom všetky hrany z $P$ okrem $xy,\, ab$. Miesto nich tam pridáme hrany $ax,\, by$. Párovaniu $P’$ prislúchajú hrany $M’$, ktorých odobratím vznikne nesúvislý graf.

Ukážeme si teraz, že všetky hrany, ktoré nepatrili do $M$ nepatria ani do $M’$, a že hrana $v_1v_2$ tiež nepatrí do $M’$. Preto $|M’| < |M|$, čo bude spor s minimalitou $M$.

V popárovaní $P’$ po odobratí hrany $e = v_1v_2$ sa vieme z vrchola $v_1$ do vrchola $v_2$ dostať nasledovne: z vrchola $v_1$ sa vieme dostať do vrchola $a$, odtiaľ novou hranou $ax$ do vrchola $x$ a odtiaľ sa vieme dostať do vrchola $v_2$. Preto odobratím hrany $e$ nevznikne nesúvislý graf, a preto nepatrí do množiny $M’$.

Teraz už rovno nahliadneme, že všetky hrany, ktoré nepatrili do $M$ nepatria ani do $M’$. Najprv si ale ešte zadefinujeme dva intuitívne pojmy, ktoré pri dôkaze využijeme.

Nech $a$-$b$ cesta je cesta medzi vrcholmi $a,\, b$ v pôvodnom strome a $x$-$y$ cesta je zase cesta medzi vrcholmi $x,\, y$ v pôvodnom strome (bez toho, aby sme do stromu pridali tých $n$ hrán).

Nech $h = uv$ je hrana, ktorá nepatrila do $M$ pri popárovaní $P$, teda jej odobratím nevznikol nesúvislý graf pri danom popárovaní.

Zrejme si pôvodný graf vieme rozdeliť na dva grafy spojené hranou $e$. Nech $G_1$ je graf, ktorý obsahuje vrcholy $a,\, b$ a $G_2$ je graf, ktorý zase obsahuje vrcholy $x,\, y$.

BUNV nech $h$ patrí $G_1$ (ak $h$ patrí $G_2$ myšlienka dôkazu je analogická). Chceme teraz vytvoriť cestu medzi vrcholmi $u$ a $v$ pri novom popárovaní $P’$. Vytvoríme ju simulovaním pôvodnej cesty, ktorú sme v predošlom odseku spomenuli a následnými drobnými úpravami, ak to bude potrebné.

Simulujme teraz cestu medzi vrcholmi $u,\, v$ pri pôvodnom popárovaní $P$, kým nenarazíme na hranu $ab$. Ak na ňu nenarazíme, rovno sme vytvorili cestu medzi $u,\, v$ v novom popárovaní $P’$.

Ak ale cesta obsahovala hranu $ab$, vieme pokračovať nasledovne: prejdeme po hrane $ax$ potom prejdeme $x$-$y$ cestou a na záver prejdeme hranou $yb$. Zrejme cesta medzi $u,\, v$ pri pôvodnom popárovaní je len v grafe $G_1$, lebo oba vrcholy sú v grafe $G_1$ a z $G_1$ do $G_2$ sa dá dostať len jednou hranou $e$. Rovnako to isté môžeme povedať o $x$-$y$ ceste, takže sa nebudú križovať. Následne pokračujeme už bez problémov až kým neprídeme do vrchola $v$, pretože vieme, že pôvodná cesta nemôže obsahovať aj $ab$ aj $xy$ hranu.

V prípade, že $h$ patrí grafu $G_2$ postupujeme analogicky. Ak narazíme na hranu $xy$, v ceste ju nahradíme hranou $ax$, $a$-$b$ cestou a hranou $yb$.

Tým sme ukázali, že každá hrana, ktorá nepatrila do $M$ nepatrí ani do $M’$ a súčasne hrana $e$ patrila do $M$ ale do $M’$ už nepatrí. Preto $|M’| < |M|$, čo je nami hľadaný spor.