Zkouška - Mareš 21. 1. 2019

1. KMP - popis, analýza, ...

2. Předseda a tajemník - Máme množinu poslanců a množinu klubů, přičemž každý poslanec může být ve více klubech. Cílem je najít pro každý klub z jeho členů předsedu a tajemníka tak, aby žádný poslanec nezastával více než jednu funkci.

3. Najděte algoritmus, který hledá průsečíky kružnic (s nápovědou, že půjde o nějakou úpravu průniků přímek)

Řešení:
2) Vyrobí se bipartitní graf, kde v levé partitě jsou všichni poslanci a v pravé pro každý klub vrchol předsedy a vrchol tajemníka. Hrany se natahají z těchto dvou vrcholů klubu do každého člena toho klubu. Graf se pak klasicky doplní na síť s jednotkovými kapacitami, najde se maximální tok a pozice se pak obsadí podle těch hran, kterými tok teče.

3. Základní myšlenka je taková, že když z kružnice odeberu nejvrchnější a nejspodnější bod, stanou se mi z ní dva oblouky, což už je skoro identická úloha. Stačí tedy zametat shora dolů a když najdeme vršek kružnice, vložíme si do průřezu odkazy na K_levá a K_pravá. Na spodku kružnice je pak samozřejmě zase zahodíme.
   Tohle už funguje v podstatě identicky s průniky přímek, s tím rozdílem že dva oblouky mohou mít dva společné průsečíky. To ošetřím tak, že a) když najdu průsečíky dvou oblouků, naplánuji si do kalendáře jenom ten nejvrchnější, a b) když narazím na průsečík, musím další průsečíky hledat i v té dvojici, kterou jsem právě prohodil.