# Zk 15.9.2005

<{ForumPost(poster="Tacoud", timestamp=2005-09-16 09:09:43)}>
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]
<{/ForumPost}>