Úkoly z Kombinatoriky a grafů, 3. série

Veškerá tvrzení precizně zdůvodněte.

(3.1) Do cíle dojelo n závodníků, bohužel se ztratily data kdo kdy dojel. Nicméně někteří závodníci si zapomatovali některé z ostatních závodníků, kteří dojeli do cíle až po nich (ale ne nutně všechny a ne jejich pořadí). Toto si můžeme znázornit pomocí orientovaného grafu. Navrhněte algoritmus, který dostane na vstupu orientovaný graf ţvzpomínek� závodníků a vypíše nejpřesnější možné pořadí. To znamená, že není-li možné mezi několika závodníky rozhodnout, který dojel dříve, měl by algoritmus vypsat, že závodníci obsadili (třeba) desáté až třinácté místo. Součástí řešení by měl být slovní popis algoritmu, důkaz správnosti, odhad časové a paměťové složitosti a program (nejlépe v pseudokódu, nebo chcete-li se s ním programovat …). Algoritmus musí být jasný i bez nahlížení do zdrojáku. Plný počet bodů bude za řešení v lineárním čase.

4 body

(3.2) Nechť R je relace na nějaké (nekonečné) množině neobsahující konečný cyklus. Dokažte, že R lze rozšířit na částečné uspořádání, tj. že existuje částečné uspořádání S takové, že R ⊆ S.

6 bodů