2. Kruhové Mestské Spoje (κ ≤ 2) vzorové riešenie

Zadanie. O sláve Mr. Mira sa dopočuli aj vo Farebnom meste. Zavolali ho, aby im pomohol navrhnúť linky MHD. Vo Farebnom meste majú každú ulicu vymaľovanú jednou z troch farieb: červenou, zelenou alebo modrou. Každá ulica je obojsmerná a spája práve dve križovatky. Z každej križovatky vychádzajú práve tri ulice, z každej farby jedna.

Každá linka MHD má cyklickú trasu. Nemá teda východziu a konečnú zastávku, ale chodí dokola po svojej trase. Pri jednom opakovaní trasy nesmie dvakrát prejsť tou istou ulicou. Dokážte, že je možné v meste zaviesť linky MHD tak, že každou ulicou budú premávať práve dve linky MHD.

Čo to vlastne máme dokázať. Pre lepšiu predstavu si môžeme skúsiť nakresliť zopár príkladov, ako môže vyzerať Farebné mesto a skúsiť v nich nájsť linky MHD. Avšak našou úlohou nie je vyriešiť úlohu na jednom alebo zopár viac konkrétnych mestách. Potrebujeme ukázať, že linky MHD môžeme zaviesť v ľubovoľnom meste, ktoré spĺňa podmienky opísané v zadaní. Konkrétne príklady miest nám môžu pomôcť tak, že na nich môžeme odpozorovať princípy, ktoré budeme vedieť použiť aj vo všeobecnosti.

V zadaní sa píše, že ulice farebného mesta sú zafarbené tromi farbami. Bolo by dobré túto informáciu nejako využiť a skúsiť opísať linky MHD pomocou týchto farieb. Pozrime sa na jednu križovatku. Niektorá linka do nej musí prichádzať (môže aj odchádzať, ale to nevadí, pôjdeme po nej len v opačnom smere) po červenej ulici. Z danej križovatky potom musí pokračovať ulicou inej farby, povedzme zelenou. Pokračujme ďalej po tejto linke do križovatky, kam prichádza po zelenej ulici. Ako bude pokračovať ďalej? Keďže z každej križovatky vychádza z každej farby jedna ulica, tak nám stačí určiť farbu ulice, ktorou má naša sledovaná linka pokračovať. Bolo by dobré, ak by linky striedali farby ulíc podľa nejakého pekného systému. Čo za systém využívajúci farby môžeme vymyslieť. Napr. linky môžu striedať všetky farby v poradí červená, zelená, modrá; môžu striedať len niektoré dve farby alebo aj rôzne komplikovanejšie postupnosti farieb. Môžete sa zamyslieť, v ktorých prípadoch, aké linky dostaneme. Budú kruhové, budú každou ulicou chodiť dve?

Ako dobrým systémom sa ukáže striedanie dvoch farieb. Pozrime sa teda, čo za linky budú také, ktoré budú chodiť striedavo po dvoch farbách, začnime červenou a zelenou farbou.

Vyberme si niektorú križovatku, označme si ju \(T\), a vyberme sa z nej po červenej ulici. Budeme ďalej pokračovať zelenou ulicou, červenou, zelenou a tak ďalej. Keďže z každej križovatky vychádza ulica každej farby, vždy budeme mať kam pokračovať. Keďže mesto má obmedzený počet križovatiek, po nejakom čase sa musíme dostať do križovatky, v ktorej sme už boli. Aby táto červeno-zelená linka bola cyklická, mala by to byť križovatka \(T\), v ktorej sme začali.

Čo ak by sme takto prišli do inej križovatky \(X\)? Keď sme prešli prvýkrát križovatkou \(X\), prešli sme tak červenou a zelenou ulicou (v nejakom poradí), ktoré vychádzajú z križovatky \(X\). Keď sme sa do križovatky \(X\) vrátili po druhýkrát, prišli sme do nej po ešte nepoužitej ulici. Tá má zelenú alebo červenú farbu. Takto dostávame, že z križovatky \(X\) vychádzajú dve zelené alebo dve červené ulice. Preto sa nám nemôže stať, že sa vrátili do križovatky \(X\). Jediná križovatka, v ktorej sa môžeme napojiť na našu prejdenú trasu, je teda križovatka \(T\), z ktorej sme začali.

Takto sme ukázali, že ak z jednej križovatky budeme striedať červené a zelené ulice, budeme chodiť do kola tými istými ulicami. Preto môžeme zaviesť cyklickú linku, ktorá bude chodiť týmito ulicami. Samozrejme, mohli ostať červené a zelené, ktorými táto linka neprešla. V takom prípade tento náš postup zopakujeme a dostaneme tak niekoľko cyklických liniek, ktoré budú striedať červené a zelené ulice. Linky takéhoto typu budeme volať červeno-zelené.

Podobným spôsobom zavedieme aj zeleno-modré a modro-červené linky. Tie budú z rovnakého dôvodu tiež cyklické. Vo Farebnom meste teda zavedieme linky troch typov: červeno-zelené, zeleno-modré a modro-červené. Z jedného typu nám môže v meste vzniknúť aj viac liniek. Všetky takéto linky budú teda cyklické.

Ostáva nám teda ukázať, že každou ulicou budú prechádzať práve dve linky. To je jednoduché, lebo každá farba sa nachádza práve v dvoch typoch liniek. Jednou červenou ulicou bude chodiť jedna červeno-zelená a jedna modro-červená linka. Pri zelených a modrých uliciach je to podobne.

Tak sme ukázali to, čo sme mali. Vo Farbnom meste môžeme zaviesť linky spomenutých troch typov. Dostaneme niekoľko cyklických liniek a každou ulicou budú prechádzať práve dve linky. Názorné riešenie a ďalšie pohľady na túto úlohu môžete nájsť aj vo videovzoráku.