skuska 29.5. Cepek

Návštěvník

skuska 29.5. Cepek

Příspěvek od Návštěvník »

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
Odpovědět

Zpět na „2006“