# Cepek 25.5.2018

<{ForumPost(poster="Joffrey", timestamp=2018-05-26 14:19:20)}>
Zadani vypadalo priblizne takhle:  
1) Dokazte nebo vyvratte: pokud do cerveno-cerneho stromu pridame prvek a vzapeti na to je jej zase vymazeme, vysledny strom bude shodny s puvodnim.  
2) Dokazte nebo vyvratte: Mame orientovany graf G a na nem orientovanou cestu z x do y, potom pokud pokud spustime libovolne DFS pak pokud DFS nalezne vrchol x drive nez y pak y bude v danem DFS strome (ne nutne primym) naslednikem x.  
3)Nalezeni nejspolehlivejsi cesty: Mame orientovany graf G a jeho hrany jsou ohodnocene 0<=s(u,v)<=1, kde s(u,v) je pravdepodobnost spolehlivosti hrany. Tyto pravdepodobnosti hran jsou na sobe nezavisle, tedy pravdepodobnost, ze dve libovolne hrany s(x,y) a s (u,v) budou spolehlive je rovna s(u,v) * s(x,y). Vymyslete co nejefektivnejsi algoritmus, ktery nalezne nejspolehlivejsi cestu. Urcete a dokazte slozitost+spravnost.  
  
U ustni jsem dostal minimalni kostry(definice + dokazat vetu ze slajdu + Jarnik-Prim, Boruvka-Kruskal; zkousejiciho muze zajimat i detailnejsi rozebrani casove slozitosti, popripade proc je algoritmus korektni)  
  
  
RESENI(ten kdo si chce zapocitat necht uz dal necte):  
1) Neplati, existuje protipriklad na trech vrcholech, ktery bude mit po dane uprave stejny tvar ale ruznou barevnost.  
2) Neplati, protipriklad x<=>z=>y, pokud bychom spustili DFS z bodu 'z', potom nalezneme nalezneme prvni x a potom y ale y nebude naslednikem x.  
3) Upraveny Dijkstra
<{/ForumPost}>