# skuska 29.5. Cepek

<{ForumPost(poster="Anonymous", timestamp=2007-05-29 13:10:18)}>
Zadanie z pisomky tak ako si ho pamatam... (No garancy:-)  
  
1. priklad - nejaka rekurencia, uz si to presne nepamatam, trebalo urcit thetu, teda horny a dolny odhad substituciou...  
  
2. priklad   
Dokazte alebo vyvratte: v AVL strome je dana cesta od vrcholu do nejakeho listu. Ta cesta rozdeluje strom na 3 casti: X - vsetky vrcholy stromu nalavo od cesty, Y - vrcholy na danej ceste, Z - vsetky vrcholy napravo od cesty.  
Pre vsetky x z X, pre vsetky y z Y, pre vsetky z zo Z plati ze kluc(x) je mensi rovny kluc(y) a to je mensie alebo rovne kluc(z)  
  
3. priklad  
Dokazte alebo vyvratte: Je dany orientovany graf a v nom vrchol u pre ktory plati ze jeho vstupny stupen a vystupny stupen je aspon 1 a graf neobsahuje slucky (z vrcholu a nemoze viest hrana do vrcholu a). Tvrdenie:  BFS podstrom ktory obsahuje vrchol u obsahuje aspon 2 vrcholy nezavisle na poradi v akom sa bfs na vrcholy pusta.  
  
a riesenie - na 2. a 3. priklad sa da najst protipriklad.   
3: a -> u -> b  ak pustim bfs najprv z vrcholu b, potom z vrcholu u a potom z vrcholu a tak dostanem 3 jednoprvkove dfs stromy
<{/ForumPost}>