Opravovatelia

Šošo [email protected]

Uvažujme orientovaný graf, kde veľvyslanci budú vrcholy a hrana ${u, v}$ existuje práve vtedy, keď sa príslušný veľvyslanec $u$ pozerá na veľvyslanca $v$. Vyberme ľubovoľný vrchol $v_0$. Ten je v nejakom komponente súvislosti grafu. Posúvajme sa dopredu z $v_0$ v smere hrán. Postupne budeme navštevovať vrcholy, a keďže ich je konečne veľa, tak narazíme na vrchol, ktorý sme už navštívili. Preto máme v komponente cyklus. Zároveň si môžeme všimnúť, že viac cyklov v komponente mať nemôžeme, keďže z cyklu nevedie hrana von, teda by neexistovala cesta medzi týmito cyklami. Rovnako nemôžeme mať 2 cykly zdieľajúce vrchol, keďže z každého vrchola vedie iba jedna hrana. Preto máme v komponente práve jeden cyklus, teda keď odoberieme z neho hranu, dostaneme strom. Inak povedané, každý komponent grafu obsahuje cyklus a každý vrchol cyklu je koreňom stromu, ktorý sa „napája na cyklus“ (môže byť aj veľkosti 1).

Začnime podúlohou 2. V každom komponente môžeme zo „stromových častí“ začať odoberať vrcholy od listov (veľvyslanci, na ktorých sa nikto nepozerá začnú odchádzať). Takto odoberieme všetky stromy bez toho, aby nejaký vrchol zaspal. Ostal nám cyklus $v_1v_2 \dots v_k$, kde hrany sú ${v_i, v_{i+1}}, {v_k, v_1}$. Z neho môžeme odobrať vrcholy postupne $v_1, v_2, \dots v_{k-1}$, pričom zaspí iba vrchol $v_k$. Teda pre každý komponent vieme dosiahnuť, aby zaspal práve jeden vrchol. Menej unudených vrcholov mať nemôžeme, keďže v komponente je cyklus a ak odoberieme vrchol z cyklu (čo musíme, lebo vrcholy z cyklu sa pozerajú do cyklu), tak jeden vrchol zaspí. Teda minimum unudených vrcholov je počet komponentov, čo je najviac $\left\lfloor \frac{n}{2} \right\rfloor$. Tento počet spĺňa konštrukcia, kde máme samé dvojcykly prípadne jeden trojcklus, ak je $n$ nepárne.

Pokračujme 3. podúlohou. V každom komponente veľkosti $k$ môžeme mať vždy najmenej 1 unudený vrchol a najviac $k-1$ unudených vrcholov, keďže aspoň jeden vrchol musíme odstrániť. Teda za každý komponent je tento súčet najviac $k$. Sčítaním cez všetky komponenty dostávame požadované tvrdenie.

Na 1. podúlohu je odpoveď $\left\lceil \frac{n}{3} \right\rceil$. Pre konštrukciu zvoľme samé trojcykly, prípadne jeden 4-cyklus alebo 5-cyklus podľa zvyšku $n$ po delení tromi. Z každého trojcyklu môže byť najviac 1 vrchol unudený a z 4-cyklu, resp. 5-cyklu najviac 2, keďže unudených vrcholov musí byť najviac toľko ako odídených, pokiaľ sa na každý vrchol pozerá 1 vrchol. Tým dostaneme $\left\lceil \frac{n}{3} \right\rceil$ unudených vrcholov. Stačí ukázať, že $\left\lceil \frac{n}{3} \right\rceil$ unudených vrcholov vždy vieme mať.

Predpokladajme sporom, že by to tak nebolo pre nejaký graf s našimi vlastnosťami (teda pre taký graf, kde z každého vrcholu vedie práve jedna hrana). Vyberme najmenší taký graf (počtom vrcholov), pre ktorý to neplatí. Predpokladajme, že v nejakom komponente existuje list $l$ (nevedie do neho hrana), ktorého nasledovník nie je v cykle. Potom odstráňme nasledovníka. Všetky vrcholy, z ktorých viedla hrana do nasledovníka vrátane $l$ zaspia. Dostávame znovu graf s našimi vlastnosťami, pričom sme odobrali $k$ vrcholov a z toho $k-1$ vrcholov zaspalo. To je viac ako tretina a z minimality grafu vieme odstraňovať vrcholy, aby aspoň tretina zvyšných zaspala. Dokopy teda máme viac ako tretinu unudených, čo je spor. Preto taký list neexistuje, teda všetky vrcholy majú vzdialenosť od cyklu najviac 1.

Nech má komponent $k$ vrcholov. Označme $f(v)$ počet hrán vedúcich do vrcholu $v$. Vrcholy mimo cyklu majú $f(v) = 0$ a súčet všetkých $f(v)$ je $k$ (počet hrán, teda aj počet vrcholov). Pokiaľ je počet vrcholov v cykle párny, vyberme vrcholy na párnych miestach alebo na nepárnych miestach, ktoré majú väčší súčet $f(v)$. Ich súčet $f(v)$ je zároveň počet unudených vrcholov, ktorý je preto aspoň polovica. To je aspoň tretina, čo sme chceli dokázať. Pokiaľ je cyklus nepárny, tak vyberme vrchol $u$ z cyklu s najmenším $f(u)$. Zostane nám párny počet vrcholov na cykle a z nich opäť vyberme vrcholy na párnych alebo nepárnych miestach s väčším súčtom $f(v)$. Pokiaľ má cyklus $c$ vrcholov, počet unudených vrcholov bude aspoň $\frac{c-1}{2c}k \geq \frac{k}{3}$, keďže priemerná hodnota $f(v)$ na cykle je $\frac kc$, vyberieme $\frac{c-1}2$ vrcholov a $c \geq 3$. Dokopy ich preto bude tiež aspoň $\frac{n}{3}$, čo bolo treba dokázať.

Iné riešenie (trochu trikové)

Preveďme si úlohu na graf ako v prvom riešení. Už vieme, že ak odoberieme v komponente hranu z cyklu, dostaneme strom. Ignorujme na chvíľu takúto hranu $h$. Nech má daný komponent $k$ vrcholov. Vrchol $v$, z ktorého vychádzala $h$ je teraz koreňom stromu. Ofarbime strom bipartitne dvomi farbami - párne vrstvy namodro (tie, obsahujúce $v$) a nepárne vrstvy načerveno. Pokiaľ odoberieme celú modrú množinu vrcholov, pričom najprv odoberieme vrchol $v$ (aby náhodou nezaspal pri odoberaní iného vrchola), zaspia všetky červené vrcholy. Pokiaľ odstránime celú červenú množinu, zaspia všetky modré vrcholy okrem $v$ a možno aj vrchol $v$ (ak $h$ išla do červeného vrcholu). Dokopy zaspí aspoň $k-1$ vrcholov a najviac $k$. Pri jednej možnosti odobrania máme preto aspoň $\frac{k-1}{2}$ unudených vrcholov a pri druhej najviac $\frac{k}{2}$ unudených vrcholov.

Teraz ľahko vyriešime 1. aj 2. podúlohu. Pokiaľ $k = 2$, tak z daného komponentu vieme vynútiť 1 unudený vrchol. Pre $k \geq 3$ platí $\frac{k-1}{2} \geq \frac{k}{3}$, teda vieme vynútiť aspoň tretinu unudených vrcholov z každého komponentu. Preto vieme vynútiť aspoň tretinu unudených vrcholov aj v celom grafe. Preto je odpoveď na 1. podúlohu $\left\lceil \frac{n}{3} \rceil$ (konštrukcia je rovnaká ako v prvom riešení).

Z každého komponentu vieme vynútiť aspoň polovicu neunudených vrcholov, teda aj v celom grafe. Odpoveď na 2. podúlohu je teda $\left\lfloor \frac{n}{2} \rfloor$ (konštrukcia je opäť rovnaká).

Pre tretiu úlohu uvažujme najväčšiu možnú množinu unudených vrcholov. Nech je ich $u$. Tieto vrcholy sa na seba zrejme nepozerajú. Preto ich môžeme postupne odobrať. Zvýšia nám ostatné vrcholy, z ktorých odoberáme ľubovoľne. Počet unudených vrcholov je potom najviac $n-u$, keďže aspoň $u$ bolo odobratých. Najmenší možný počet unudených vrcholov preto nemôže byť viac ako $n-u$. Preto súčet najmenšieho a najväčšieho počtu unudených vrcholov je najviac $n$, čo bolo treba dokázať.