Zk 15.9.2005

1. Dokažte nebo vyvraťte: Pokud do červeno-černého stromu vložíte nějaký uzel a hned vzápětí ho vyjmete, tak strom bude vypadat stejně jako před vložením onoho uzlu.

2. Dokažte nebo vyvraťte: Pokud v nějakém orientovaném grafu existuje orientovaná cesta z vrcholu x do vrcholu y a vrchol x bude pomocí DFS odhalen dříve než vrchol y, tak to znamená, že vrchol y bude následníkem vrcholu x v DFS stromě.

3. Je dán orientovaný graf a každé hraně je přiřazena hodnota "spolehlivosti" s(x). Spolehlivost udává, jaká je šance, že daná hrana "neselže". Hodnoty spolehlivosti pro každou hranu x jsou 0<=s(x)<=1. Spolehlivost pro cestu z A do B se vypočítá jako součin spolehlivostí všech hran na této cestě. Vymyslete algoritmus s co nejlepší časovou složitostí, který najde nejspolehlivější cestu z vrcholu X do nějakého vrcholu Y.

Řešení:

1. Neplatí

2 . Neplatí - tady hodně lidí - včetně mě - naletělo na to, že DFS může projet některé vrcholy na cestě z X od Y ještě než objeví X (DFS není spuštěno z X).

3. Modifikovaný Dijkstra, vybírá maximum místo minima. Hodně lidem strhli body za to, že nenapsali, že všechny hrany mají nezápornou hodnotu a tudíž lze Dijkstru použít.
   [/code]