Zadani vypadalo priblizne takhle:
Dokazte nebo vyvratte: pokud do cerveno-cerneho stromu pridame prvek a vzapeti na to je jej zase vymazeme, vysledny strom bude shodny s puvodnim.
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):
Neplati, existuje protipriklad na trech vrcholech, ktery bude mit po dane uprave stejny tvar ale ruznou barevnost.
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.
Upraveny Dijkstra