Zadanie
Po tom, čo spokojne dohrajú hru, sa ozve buchot pred Merlinovou chatrčou. Krtko vykukne z okna von a zbadá vojakov, ktorí ho hľadajú. Neváha ani chvíľu a vylezie cez okno na neďaleký strom. A kým vojaci spovedajú Merlina a prehľadávajú dom, Krtko sa obzerá po listoch na strome.
Krtkov strom1 má \(2n\) listov. Ukážte, že vždy vieme pridať \(n\) hrán tak, aby výsledný graf bol súvislý aj po zmazaní ľubovoľnej hrany (zmazať možno pôvodnú alebo novú hranu).
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.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.