AVL strom: Postupným vkládáním prvků \(42,13,2,16,32\) do prázdného stromu vznikne AVL-strom. Kolik rotací se celkem provedlo (dvojité rotace jsou započteny jako jedna rotace)?

AVL strom: Postupným vkládáním prvků \(42,13,2,16,32\) do prázdného stromu vznikne AVL-strom. Vypište posloupnost hodnot vrcholů, které se staly v průběhu vkládání nevyvážené. Jednotlivé hodnoty oddělujte čárkou a mezerou.

AVL strom: Postupným vkládáním prvků \(42,13,2,16,32\) do prázdného stromu vznikne AVL-strom. Vypište zleva doprava listy výsledného AVL-stromu.

Binární halda: Je daná halda o \(n= 67\) prvcích. Kolik obsahuje listů a kolik hladin? Výsledek uveďte jako dvojici čísel LISTY, HLADINY oddělené čárkou a mezerou.

Binomiální halda: Vypište uspořádanou posloupnost řádů stromů \(\cal{T}\) binomiální haldy, která obsahuje \(n = 141\) prvků.

Co lze říci o nejkratší cestě a nejkratším sledu z vrcholu 1 do vrcholu 8 v následujícím grafu?

Do AVL stromu na obrázku pomocí volání AVLInsert postupně vložíme prvky \(63,91,65,79\). Následně pomocí AVLDelete postupně smažeme prvky \(72,75\). Vypište zleva doprava pro výsledný AVL strom všechny prvky na 2. hladině (ve vzdálenosti 2 od kořene) ve formě čísel oddělených čárkou a mezerou. Pokud se Vám nedaří najít správné rotace, podívejte se do cvičebnice, kde si řešení úlohy můžete postupně odladit.

Do AVL stromu na obrázku pomocí volání AVLInsert postupně vložíme prvky \(87,66,21,33\). Následně pomocí AVLDelete postupně smažeme prvky \(81,73\). Vypište zleva doprava pro výsledný AVL strom všechny prvky na druhé hladině (tj. ve vzdálenosti 2 od kořene) ve formě čísel oddělených čárkou a mezerou.

Do AVL stromu na obrázku pomocí volání AVLInsert postupně vložíme prvky \(87,71,38,42\). Následně pomocí AVLDelete postupně smažeme prvky \(83,78\). Vypište všechny prvky na třetí hladině (ve vzdálenosti 3 od kořene) zleva doprava pro výsledný AVL strom ve formě čísel oddělených čárkou a mezerou.

Do binárního vyhledávacího stromu byly postupně vloženy tyto prvky: \(13, 5, 1, 10, 18, 17, 15, 16\). (Pomocí BVSInsert, se stromem nebyly prováděny žádné jiné operace.) Vypište zleva doprava hodnoty všech listů v tomto stromě poté, co byla pomocí BVSDelete smazána hodnota 13. Hodnoty oddělujte čárkou a mezerou.

Do binárního vyhledávacího stromu byly postupně vloženy tyto prvky: \(13, 5, 1, 10, 18, 17, 15, 16\). Vypište hodnotu druhého listu zleva.

Do binárního vyhledávacího stromu byly postupně vloženy tyto prvky: \(9,4,2,6,5,8,42,13,21\). Vypište hodnotu třetího listu zprava.

Graf \(G= (V,E)\) je strom obsahující přesně 100 vrcholů, z toho je přesně 10 listů. Určete maximální možný stupeň libovolného vrcholu tohoto stromu.

Graf \(G= (V,E)\) je strom obsahující přesně 100 vrcholů, z toho je přesně 20 listů. Určete maximální možný stupeň libovolného vrcholu tohoto stromu.

Graf \(G=(V,E)\) je strom obsahující přesně 100 vrcholů, z toho je přesně 15 listů. Určete maximální možný stupeň libovolného vrcholu tohoto stromu.

Hledáme délky nejkratších cest z vrcholu \(a\) v následujícím grafu algoritmem Relaxace z přednášky. Na začátku položíme pro všechny vrcholy \(h(v)=+\infty\) a označíme je jako nenalezené. Pak nastavíme \(h(a)=0\) a označíme \(a\) jako otevřený. Kolika způsoby lze postupně vybrat \(4\) (v tu chvíli) otevřené vrcholy tak, že po jejich relaxaci (a uzavření) bude pro každý vrchol \(v\) v grafu hodnota \(h(v)\) udávat délku nejkratší cesty z \(a\) do \(v\) v zadaném grafu? Uveďte počet způsobů a jeden takový způsob oddělené čárkami, např: \(25, b, a, c, a\).

Hledáme délky nejkratších cest z vrcholu \(a\) v následujícím grafu algoritmem Relaxace z přednášky. Na začátku položíme pro všechny vrcholy \(h(v)=+\infty\) a označíme je jako nenalezené. Pak nastavíme \(h(a)=0\) a označíme \(a\) jako otevřený. Kolika způsoby lze postupně vybrat \(5\) (v tu chvíli) otevřených vrcholů tak, že po jejich relaxaci (a uzavření) bude pro každý vrchol \(v\) v grafu hodnota \(h(v)\) udávat délku nejkratší cesty z \(a\) do \(v\) v zadaném grafu? Uveďte počet způsobů a jeden takový způsob oddělené čárkami, např: \(25, b, a, c, a, b\).

Je dán graf \(G=(V,E)\), pro který platí \[|E|=2|V|+2.\] Graf \(G\) má 8 vrcholů stupně 5 a ostatní vrcholy jsou stupně 2. Kolik vrcholů graf \(G\) obsahuje? (V případě, že graf s požadovanými vlastnostmi neexistuje, napište 0)

Je dán graf \(G=(V,E)\), pro který platí \[|E|=2|V|+24.\] Graf \(G\) má 6 vrcholů stupně 3 a ostatní vrcholy jsou stupně 5. Kolik vrcholů graf \(G\) obsahuje? (V případě, že na otázku nelze odpovědět, napište 0)

Je dán graf \(G=(V,E)\), pro který platí \[|E|=2|V|+85.\] Graf \(G\) má 17 vrcholů stupně 2 a ostatní vrcholy jsou stupně 5. Kolik vrcholů graf \(G\) obsahuje? (V případě, že na otázku nelze odpovědět, napište 0)

Je dán následující graf \(G\), kde jsou hranám přirazeny váhy. Vypište hrany v pořadí takovém, jak je vypíše algoritmus MinKostraKruskal. Výstup vypište jako posloupnost hran (množina dvojice vrcholů), menší z vrcholů hrany vždy první. Vše oddělujte čárkou a mezerou, množiny obalujte množinovými závorkami. Například výpis prvních 5 hran bude vypadat například takto \(\{1,2\},\{3,4\},\{5,6\},\{7,8\},\{10,11\}\). Stačí vložit správná čísla do následující šablony: { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }.

Je dán následující graf \(G\), kde jsou hranám přirazeny váhy. Vypište hrany v pořadí takovém, jak je vypíše algoritmus MinKostraKruskal. Výstup vypište jako posloupnost hran (množina dvojice vrcholů). Vše oddělujte čárkou a mezerou, množiny obalujte množinovými závorkami. Například výpis prvních 5 hran bude vypadat například takto \(\{1,2\},\{3,4\},\{5,6\},\{7,8\},\{10,11\}\). Stačí vložit správná čísla do následující šablony: { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }.

Je dán následující graf \(G\), kde jsou hranám přirazeny váhy. Vypište hrany v pořadí takovém, jak je vypíše algoritmus MinKostraKruskal. Výstup Kruskala vypište jako množinu dvojic vrcholů, vše oddělujte čárkou a mezerou, množiny obalujte množinovými závorkami. Tj. výpis prvních 5 hran pro Krukala bude vypadat například takto \(\{1,2\},\{3,4\},\{5,6\},\{7,8\},\{10,11\}\). Stačí vložit správná čísla do následující šablony: { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }, { , }.

Je dán následující graf \(G\), kde váhy hran jsou dané jako minimum z čísel vrcholů, tj. pro každé \(\{u,v\}\in E(G)\), \(w(\{u,v\}) = \min \{u,v\}\). Určete váhu minimální kostry grafu \(G\) a počet koster s touto váhou, které v grafu existují. Výsledek zapište jako dvojici čísel VÁHA, POČET oddělených čárkou a mezerou.

Je dáno pole s 16 uloženými prvky: \(21,11,4,29,21,29,25,5,24,18,3,15,20,14,4,18\). Pomocí HeapBuild z přednášky vytvořte z těchto hodnot minimovou binární haldu (reprezentovanou) v poli. Na tuto haldu zavolejte HeapExtractMin z přednášky a poté vložte prvek \(23\) pomocí přednáškového HeapInsert a nakonec ještě jednou HeapExtractMin. Vypište obsah pole po provedení poslední z výše jmenovaných operací ve formátu jako je zadán vstup, tj. jako posloupnost čísel oddělených čárkou a mezerou.

Je dáno pole s 18 uloženými prvky: \(26, 23, 6, 19, 16, 25, 14, 7, 18, 27, 3, 2, 17, 21, 5, 29, 10, 2\). Pomocí HeapBuild z přednášky vytvořte z těchto hodnot minimovou binární haldu (reprezentovanou) v poli. Na tuto haldu zavolejte 2x HeapExtractMin z přednášky a poté vložte prvek \(11\) a následně prvek \(4\) pomocí přednáškového HeapInsert. Vypište obsah pole po provedení poslední z výše jmenovaných operací ve formátu jako je zadán vstup, tj. jako posloupnost čísel oddělených čárkou a mezerou.

Je dáno pole s 23 uloženými prvky: \(27,25,14,7,28,18,23,16,28,12,20,2,28,23,8,23,29,11,17,13,16,19,27\). Pomocí HeapBuild z přednášky vytvořte z těchto hodnot minimovou binární haldu (reprezentovanou) v poli. Na tuto haldu zavolejte 3x HeapExtractMin z přednášky a poté vložte prvek \(23\) pomocí přednáškového HeapInsert. Vypište obsah pole po provedení poslední z výše jmenovaných operací ve formátu jako je zadán vstup, tj. jako posloupnost čísel oddělených čárkou a mezerou. Pokud máte více možností prohození při opravování haldy, vybírejte si konzistentně pravého nebo levého syna.

Je dáno pole s uloženými 17 prvky: \(5,21,5,19,3,5,15,22,21,1,1,28,24,11,30,10,13\). Pomocí HeapBuild z přednášky vytvořte z těchto hodnot minimovou binární haldu v poli. Na tuto haldu zavolejte 3x HeapExtractMin z přednášky a poté vložte prvek \(2\) podle přednáškového HeapInsert. Vypište obsah pole po provedení poslední z jmenovaných operací ve formátu jako je zadán vstup, tj. jako posloupnost čísel oddělených čárkou a mezerou.

Je dáno pole s uloženými 19 prvky: \(10,29,13,10,3,16,6,25,16,9,27,3,16,14,29,7,29,16,2\). Pomocí HeapBuild z přednášky vytvořte z těchto hodnot minimovou binární haldu v poli. Na tuto haldu zavolejte 2xHeapExtractMin z přednášky a poté vložte prvek \(7\) podle přednáškového HeapInsert. Vypište obsah pole po provedení poslední z jmenovaných operací ve formátu jako je zadán vstup, tj. jako posloupnost čísel oddělených čárkou a mezerou.

Je daná binomiální halda s \(2018\) prvky. Vypište počty vrcholů na 2. hladině (ve vzdálenosti 2 od kořene) u jednotlivých binomiálních stromů v posloupnosti \(\cal T\) jako posloupnost čísel oddělených čárkou a mezerou. Pořadí čísel je dané pořadím stromů v posloupnosti \(\cal T\). Dále, pokud strom nemá na 2. hladině žádný prvek, napište 0. (Například halda s 11 prvky je složena ze tří stromů, řády jsou 0, 1 a 3, počet prvků na 2. hladině je u jednotlivých stromů postupně 0, 0 a 3)

Jsou dány následující dvě binomiální haldy. Slijte tyto haldy pomocí BHMerge(h1,h2) z přednášek a následně z výsledné haldy odeberte minimum podle BHExtractMin. Vypište hodnoty klíčů uložené v kořenech stromů výsledné haldy. Jednotlivé klíče oddělte čárkou a mezerou, pořadí odpovídá pořadí stromů v \(\cal{T}\).

Kolik automorfismů má následující graf s 35 vrcholy a 35 hranami? Vrcholy jsou značeny jako černá kolečka a hrany jako černé čáry. Odpověď zadejte jako celé číslo.

Kolik automorfismů má následující graf?

Kolik hran má graf \(K_{3,4,5}\)?

Kolik koster má graf na obrázku?

Kolik minimálně a kolik maximálně má vrcholů AVL strom \(T\) o 13 hladinách? Výsledek zapište jako dvojici čísel \(minT\), \(maxT\).

Kolik neizomorfních koster má graf \(C_6\) s jednou tětivou (hrana, která propojuje vrcholy, jež by na kružnici měly vzdálenost 3)?

Kolik neizomorfních koster má graf \(K_6\)?

Kolik nejvíce (neprázdných) hladin může mít AVL strom s \(2023\) vrcholy?

Kolik nejvíce a kolik nejméně komponent souvislosti může mít graf s 31 vrcholy a 90 hranami? Výsledek zapište jako dvojici čísel MAX, MIN oddělených čárkou a mezerou.

Kolik nejvíce komponent souvislosti může mít graf s 21 vrcholy a 73 hranami?

Kolik nejvíce stromů má les vzniklý z grafu \(K_{10}\), kterému odebereme 40 hran?

Kolik skoromediánů obsahuje posloupnost dvaceti čísel 2, 8, 11, 6, 13, 12, 12, 7, 14, 12, 15, 13, 6, 10, 6, 1, 6, 9, 6, 6?

Kolik skoromediánů obsahuje posloupnost dvaceti čísel \[4, 8, 11, 5, 14, 13, 13, 7, 15, 13, 16, 14, 5, 11, 5, 3, 5, 9, 5, 5?\] Vypište je bez opakování. Odpověď zapište ve tvaru POCET_SKOROMEDIANU:SEZNAM_SKOROMEDIANU, kde skoromediány v SEZNAMu budou seřazené od nejmenšího po největší a oddělené čárkama. Například odpověď 5:7,8 znamená, že posloupnost obsahovala 5 skoromediánů a to s dvěma hodnotama (7 a 8).

Máme hešovací tabulku s otevřeným adresováním. Co se stane, pokud při provádění některé z operací narazíme na náhrobek?

Máme prázdnou hešovací tabulku velikosti 13 (přihrádky označené \(0,\ldots, 12\)) a chceme do ní zahešovat čísla \(8, 1, 21, 47, 3, 42\) (v tomto pořadí). Použijeme dvojité hešování s otevřeným adresováním. Hešovací funkce je dána předpisem \(h(k,i) = (k + i \cdot (1 + (k \bmod 7))) \bmod 13\). Určete počet kolizí.

Máme prázdnou hešovací tabulku velikosti 13 (přihrádky označené \(0,\ldots, 12\)) a chceme do ní zahešovat čísla \(8, 1, 21, 47, 3, 42\) (v tomto pořadí). Použijeme dvojité hešování s otevřeným adresováním. Hešovací funkce je dána předpisem \(h(k,i) = (k + i \cdot (1 + (k \bmod 7))) \bmod 13\). Vypište prvky, při jejichž vložení nastala kolize v pořadí, jak byly vkládány, oddělené čárkou a mezerou (pokud po kolizi prvek potřeboval více pokusů vložení, zapište ho jen jednou).

Máme prázdnou hešovací tabulku velikosti 13 (přihrádky označené \(0,\ldots, 12\)) a chceme do ní zahešovat čísla \(8, 1, 21, 47, 3, 42\) (v tomto pořadí). Použijeme dvojité hešování s otevřeným adresováním. Hešovací funkce je dána předpisem \(h(k,i) = (k + i \cdot (1 + (k \bmod 7))) \bmod 13\). Vypište obsah tabulky po vložení všech čísel jako posloupnost čísel oddělených čárkou v pořadí od přihrádky 0 po přihrádku 12. Pokud je příslušná přihrádka prázdná, napište na příslušné místo v posloupnosti "-".

Máme prázdnou hešovací tabulku velikosti 13 (přihrádky označené \(0,\ldots, 12\)), používáme dvojité hešování s otevřeným adresováním s náhrobky a hešovací funkci danou předpisem \(h(k,i)= (6\cdot k + i \cdot((3\cdot k) \bmod 5+1))\bmod 13\). Do tabulky postupně voláním OpenInsert zahešujeme klíče 12,64,32,38,44,26. Následně postupně zavoláme OpenDelete na klíče 32, 12. Nakonec postupně zavoláme OpenInsert na klíče 31, 13. Vypište obsah tabulky po dokončení všech operací jako posloupnost čísel oddělených čárkou v pořadí od přihrádky 0 po přihrádku 12. Pokud je příslušná přihrádka prázdná, napište na příslušné místo v posloupnosti "-", pokud obsahuje náhrobek napište na příslušné místo v posloupnosti "t".

Máme prázdnou hešovací tabulku velikosti 17 (přihrádky označené \(0,\ldots, 16\)) a chceme do ní zahešovat čísla 25, 22, 46, 92, 63, 8, 82, 34, 6, 75, 58, 21, 7, 15, 29, 88 (v tomto pořadí). Použijeme dvojité hešování s otevřeným adresováním. Hešovací funkce je dána předpisem \(h(k,i)= 7\cdot k + i \cdot(3\cdot k \bmod 7+1)\bmod 17\). Vypište obsah tabulky po vložení všech čísel jako posloupnost čísel oddělených čárkou v pořadí od přihrádky 0 po přihrádku 16. Pokud je příslušná přihrádka prázdná, napište na příslušné místo v posloupnosti "-".

Máme prázdnou hešovací tabulku velikosti 17 (přihrádky označené \(0,\ldots, 16\)), používáme dvojité hešování s otevřeným adresováním s náhrobky a hešovací funkci danou předpisem \(h(k,i)= (5\cdot k + i \cdot((3\cdot k) \bmod 7+1))\bmod 17\). Do tabulky postupně voláním OpenInsert zahešujeme klíče 12,54,99,33,52,37. Následně postupně zavoláme OpenDelete na klíče 33 a 99. Nakonec postupně zavoláme OpenInsert na klíče 27 a 16. Vypište obsah tabulky po dokončení všech operací jako posloupnost čísel oddělených čárkou v pořadí od přihrádky 0 po přihrádku 16. Pokud je příslušná přihrádka prázdná, napište na příslušné místo v posloupnosti "-", pokud obsahuje náhrobek napište na příslušné místo v posloupnosti "t".

Máme prázdnou hešovací tabulku velikosti 17 (přihrádky označené \(0,\ldots, 16\)), používáme dvojité hešování s otevřeným adresováním s náhrobky a hešovací funkci danou předpisem \(h(k,i)= (6\cdot k + i \cdot((4\cdot k) \bmod 7+1))\bmod 17\). Do tabulky postupně voláním OpenInsert zahešujeme klíče 12, 62, 46, 45, 20, 11. Následně postupně zavoláme OpenDelete na klíče 20, 62. Nakonec postupně zavoláme OpenInsert na klíče 22, 30, 11. Vypište obsah tabulky po dokončení všech operací jako posloupnost čísel oddělených čárkou v pořadí od přihrádky 0 po přihrádku 16. Pokud je příslušná přihrádka prázdná, napište na příslušné místo v posloupnosti "-", pokud obsahuje náhrobek napište na příslušné místo v posloupnosti "t".

Máme prázdnou hešovací tabulku velikosti 17 (přihrádky označené \(0,\ldots, 16\)), používáme dvojité hešování s otevřeným adresováním s náhrobky a hešovací funkci danou předpisem \(h(k,i)= (6\cdot k + i \cdot((4\cdot k) \bmod 7+1))\bmod 17\). Do tabulky postupně voláním OpenInsert zahešujeme klíče 19, 69, 53, 52, 27, 18. Následně postupně zavoláme OpenDelete na klíče 27, 69. Nakonec postupně zavoláme OpenInsert na klíče 29, 37, 18. Vypište obsah tabulky po dokončení všech operací jako posloupnost čísel oddělených čárkou v pořadí od přihrádky 0 po přihrádku 16. Pokud je příslušná přihrádka prázdná, napište na příslušné místo v posloupnosti "-", pokud obsahuje náhrobek napište na příslušné místo v posloupnosti "t".

Máme prázdnou hešovací tabulku velikosti 17 (přihrádky označené \(0,\ldots,16\)) a chceme do ní zahešovat čísla \(5,3,42,93,22,25,37, 59\) (v tomto pořadí). Použijeme hešování s řetízky pro hešovací funkci dánou předpisem \( h(x) = 7\cdot x \bmod 17\). Vypište nejdelší vzniklý řetízek v tabulce po vložení posledního prvku, a to od posledně vložené hodnoty po první. Hodnoty oddělujte čárkou a mezerou.

Máme randomizovaný algoritmus a nějaký jeho vstup takový, že v něm tento algoritmus nalezne hledaný objekt s pravděpodobností přesně \(\frac{1}{512}\). S jakou pravděpodobností nalezneme hledaný objekt, zopakujeme-li tento algoritmus nad tímto vstupem nezávisle 512-krát? (Odpověd uveďte zaokrouhlenou na 6 desetinných míst a k oddělení desetinných míst použijte čárku – např. 0,123456.)

Máte kód BubbleSortu pro setřídění pole \(A[1], \dots, A[6]\): bublal = true while (bublal) do bublal = false for j = 1 to n-1 do if (A[j] > A[j+1]) then prohod(A[j+1],A[j]) bublal = true Vymyslete vstup na prvcích \(1,2,\dots, 6\) tak, aby v průběhu třídění proběhlo přesně jedno prohození prvků.

Mějme následující rekurzivní funkci \(moon\). (Lomítko je celočíselné dělení.) Vyberte z nabízených možností všechny, které vyjadřují asymptotickou časovou složitost volání \(moon(1,n)\). moon(x,y) if (x < y) then { j = (y - x) * (y - x) while (j > 0) do j-- moon(x,(x+y)/2) }

Mějme neorientovaný graf, kde každý vrchol odpovídá jednomu políčku šachovnice \(8 \times 8\). Dva vrcholy jsou sousední pravě tehdy, když jezdec (kůň) může přeskočit z jednoho odpovídajícího políčka na druhé. Kolik má tento graf hran? Pohyb jezdce je takový, že se vždy nejprve přesune o dvě pole svisle nebo vodorovně a poté ještě o jedno pole kolmo na původní směr — cesta pripomíná písmeno \(L\).

Maximální binomiální halda: Vypište posloupnost řádů stromů \(\cal{T}\) binomiální haldy, která vznikne slitím BHMerge(h1,h2) dvou hald na obrázku. Jednotlivé čísla oddělte čárkou a mezerou, pořadí odpovídá pořadí stromů v \(\cal{T}\).

Maximální binomiální halda: Vypište posloupnost hodnot (klíčů) uložených v kořenech stromů \(\cal{T}\) binomiální haldy, která vznikne slitím BHMerge(h1,h2) dvou hald na obrázku. Jednotlivé hodnoty oddělte čárkou a mezerou, pořadí odpovídá pořadí stromů v \(\cal{T}\).

Minimální binární halda: Je daná posloupnost \(n\) prvků uložených v poli: \(10,5,3,8,11,3,1,2,5,2\). Zavolejte HeapBuild a poté HeapExtractMin. Napište ve stejném formátu (čísla oddělená čárkou a mezerou) výsledek po zavolání operace HeapExtractMin.

Minimální binární halda: Je daná posloupnost \(n\) prvků uložených v poli: \(10,5,3,8,11,9,1,2,5,4\). Napište ve stejném formátu (čísla oddělená čárkou a mezerou) výsledek po zavolání operace HeapBuild.

Na následující graf pustíme přednáškový BFS algoritmus z vrcholu 42. U algoritmu se sousedi vrcholů vždy prochází v pořadí rostoucích čísel vrcholů tj. od souseda s nejmenším číslem. Určete, které vrcholy budou ve frontě po uzavření všech vrcholů ve vzdálenosti 2 od vrcholu 42 (na konci fáze \(F_2\)). Řešení uveďte v takovém pořadí, v jakém jsou uloženy ve frontě, jako poslopnout čísel oddělených čárkou a mezerou.

Na následující graf pustíme přednáškový DFS a BFS algoritmus z vrcholu 1. U obou algoritmů se sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů (tj. od souseda s nejmenším číslem). Pro každý z algoritmů určete první uzavřený vrchol (tj. ten, který se jako první stane uzavřený) a vrchol, který se jako poslední stane otevřený (tzn. ten vrchol, který bude algoritmem jako poslední označen jako otevřený). Řešení uveďte jako čtveřici čísel: DFS-prvni-uzavreny, DFS-posledni-otevreny, BFS-prvni-uzavreny, BFS-posledni-otevreny (oddělených čárkou a mezerou).

Na následující graf pustíme přednáškový DFS a BFS algoritmus z vrcholu 52. U obou algoritmů sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů tj. od souseda s nejmenším číslem. Pro každý z algoritmů určete, který vrchol se jako poslední stane otevřený (tzn. ten vrchol, který bude algoritmem jako poslední označen jako "otevřený"), první uzavřený vrchol a poslední uzavřený vrchol (tj. ten, který se jako poslední stane uzavřený). Řešení uveďte jako šestici čísel DFS_posl_otevren, DFS_prvni_uzavren, DFS_posl_uzavren, BFS_posl_otevren, BFS_prvni_uzavren, BFS_posl_uzavren, oddělených čárkou a mezerou.

Na následující graf pustíme přednáškový DFS a BFS algoritmus z vrcholu 65. U obou algoritmů sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů tj. od souseda s nejmenším číslem. Pro každý z algoritmů určete, který vrchol se jako poslední stane otevřený (tzn. ten vrchol, který bude algoritmem jako poslední označen jako "otevřený"), první uzavřený vrchol a poslední uzavřený vrchol (tj. ten, který se jako poslední stane uzavřený). Řešení uveďte jako šestici čísel DFS_posl_otevren, DFS_prvni_uzavren, DFS_posl_uzavren, BFS_posl_otevren, BFS_prvni_uzavren, BFS_posl_uzavren, oddělených čárkou a mezerou.

Na následující graf pustíme přednáškový DFS algoritmus z vrcholu 42. U algoritmu se sousedi vrcholů vždy prochází v pořadí rostoucích čísel vrcholů tj. od souseda s nejmenším číslem. Určete, kterých 5 vrcholů se uzavře (přejde do stavu uzavřen) jako první. Řešení uveďte v takovém pořadí, v jakém jsou uzavírány, a jako poslopnout čísel oddělených čárkou a mezerou.

Najděte nějakou nejdelší rostoucí podposloupnost následující posloupnosti: 75, 48, 95, 13, 71, 67, 60, 88, 15, 10, 50, 63, 2, 12, 43, 91, 27, 45, 34, 30. Výslednou podposloupnost vypište jako čísla oddělená čárkou.

Najděte nějakou nejdelší rostoucí podposloupnost následující posloupnosti: 78, 53, 76, 49, 65, 8, 1, 43, 45, 5, 84, 10, 0, 17, 22, 66, 46, 59, 35, 74. Výslednou podposloupnost vypište jako čísla oddělená čárkou.

Najděte nějakou nejdelší rostoucí podposloupnost následující posloupnosti: 90, 65, 88, 61, 77, 20, 13, 55, 57, 17, 96, 22, 10, 29, 34, 78, 58, 71, 47, 86. Výslednou podposloupnost vypište jako čísla oddělená čárkou.

Najděte nějakou nejdelší rostoucí podposloupnost následující posloupnosti: \[76, 53, 95, 23, 71, 69, 60, 89, 25, 11, 56, 66, 8, 77, 19, 45, 91, 27, 48, 34, 33.\] Výslednou podposloupnost vypište jako čísla oddělená čárkou.

Nechť \((\Omega,P)\) je diskrétní pravděpodobnostní prostor a \(|\Omega|\ge 2\). Pak určitě platí:

Nechť \(x\) a \(y\) jsou dva různé pevně zvolené vrcholy grafu \(K_{5,3}\), které nejsou spojeny hranou. Kolik cest délky 4 existuje v grafu \(K_{5,3}\) z vrcholu \(x\) do vrcholu \(y\)? V případě, že možných odpovědí je více v závislosti na konkrétní volbě \(x\) a \(y\), uveďte je všechny jako výčet oddělený čárkami (na pořadí a mezerách nezáleží).

Postupným vkládáním prvků 7, 4, 1, 5, 6, 2, 3, 9, 8 (v tomto pořadí) do prázdného AVL stromu pomocí AVLInsert dle přednášky vznikne vyvážený binární vyhledávací strom. Vypište zleva doprava všechny jeho listy jako posloupnost čísel oddělených čárkou a mezerou.

Pro úplný tripartitiní graf \(K_{1,1,2}\) určete počet podgrafů na 4 vrcholech, počet indukovaných podgrafů na libovolném počtu vrcholů a počet neizomorfních podgrafů na libovolném počtu vrcholů. Výsledek zapište jako trojici čísel POCETPODGRAFU, POCETINDUKOVANYCH, POCETNEIZOMORNICH v tomto pořadí oddělených čárkou a mezerou.

Pro řetězce \(x=\)automatyagramatiky a \(y=\)algoritmyagrafy najděte nejmenší editační vzdálenost \(L(x,y)\) a počty jednotlivých potřebných změn k získání řetezce \(y\) z řetězce \(x\). Výsledkem je tedy čtveřice čísel udávající po řadě editační vzdálenost, počet vložení nových znaků, počet smazání znaků, počet změn znaků. Jednotlivá čísla oddělte čárkou a mezerou. Například pro \(x=\)abba, \(y=\)cba je \(L(x,y) = 2\) a editace: abba (změna a na c) \(\rightarrow\) cbba (smazání b) \(\rightarrow\) cba. Tedy výstup vypadá takto: 2, 0, 1, 1.

Pro graf \(C_5\) určete počet podgrafů na pěti vrcholech, počet indukovaných podgrafů na libovolném počtu vrcholů a počet neizomorfních podgrafů na libovolném počtu vrcholů. Výsledek zapište jako trojici čísel POCETPODGRAFU, POCETINDUKOVANYCH, POCETNEIZOMORNICH v tomto pořadí oddělených čárkou (a mezerou).

Pro graf \(K_{2,3}\) určete počet podgrafů na pěti vrcholech, počet indukovaných podgrafů na libovolném počtu vrcholů a počet neizomorfních podgrafů na libovolném počtu vrcholů. Výsledek zapište jako trojici čísel POCETPODGRAFU, POCETINDUKOVANYCH, POCETNEIZOMORNICH v tomto pořadí oddělených čárkou (a mezerou).

Pro graf na obrázku spočtěte délky nejkratších cest z vrcholu 1 do ostatních. Výsledek zapište jako posloupnost délek těchto cest oddělených čárkou a mezerou, uspořádání je podle vrcholů tj. od 1 do 6. Délku nedosažitelného vrcholu zapište jako N.

Pro graf na obrázku spočtěte délky nejkratších cest z vrcholu 6 do ostatních. Výsledek zapište jako posloupnost délek těchto cest oddělených čárkou a mezerou, uspořádání je podle vrcholů tj. od 1 do 6. Pro nedosažitelný vrchol zapište místo délky "N".

Pro následující kód (lomítko je celočíselné dělení) vyberte z nabízených možností všechny, které vyjadřují jeho asymptotickou časovou složitost v nejhorším případě v závislosti na \(N\). i = N while (i > 0) do j = 5 i = i / 3 while (j < N) do j = j * 5

Pro následující kód vyberte z nabízených možností všechny, které vyjadřují jeho asymptotickou časovou složitost v závislosti na \(N\) v nejhorším případě. i = N while (i > 0) do j = 0 while (j * j < i) do j++ i = i-3

Určete maximální počet hran orientovaného grafu s 20 vrcholy.

Určete maximální počet hran neorientovaného grafu s 10 vrcholy a 3 komponentami.

Určete maximální počet hran nesouvislého neorientovaného grafu s 10 vrcholy.

Určete maximální počet hran orientovaného acyklického grafu s 10 vrcholy a 3 (slabě) souvislými komponentami.

Určete maximální počet hran orientovaného grafu s 12 vrcholy.

Určete minimální počet hran neorientovaného grafu s 10 vrcholy a 3 komponentami.

Určete počet všech koster grafu \(K_3\).

Určete počet všech nesouvislých neizomorfních indukovaných podgrafů grafu \(K_3\).

Určete počet všech podgrafů grafu \(K_3\).

Určete počet všech souvislých neizomorfních podgrafů grafu \(K_3\).

Určete počet všech souvislých neizomorfních indukovaných podgrafů grafu \(K_3\).

Určete pořadí, ve kterém se budou otevírat (tj. označovat jako "otevřený") vrcholy následujícího orientovaného grafu při procházení do hloubky, kdy se sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů a start je ve vrcholu 1. Řešení uveďte jako čísla vrcholů oddělená čárkami a mezerami.

Určete pořadí, ve kterém se budou otevírat (tzn. označovat jako "otevřený") vrcholy následujícího orientovaného grafu při procházení do šířky, kdy se sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů a start je ve vrcholu 1. Řešení uveďte jako čísla vrcholů oddělená čárkami a mezerami.

Určete pořadí, ve kterém se budou otevírat (tzn. označovat jako "otevřený") vrcholy následujícího orientovaného grafu při procházení do šířky, kdy se sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů a start je ve vrcholu 1. Řešení uveďte jako čísla vrcholů oddělená čárkami a mezerami.

Určete pořadí, ve kterém se budou otevírat (tzn. označovat jako "otevřený") vrcholy následujícího orientovaného grafu při procházení do šířky, kdy se sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů a start je ve vrcholu 1. Řešení uveďte jako čísla vrcholů oddělená čárkami a mezerami.

Určete pořadí, ve kterém se budou otevírat (tzn. označovat jako "otevřený") vrcholy následujícího orientovaného grafu při procházení do hloubky, kdy se sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů a start je ve vrcholu 1. Řešení uveďte jako čísla vrcholů oddělená čárkami a mezerami.

Určete pořadí, ve kterém se budou otevírat (tzn. označovat jako "otevřený") vrcholy následujícího orientovaného grafu při procházení do hloubky, kdy se sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů a start je ve vrcholu 1. Řešení uveďte jako čísla vrcholů oddělená čárkami a mezerami.

Určete pořadí, ve kterém se budou zavírat (tzn. označovat jako "zavřený") vrcholy následujícího orientovaného grafu při procházení do hloubky, kdy se sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů a start je ve vrcholu 1. Řešení uveďte jako čísla vrcholů oddělená čárkami a mezerami.

Určete pořadí, ve kterém se budou zavírat (tzn. označovat jako "zavřený") vrcholy následujícího orientovaného grafu při procházení do hloubky, kdy se sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů a start je ve vrcholu 1. Řešení uveďte jako čísla vrcholů oddělená čárkami a mezerami.

Určete pořadí, ve kterém se budou zavírat (tzn. označovat jako "zavřený") vrcholy následujícího orientovaného grafu při procházení do hloubky, kdy se sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů a start je ve vrcholu 1. Řešení uveďte jako čísla vrcholů oddělená čárkami a mezerami.

Uvažujte nesouvislý 2-regulární graf o 7 vrcholech. Pro tento graf určete počet podgrafů na 7 vrcholech a počet neizomorfních indukovaných podgrafů na 4 vrcholech. Výsledek zapište jako dvojici čísel POCETPODGRAFU, POCETINDUKOVANYCH v tomto pořadí oddělených čárkou (a mezerou).

V jaké vzdálenosti bude vrchol 4 u následujícího orientovaného grafu při procházení do šířky, kdy se sousedi vrcholů vždy procházejí v pořadí rostoucích čísel vrcholů a start je ve vrcholu 1. Pokud je vrchol 4 nedosažitelný, napište číslo -1.

Vyberte všechny možnosti, které definují graf \(G= (V,E)\) jako strom (ekvivalentní k definici). Tj. vyberte taková tvrzení, že každý strom splňuje příslušné tvrzení a každý graf, který splňuje příslušné tvrzení je strom.

Vypište jedno libovolné topologické uspořádání následujícího orientovaného grafu jako posloupnost vrcholů oddělených čárkou a mezerou. V případě, že topologické uspořádání neexistuje, napište 0.

Z následujících možností vyberte všechna pravdivá tvrzení o neorientovaném grafu s 10 vrcholy a 9 hranami:

Z následujících možností vyberte všechna pravdivá tvrzení o neorientovaném grafu s 12 vrcholy a 55 hranami:

Z následujících možností vyberte všechna pravdivá tvrzení o neorientovaném grafu s 30 vrcholy a 29 hranami:

Zjistěte nejmenší editační vzdálenost mezi řetězci \(\mathtt{x}=\mathtt{progtest}\) a \(\mathtt{y}=\mathtt{peklo}\). Vaše odpověď se bude skládat z minimální editační vzdálenosti a řetězce symbolicky (\(\mathtt{D}\)=mazání, \(\mathtt{I}\)=vložení, \(\mathtt{R}\)=změna) popisujícího provedené operace vedoucí ke srovnání řetězců, viz příklad níže. Například pro \(\mathtt{x}=\mathtt{abba}\), \(\mathtt{y}=\mathtt{cbad}\) je \(L(x,y)=3\) a editace: \(\mathtt{abba}\) (změna \(\mathtt{a}\) na \(\mathtt{c}\)) → \(\mathtt{cbba}\) (smazání \(\mathtt{b}\)) → \(\mathtt{cba}\) (vložení \(\mathtt{d}\)) → \(\mathtt{cbad}\). Tedy výstup vypadá takto: \(3, \mathtt{RDI}\).