První série dvacátého devátého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

• Termín série: 10. října 2016
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

• Odměna série: Sladkou odměnu pošleme každému, kdo vyřeší tři libovolné úlohy na plný počet bodů.

Zadání úloh

• 29-1-1: Připálené placky
• 29-1-2: Kupecké počty
• 29-1-3: Střídání zbraní
• 29-1-4: Zběsilý útěk
• 29-1-5: Lučištníci
• 29-1-6: Štítové kouzlo
• 29-1-7: Stromy kolem nás

„Nepovídej mi, že máme zase místo placek chlebové uhlí!“ poznamenal naoko výhružně Warin a poklepal si na meč zavěšený za pasem. Samozřejmě to nemyslel vážně, ale s Rheou se rádi navzájem škádlili. Znal se s ní déle než s kýmkoliv jiným z jejich malé družinky a prožili toho spolu již hodně – on jako rytíř řádu, ona jako nadaná kouzelnice.

Zbytek jejich družiny nacházející se v severské pustině tvořili ještě nadaný zloděj a lukostřelec Gorf a druhý rytíř, mladý Lian. Do této prapodivné skupinky je svedl důležitý úkol a už více než týden putovali daleko za známými a bezpečnými cestami království.

Teď ale byl jejich hlavní starostí ukrutný hlad. Připálené placky sice nejsou zrovna lahůdka, ale když se z nepřipálené strany namažou máslem, tak se jíst dají. Jenom při rychlém sundavání z ohně je Rhea poskládala náhodně na jednu hromádku.

29-1-1 Připálené placky (8 bodů)

Máme na sobě položenou spoustu placek, každá z nich je z jedné strany připálená a z druhé strany krásně dozlatova. Rádi bychom všechny placky otočili nepřipálenou stranou nahoru, abychom je pak mohli všechny rychle namazat máslem.

Bohužel placky jsou ještě příliš horké na to, abychom je brali do rukou. Jediné, co můžeme dělat, je podebrat si několik vrchních placek pánvičkou a celou tuto část otočit. Jak to vypadá, si můžete prohlédnout na následujícím obrázku.

Dostanete zadáno, jak vypadá hromada placek (posloupnost říkající, které z placek leží nahoru připálenou stranou a které nepřipálenou). Vaším úkolem je najít co nejkratší posloupnost podebrání a otočení takovou, aby se po jejím provedení všechny placky nacházely nepřipálenou stranou nahoru.

Řešení

29-1-2 Kupecké počty (11 bodů)

Skupina kupců se společně podílela na jedné velké investici. Každý platil nějakou část, některé z nich to stálo více a některé naopak méně. Nyní by si chtěli všechny náklady rovnoměrně rozdělit tak, aby ve výsledku investovali všichni stejně.

Kupci se mohou vyrovnat tím, že ti, kteří platili málo, dají nějaký obnos těm, kteří platili hodně. O každém předání peněz se ovšem musejí dělat záznamy v účetních knihách, a tak by kupci chtěli provést těchto převodů peněz co možná nejméně.

Navíc se ale žádný z kupců nechce zadlužit více, než už je, nebo se naopak nechat přeplatit víc, než už přeplacený je. Není tak třeba možné kupci, který má dostat 100 zlatých, dát 120 zlatých, protože by se tím stal o 20 zlatých přeplacený. Stejně tak není možné poslat jakékoliv peníze kupci, který ostatním dluží (zadlužil by se ještě víc).

Vymyslete postup, který pro zadané částky zaplacené jednotlivými kupci spočítá, kdo komu má kolik dát tak, aby byla respektována uvedená pravidla a převodů bylo málo.

Spočítat řešení s úplně nejmenších počtem převodů je těžký problém a tak to po vás ani nechceme (jako dobrovolné cvičení si však můžete zkusit rozmyslet, proč je to těžký problém). K vyřešení úlohy stačí, když vymyslíte postup vedoucí k maximálně dvojnásobnému počtu převodů peněz, než je optimum. Důležitou částí je i důkaz, že uděláte nejvýše dvojnásobek převodů, než je nezbytně nutné udělat.

Řešení

29-1-3 Střídání zbraní (12 bodů)

Gardisté městské gardy mají k dispozici přesně tolik kopí, kolik jich v gardě slouží. Každé kopí je ale jinak dlouhé a jednotliví gardisté jsou také různě vysocí.

Když si gardisté vybírají, se kterým kopím půjdou bojovat, jsou ochotni si vzít jenom kopí nanejvýš tak dlouhé, jak jsou oni vysocí (neboli gardista nemůže mít delší kopí, než je jeho výška).

Při výcviku dbají velitelé na to, aby si co nejvíce gardistů zkusilo bojovat s co nejvíce různými kopími. Zajímalo by je tedy, kolik existuje různých možností, jak si gardisté mohou rozdělit kopí tak, aby každý dostal právě jedno a to nebylo vyšší, než je on sám. Vaším úkolem to je pro zadané délky kopí a výšky gardistů spočítat.

Příklad: Pro kopí o délkách 7,3,6,1 a pro gardisty vysoké 3,7,4,8 existují celkem 4 možnosti, jak si kopí mohou rozdělit. Gardisté ve výše uvedeném pořadí dostanou kopí délek (1,6,3,7), (3,6,1,7), (1,7,3,6) nebo (3,7,1,6).

Řešení

29-1-4 Zběsilý útěk (10 bodů)

Stopaře překvapil v divočině drak, a tak se před ním dal na útěk. Stopař má představu o tom, jak vypadá okolní terén, takže si naplánoval dostatečně klikatou trasu na zmatení draka. Okolí se skládá buď z normálně prostupného terénu, nebo ze strašidelných hustolesů.

Stopařova trasa je tvořena lomenou čárou (neboli na sebe navazujícími úsečkami), která může procházet i skrz hustolesy, ale v takovém případě v nich stopař zvládne běžet jen poloviční rychlostí. Hustolesy jsou obdélníkové oblasti, které budou, stejně jako stopařova trasa, zadány na vstupu.

Navíc máme slíbeno, že každou úsečku na trase protíná nejvýše jeden hustoles a že hustolesů je zhruba stejně mnoho, jako úseček trasy. Představu můžete získat třeba z obrázku níže. Vaším úkolem bude spočítat, jak dlouho bude stopařovi proběhnutí celé trasy trvat.

Při řešení by se vám mohlo hodit nahlédnout do geometrické kuchařky.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku vstupu dostanete tři celá čísla oddělená mezerou: Nejprve rychlost stopaře v normálním terénu V vyjádřenou v metrech za sekundu. Dále pak číslo N udávající počet bodů na stopařově trase (mezi těmito body se stopař pohybuje po úsečce) a nakonec číslo H udávající počet hustolesů (pozor, jeden hustoles může zasahovat i do více úseček).

Na dalších N řádcích naleznete vždy dvě čísla, každá dvojice udává souřadnice jednoho z bodů na stopařově trase. A nakonec na dalších H řádcích najdete vždy 4 čísla a_x,a_y,b_x,b_y udávající souřadnice levého dolního a pravého horního rohu daného hustolesa. Všechny souřadnice jsou zadány v metrech.

Formát výstupu: Na výstup vypište počet sekund, za které stopař překoná celou trasu, zaokrouhlený na celé sekundy.

10 5 2
100 100
350 350
500 500
1100 500
1100 100
100 200 1300 300
400 400 600 600

205

Stopař celkově uběhne cca 1566 m, z toho cca 483 m hustolesem.

Řešení

29-1-5 Lučištníci (10 bodů)

Lučištníci stojící v řadě na hradbě mají vyhlédnuté své cíle. Každý z nich míří lukem na nějaké místo, ale je neúčinné a nebezpečné, aby všichni stříleli, jak se jim zachce. Rádi by svou palbu koncentrovali a navíc by měli střílet jen ti, jejichž dráhy palby se nekříží.

Lučištníky můžeme popsat pomocí bodů, na které míří. Například na obrázku níže nultý lučištník míří na bod 2, první na bod 0, druhý na bod 3, třetí na bod 1, čtvrtý na bod 5, pátý na bod 4 a šestý na bod 6.

Ze všech lučištníků chceme vybrat co největší skupinu, jejíž dráhy střelby se nekříží. V uvedeném příkladě jsou to třeba lučištníci 0, 2, 4 a 6 (zvýraznění plnými čarami). Stejně tak by fungovali třeba lučištníci 1, 2, 5 a 6.

Navrhněte algoritmus, který takovou skupinu najde. Pokud existuje více řešení, stačí oznámit libovolné jedno z nich.

Řešení

29-1-6 Štítové kouzlo (10 bodů)

Na městské hradby útočí drak a postupně je ničí. Městské hradby si můžeme představit jako řadu různě vysokých kusů. Drak při každém svém náletu ubere všem nechráněným kusům hradeb jednu jednotku výšky. Níže, než úplně do základů, je ale spálit nemůže (výška hradeb nemůže jít do záporných čísel).

Hradby můžeme chránit pomocí štítového kouzla, ale kouzelnice Rhea umí roztahovat štít vždy jen o jeden kus hradeb mezi každými dvěma drakovy útoky. Navíc chráněná oblast hradeb musí být souvislá.

Začneme tedy tvořit štít nad libovolným kusem hradeb, který je od této chvíle chráněn a již se neničí. V každém dalším kroku ho můžeme rozšířit o jedna doleva, nebo doprava.

Vaším cílem je pro zadané výšky hradeb poradit kouzelnici Rhee, kde má začít a jak má štít postupně rozšiřovat, aby se v součtu uchránilo co nejvíce hradeb (tedy aby součet zbylých výšek hradeb byl co největší).

Příklad: Pro hradby vysoké 5,1,1,1,4,4,1 je nejlepší začít se štítem nad předposledním úsekem hradeb a pak ho rozšiřovat směrem doleva. Tím se nám povede uchránit celkově 7 dílů hradeb. Kdybychom začali na páté pozici a rozšiřovali doprava, uchráníme stejně dílů hradeb, kdežto kdybychom začali se štítem nad nejvyšší hradbou, tak se nám povede uchránit nejvýše 5 dílů hradeb – vysoké hradby na opačné straně padnou dříve, než nad ně stihneme rozšířit štít.

Na obrázku jsou znázorněny výšky hradeb a části, které z nich zůstanou, pokud začneme stavět štít nad předposlední hradbou a roztáhneme ho doleva (další stavění štítu pak už nic jiného nezachrání).

Řešení

29-1-7 Stromy kolem nás (15 bodů)

Pojďte, v letošním seriálu spolu budeme zkoumat stromy. Ne snad že bychom vás chtěli přeučit na botaniky – půjde nám o stromy ryze abstraktní, matematické. A ještě více o algoritmy pro práci s nimi.

Klíč k určování stromů

Definici stromu najdete v kuchařce této série: je to souvislý graf bez kružnic. To zní učeně, ale kupodivu je to i velmi praktické: příklady takových stromů potkáváme všude kolem sebe.

Hierarchie – kupříkladu továrna má továrníka, pak ředitele, ten své náměstky, jejich podřízenými jsou šéfové oddělení, jim podléhají mistři v dílnách, a tak dále až k řadovým dělníkům. Příslušný strom sestává z vrcholů (což jsou zaměstnanci) a hran (vztahy „být přímým podřízeným“). (Sám název hierarchie pochází z byzantské řečtiny: hieros znamená svatý, z toho hiereus je kněz; arché značí moc, vládu. Jak to souvisí: Původně se hierarchií nazývaly složité vztahy podřízenosti mezi církevními hodnostáři.)

Stromy popisující nějakou hierarchii mají většinou jeden význačný vrchol – v našem příkladě je to pan továrník, obecně se mu říká kořen stromu. Jakmile nějaký kořen zvolíme, hned je jasné, kterým směrem je to ve stromu nahoru (ke kořeni) a kterým dolů. Nenechte se prosím zmást tím, že na rozdíl od biologů matematici kreslívají stromy kořenem nahoru. Podle směru také můžeme sousedy každého vrcholu rozdělit na otce (směrem ke kořeni, v našem příkladě nadřízený) a syny (směrem od kořene, tedy podřízení). Kořen nemá otce, ostatní vrcholy mají právě jednoho otce. Listy jsou ty vrcholy, jež nemají syny.

Libovolný vrchol v spolu se všemi svými potomky (to jsou jeho synové, pak synové synů, atd.) tvoří podstrom, jehož kořenem je v.

Aritmetický výraz – mějme nějaký výraz s čísly a aritmetickými operacemi, třeba 1-2*(3+4)+5. Pořadí, v jakém se jednotlivé operace vyhodnocují, můžeme popsat stromem:

Listy odpovídají zadaným číslům, ostatní (vnitřní) vrcholy jednotlivým podvýrazům. V každém vnitřním vrcholu bydlí jedna operace, která dostane mezivýsledky ze svých synů a pošle svůj výsledek otci. V kořeni pak získáme výsledek celého výrazu. Jelikož běžné operace pracují s právě dvěma čísly, půjde o strom binární – tedy každý vrchol kromě listů bude mít právě dva syny.

Městečko lakomců – mapu nějakého městečka si můžeme představit jako obecný graf: hrany odpovídají ulicím, vrcholy křižovatkám; slepé konce budeme považovat za speciální případ křižovatek. Pokud ale je pan starosta držgrešle a chce udržovat co nejméně silnic, brzy z městečka zbude jen kostra, tedy strom propojující všechny křižovatky. To je příklad stromu, který nemá žádný přirozený kořen. Můžeme ho tedy zakořenit libovolně, třeba na náměstí s radnicí.

Úkol 1 [1b]

Najděte nějaký další pěkný příklad stromu. Čím méně bude podobný těm našim, tím lépe.

Reprezentace stromu

Jak stromy reprezentovat v paměti počítače? Zajisté můžeme použít totéž, co u obecných grafů: vrcholy očíslujeme a pro každý z nich si zapamatujeme seznam čísel sousedů. Jinými slovy, každý vrchol si pamatuje seznam všech hran, které z něj vedou.

Zakořeněné stromy obvykle prohledáváme od kořene dolů. Tehdy si stačí v každém vrcholu pamatovat seznam jeho synů. Někdy se hodí zapamatovat si navíc i otce vrcholu (případně informaci, že jde o kořen).

Snadno odvodíme, že strom o n vrcholech má přesně n-1 hran: Zakořeníme ho v libovolném vrcholu a všimneme si, že z každého vrcholu kromě kořene vede právě jedna hrana do otce. Tak jsme každou hranu započítali právě jednou.

Budeme se proto snažit, aby všechny algoritmy pro práci se stromy běžely v čase O(n), kde n je počet vrcholů. To postačí na projití všech vrcholů a hran, ale už ne na cokoliv náročnějšího.

Prohledávání do hloubky

Chceme-li navštívit všechny vrcholy stromu, můžeme to udělat třeba prohledáváním do hloubky. Začneme v kořeni, a kdykoliv přijdeme do nějakého vrcholu, rekurzivně se zavoláme na všechny jeho syny. Přesněji řečeno, nejprve se zavoláme na prvního syna, až se z rekurze vrátíme (prohledali jsme podstrom pod tímto synem), zavoláme se na druhého syna, a tak dále.

Abychom lépe viděli, jak prohledávání do hloubky probíhá, doplníme do něj výpis levé závorky při vstupu do vrcholu a pravé při jeho opuštění.

DFS(v):

1. Vypíšeme (.
2. Pro všechny syny s vrcholu v:
3. Zavoláme DFS(s)
4. Vypíšeme ).

Spustíme-li algoritmus DFS (tak se mu říká podle anglického názvu depth-first search) na náš příklad stromu výrazu, vypíše ((()(()(()())))()). Všimněte si, že jsme strom jakoby „obešli po obvodu“ – kdykoliv jdeme po hraně dolů, píšeme levou závorku, kdykoliv nahoru, pravou. Navíc přidáme jeden úplně vnější pár závorek.

Celý průchod stromem trvá O(n): v každém vrcholu strávíme čas O(1 + počet synů). Pokud to posčítáme přes všechny vrcholy, jedničky se sečtou na n a počty synů na n-1.

Infixový zápis tedy (až na přebytečné závorky) odpovídá tomu, jak obvykle výrazy zapisujeme. Aby se hodnoty v listech neztratily, samozřejmě je vypisujeme přímo, i když mezi žádnými syny neleží.

Postfixový zápis má zase tu hezkou vlastnost, že je jednoznačný i bez závorek. I z očesaného 1 2 3 4 + * - 5 + můžeme rekonstruovat celý strom. Podobně pro prefixový zápis.

Úkol 2 [2b]

Vymyslete algoritmus, který vytvoří strom z jeho postfixového výpisu bez závorek. Vyzkoušejte si to třeba na výrazech.

Úkol 3 [1b]

Ukažte dva různé binární stromy se stejným infixovým zápisem bez závorek. Jak vypadá jejich prefixový a postfixový zápis?

Výpočty pomocí DFS

Spoustu vlastností stromů můžeme počítat rekurzivně: stačí je umět spočítat pro listy a pak říci, jak z výsledků pro podstromy stanovit výsledek pro celý strom. Takový výpočet jde jednoduše zabudovat do DFS. Začněme triviálním příkladem.

Počet listů – stačí vracet z listů jedničku a ve vnitřních vrcholech hodnoty sčítat:

PočetListů(v):

1. Je-li v list, vrátíme 1.
2. ℓ←0
3. Pro všechny syny s vrcholu v:
4. ℓ←ℓ+ PočetListů(s)
5. Vrátíme ℓ.

Jelikož jsme každý krok prohledávání jenom konstanta-krát zpomalili, algoritmus má opět lineární složitost.

Hloubka stromu – tak se říká délce nejdelší cesty z kořene do listu (délka cesty se měří v hranách). Opět ji spočítáme úpravou DFS: nahlédneme, že hloubka stromu je o jedna více než maximum z hloubek podstromů (nejdelší cesta z kořene do listu musí vést z kořene do některého podstromu a pak pokračovat nejdelší cestou uvnitř podstromu). Hloubka listu je 0. Lineární algoritmus následuje:

Hloubka(v):

1. Je-li v list, vrátíme 0.
2. h ←0
3. Pro všechny syny s vrcholu v:
4. h ←max(h, Hloubka(s))
5. Vrátíme h+1.

Úkol 4 [4b]

Vymyslete, jak spočítat průměr stromu. Tak se říká délce nejdelší cesty. Pozor, není to totéž jako hloubka stromu, protože nejdelší cesta nemusí vést „shora dolů“ (v příkladu s továrnou jedna taková vede mezi skladníkem a některým z dělníků).

Vyhodnocení výrazu – výraz reprezentovaný stromem můžeme snadno vyhodnotit: kdykoliv se vracíme z vrcholu, spočítáme výsledek příslušného podvýrazu. Pro list vrátíme číslo v něm uložené, ve vnitřních vrcholech vezmeme hodnoty ze synů a aplikujeme na ně operaci uloženou ve vrcholu.

Strážníci – ve „stromovém“ městečku bují zločin (lidé kreslí křídou na chodníky karikatury radních!). Starosta chce na vybrané křižovatky rozestavět strážníky tak, aby každá ulice byla z alespoň jedné strany hlídaná. Jak už ale víme, je to skrblík. Pro každou křižovatku proto zjistil, kolik musí zaplatit strážníkovi, aby tam byl ochoten stát, a hledá celkově nejlevnější rozestavění strážníků.

Formálně řečeno, hledáme podmnožinu vrcholů stromu, která z každé hrany obsahuje alespoň jeden vrchol a navíc je součet cen vrcholů v množině nejmenší možný.

Nabízí se opět zapřáhnout DFS a vracet z podstromů, jak nejlaciněji je jde ohlídat. Jenže pak nedovedeme z výsledků pro podstromy zkombinovat výsledek pro celý strom. Pomůže, když si pro každý podstrom místo jednoho čísla spočítáme rovnou dvě. Budeme jim říkat h a o. To první („hlídaná cena“) bude udávat, kolik nejméně stačí zaplatit na ohlídání hran podstromu za podmínky, že v kořeni podstromu bude stát strážník. Naopak o („opuštěná cena“) hlásá minimální cenu za podmínky, že kořen je opuštěný.

V listu je triviálně h rovno ceně listu a o=0 (podstrom nemá žádné hrany, takže není potřeba nic hlídat).

Všechna h a o tedy hravě spočítáme pomocí DFS v čase O(n). Odpověď na starostovu otázku pak získáme jako minimum z h a o kořene.

Strážníci(v):

1. c_v ←cena vrcholu v
2. Je-li v list, vrátíme (c_v,0).
3. h ←c_v, o ←0
4. Pro všechny syny s vrcholu v:
5. (h_s,o_s) ←Strážníci(s)
6. h ←h + min(h_s,o_s)
7. o ←o + h_s
8. Vrátíme (h,o).

Úkol 5 [4b]

Strážníci si pořídili drony a dokáží hlídat i „za jeden roh“. Přesněji řečeno, ulice je hlídaná, pokud stojí strážník na alespoň jedné z krajních křižovatek, nebo na křižovatce, která s krajní sousedí. Pomozte najít nejlevnější rozestavění strážníků pro ohlídání všech ulic.

Vandalská indukce a centrum stromu

Ukážeme si ještě jeden způsob, jak zkoumat stromy. Tentokrát je budeme procházet od listů směrem „dovnitř“. Začneme dvěma jednoduchými pozorováními, přičemž netriviální budeme říkat stromům s alespoň dvěma vrcholy.

Pozorování 1: Každý netriviální strom má nějaký list.

Důkaz: Strom si zakořeníme v libovolném vrcholu a podíváme se na nejhlubší vrchol (nejvzdálenější od kořene). Ten nemá žádné syny a vede z něj jediná hrana do otce. Proto je to list.

Pozorování 2: Odstraníme-li z netriviálního stromu list, vznikne opět strom.

Důkaz: Je třeba ověřit, že graf zůstal souvislý a bez kružnic. Odstraněním vrcholu jsme sotva mohli vytvořit novou kružnici. Pokud byly nějaké dva neodebrané vrcholy spojené cestou, budou spojené i nadále, protože odebraný list nemůže ležet uvnitř cesty.

Z toho plyne následující, poněkud vandalská, technika indukce: ve stromu najdeme list, odtrhneme ho, čímž získáme další strom. Postup opakujeme, dokud nám nezůstane triviální strom. Jestliže zaznamenanou posloupnost odebírání listů obrátíme, dostali jsme postup, jak z jednoho vrcholu postupným přilepováním listů vytvořit původní strom.

Pokud má ovšem celý algoritmus seběhnout v lineárním čase, nemůžeme listy hledat pokaždé znovu. Budeme si udržovat frontu objevených, ale dosud neutržených listů. Na začátku spočítáme stupně všech vrcholů a listy přidáme do fronty. V každém dalším kroku odebereme jeden list z fronty a odstraníme ho ze stromu.

Jeho sousedovi snížíme stupeň o jedničku, a pokud se tento soused stal listem, přidáme ho do fronty. Každý vrchol se dostane do fronty právě jednou a jeho obsluhou strávíme konstantní čas. Celé otrhávání tedy beží v čase O(n), jak jsme chtěli.

Můžete si zkusit vymyslet, jak tuto „vandalskou indukci“ použít na libovolný z příkladů, které jsme řešili pomocí DFS. Není divu – když se DFS vrací z rekurze, také postupuje od listů ke kořeni. My zde ukážeme, jak najít „střed“ stromu, což se přímo pomocí DFS dělá obtížně.

Definice: Pro libovolný vrchol v zavedeme jeho excentricitu (výstřednost) jako maximum ze vzdáleností z v do ostatních vrcholů. (Pokud bychom tedy strom ve v zakořenili, bude nám to říkat, jak hluboko je nejhlubší list.) Centrum stromu říkáme množině všech vrcholů s nejmenší možnou excentricitou.

Příklad vidíte na následujícím obrázku. Čísla udávají excentricity, zvýrazněný vrchol je centrem stromu.

Dokážeme, že centrum každého stromu je tvořeno buďto jedním vrcholem, anebo dvěma vrcholy spojenými hranou. Navíc ho lze najít v lineárním čase.

Nejprve si všimneme, že centrum stromu neobsahuje žádný list, neboť soused listu má o jedničku nižší excentricitu. Aby tato úvaha fungovala, nesmí být soused listu také list, takže strom musí mít aspoň 3 vrcholy.

Nyní se nám bude hodit, že odstraněním všech listů se sníží excentricity všech ostatních vrcholů právě o 1. Každá nejdelší cesta z vnitřního vrcholu totiž končila v nějakém listu, tím pádem jsme ji zkrátili o jednu hranu.

Zkombinujeme-li tyto dvě vlastnosti, zjistíme, že „očesáním“ všech listů dostaneme menší strom, který má stejné centrum. Opakováním tohoto postupu graf „oloupeme“ až na jedno- nebo dvouvrcholový strom. U těch snadno nahlédneme, že jejich centrum obsahuje všechny vrcholy.

K nalézání listů nám opět poslouží fronta. Jen musíme umět rozlišit, kde končí listy z jedné „slupky“ a začínají ty z další. K tomu stačí do fronty přidávat zarážku za konec slupky, případně střídat dvě fronty. V obou případech to stihneme v lineárním čase. Může to vypadat třeba následovně:

1. Založíme dvě prázdné fronty F a G.
2. Všem vrcholům spočítáme stupně.
3. Listy přidáme do F.
4. Dokud strom obsahuje alespoň 3 vrcholy:
5. Dokud je F neprázdná:
6. v ←další vrchol z F
7. Odebereme v.
8. Pro všechny sousedy s vrcholu v:
9. Snížíme stupeň s o 1.
10. Pokud stupeň klesl na 1, přidáme s do G.
11. Prohodíme F a G.
12. Zbývající vrcholy prohlásíme za centrum.

Pro strom z předchozího obrázku proběhne výpočet takto:

Úkol 6 [3b]

Navrhněte a naprogramujte algoritmus, který v daném stromu spočítá excentricity všech vrcholů.

Martin „Medvěd“ Mareš

Řešení