# zkouska 30.6 Hric

<{ForumPost(poster="Jakobicek", timestamp=2006-06-30 11:16:49)}>
po pisemce jsem byl smutny  :cry:  
zadani  
1a. popsat RB-tree insert  
1b. definuj B-strom  
2.LU-dekompozice tridiagonalni ctrvercove matice radu 4 +vyresit soustvu pomoci LU rozkladu  
ted proc jsem byl smutny  
3.graf s ruzne ohodnocenymi hranami  
3a...spravnost boruvkova algoritmu neboli sjednoceni vsech lehkych hran pres vsechny rezy tvori v grafu s ruzne ohodnocenymi hranami min.kostru--- pokud mate nekdo pekny dukaz postnete ho sem...  :cry:   
ten muj co visi o par threadu dal stoji za houby :wink:   
3b.jednoznacnost jarnikova algoritmu v grafu s prostou vahovou fci  
toto neni tezke.. je treba vedet ze vybirame vzdy lehkou hranu pro rez mezi dosud otevrenymi a jiz zpracovanymi vrcholy...   
lehka hrana je pro dany rez za predpokladu proste vahove funkce prave jedna  
pisemka az na treti priklad nebyla prilis narocna  
na ustni je mozna dobre jit az po obede   
/*syty hric je lepsi nez hladovy hric*/  
ja jsem dostal silne souvisle komponenty   
hric nijak zvlaste nestoural jen se zeptal jakou slozitost ma usporadani vrcholu podle casu uzavreni... O(V)  
a na neco cemu jsem prilis nerozumel... souviselo to s casy uzavreni  
kamarada po me se ptal na to jak se u floyd-warshallova algoritmu zjisti jestli graf obsahuje zaporne cykly... na diagonale budou zaporna cisla  
oba jsme dostali za jedna :)
<{/ForumPost}>

<{ForumPost(poster="Veslar", timestamp=2006-07-01 21:45:55)}>
Mno neda mi to abych si rypnul. Nechapu jak si mohl byt smutny, kdyz si dostal 1 :P Takove lidi mam rad :P  
  
Mno k tomu 3a....jelikoz me to uznal tak jsem to mel snad dobre :] Nejdriv jsem to chtel dokazat tak, ze kdyz si ty rezy spravne usporadam tak nic nepokaizm. Nejdriv jsem si je usporadal tak, jak by je vzal Prim-Jarnikuv alg....ale pak se muselo resit strasne moc pripadu, aby si dokazal, ze ostatni rezy urcite nepridaji nejakou hranu, kterou by Prim-Jarnik nepridal.   
Takze jsem to zaskrtal.  
Mno a tedka k reseni ktere jsem tam nechal napsane : Nejdriv reknes, ze kazdy rez urcite respektuje nejakou podmnozinu minimalni kostry. To je zcela jiste pravda \[ to jsem tam ani nedokazoval a ani to po me nechtel ].  
Mno a jelikoz mela kazda hrana jine ohodnoceni, tak je minimalni kostra jednoznacne urcena \[popravde receno jsem si tim nebyl AZ tak jisty, ze jich tam naaahodou nemuze byt vic, ale nechtel se po me dukaz :] Mno a pak uz to je jednoduche. Pouzije se ta veta \[tam uz jsem dukaz napsal], ktera rika, ze kdyz je F podmnozina hran nejake minimalni kostry a S je rez, ktery respektuje F, tak F U {u,v} je zase podmnozina minimalni kostry \[kde u,v je lehka hrana pro rez S]. \[viz slajdy].
<{/ForumPost}>

<{ForumPost(poster="Jakobicek", timestamp=2006-07-02 09:18:24)}>
jen si rypni... si to zaslouzim... :!:  chtel jsem tu cast o smutku po ustni vymazat ale neudelal jsem to prave proto abych mohl byt po zasluze flamovan    
smutny jsem byl jen po pisemce... po ustni pochopitelne uz ne :wink:   
3a jsem totiz dokazoval nebo se o to spise pokousel zhruba pred 14 dny a na zkousce jsem si nebyl schopen vzpomenout co ze jsem to vlastne tehdy delal... pokus o par threadu zpet... jinak tvuj dukaz vypada smysluplne  
tvrzeni, ze prosta vahova fce urcuje min. kostru jednoznacne, plati   
jenom si nejsem jisty jak dokazat ze ta mnozina tvori vubec nejakou kostru ... ale asi to opravdu vyplyva z te vety na prednasce
<{/ForumPost}>