AG1

Question 1

Zdroj v grafe

Answer 1

Zdroj je takový vrchol orientovaného grafu, do kterého nevede žádnáhrana.

Question 2

Neorientovaný graf

Answer 2

Neorientovaný grafje uspořádaná dvojice(V, E), kde

• V je neprázdná konečná množina vrcholů(nebo také uzlů),
• E je množina hran

Question 3

Izomorfismus grafů

Answer 3

Nechť G a H jsou dva grafy.
Funkce f:V(G)→V(H) je izomorfismus grafů G a H, pokud f je bijekce a pro každou dvojici vrcholů u, v z V(G) platí {u, v}∈E(G) právě tehdy, když {f(u), f(v)}∈E(H).

Question 4

Graf je r-regulární, pokud

Answer 4

stupeň každého jeho vrcholu je r.

Question 5

Graf je regulární, pokud

Answer 5

je r-regulární pro nějaké r.

Question 6

Podgraf vs indukovaný podgraf

Answer 6

Graf H je podgrafem grafu G, když V(H)⊆V(G) a E(H)⊆E(G); tuto skutečnost značíme H⊆G.

indukovaný graf obsahuje všetky pôvodné hrany medzi množinou vrcholov podgrafu, tj. E(H) =E(G)∩(V(H)C2); tuto skutečnost značíme H≤G.

Question 7

Klika v grafu

Answer 7

Klika v grafu G je podmnožina vrcholů, z nichž každé dva jsou sousední (čili spojeny hranou)

Question 8

cesta v grafe

Answer 8

• Podgraf grafu G izomorfní s nějakou cestou P se nazývá cesta v grafu.
• Délka cesty je počet hran v cestě.
• Má-li cesta P v grafu G koncové vrcholy u a v, mluvíme o cestě z u do v, nebo o u-v-cestě. (připouštíme u=v, cesta tedy může mít nulovou délku).

Question 9

kružnice v grafu

Answer 9

Podgraf grafu G izomorfní s nějakou kružnicí C se nazývá kružnice v grafu (používá se i název cyklus)

Question 10

Souvislost grafu

Answer 10

Graf G je souvislý, jestliže v něm pro každé jeho dva vrcholy u, v existuje u-v-cesta. Jinak je G nesouvislý.

(graf je súvislý prváve vtedy, keď obsahuje jednu súvislú komponentu)

Question 11

Souvislá komponenta

Answer 11

Indukovaný podgraf H grafu G je souvislou komponentou, pokud je
- souvislý a
- neexistuje žádný souvislý podgraf F,F<>H, grafu G takový, že H⊆F.
(Souvislá komponenta je tedy v inkluzi maximální souvislý podgraf grafu G.)

Question 12

Prehľadávanie do hĺbky

Answer 12

DFS - prohledávání tedy znamená, že navštívíme nejdřív prvního souseda a prohledávání dalších sousedů se provede až po návratu z „hloubky“. Prepísanie na iteračný algoritmus - zásobník

Question 13

Orientovaný graf

Answer 13

Orientovaný graf G je uspořádaná dvojice(V, E), kde V je neprázdná konečná množina vrcholů (nebo také uzlů) a E je množina orientovaných hran(nebo také šipek). Orientovaná hrana (u, v)∈E je uspořádaná dvojice různých vrcholů u, v∈V. Říkáme, že u je předchůdce v a v je následník u. Platí tedy E⊆V×V.

Question 14

Symetrizace orientovaného grafu

Answer 14

Symetrizace orientovaného grafu G= (V, E) je neorientovaný graf sym(G) = (V, E′), kde{u, v}∈E′ právě tehdy, když (u, v)∈E nebo(v, u)∈E.

Question 15

Slabo súvislý orientovaný graf

Answer 15

Orientovaný graf G= (V, E) nazveme slabě souvislý, pokud je souvislá jeho symetrizace sym(G).

Question 16

Silno súvislý orientovaný graf

Answer 16

Orientovaný graf G= (V, E) nazveme silně souvislý, pokud pro každé dva vrcholy u, v∈V existuje v G orientovaná cesta z u do v a současně orientovaná cesta z v do u.

Question 17

Graf - Strom

Answer 17

Graf G nazveme stromem, pokud je souvislý a neobsahuje žádnou kružnici.

Question 18

Graf - Les

Answer 18

Graf G nazveme lesem, pokud neobsahuje žádnou kružnici.

Question 19

List grafu

Answer 19

Vrchol v grafu G nazveme listem, pokud deg G(v) = 1.

Question 20

Prehľadávanie do šírky

Answer 20

Alternativou pro konstrukci souvislých komponent je prohledávání do šířky (BFS), které jako základní datovou strukturu potřebuje frontu.

Question 21

Kostra grafu

Answer 21

Nechť G je souvislý graf. Podgraf K grafu G nazveme kostrou grafu G, pokud V(K) =V(G) a K je strom

Question 22

Vzdielenosť v grafe

Answer 22

Vzdálenost d(u,v) dvou vrcholů u a v v (orientovaném) grafu G je délka nejkratší (orientované) cesty v G z vrcholu u do vrcholu v. Pokud z u do v žádná cesta neexistuje, definujeme d(u,v) =∞

Question 23

Nechť G je orientovaný acyklický graf. Potom G obsahuje

Answer 23

zdroj i stok

Question 24

Topologické uspořádání

Answer 24

Topologické uspořádání (TU) orientovaného acyklického grafu G= (V,E) je takové pořadí vrcholů v1,v2,…,vn grafu G, že pro každou hranu (vi,vj)∈E platí i < j.

Question 25

TopSort

Answer 25

Zdroje do fornty, napočítaj vstupné hrany, ak klesne počet vstupných hrán, tak zaraď do fronty

Question 26

Jarníkúv algoritmus

Answer 26

Minimálna kostra grafu, začni s ľubovoľným vrcholom a pridaj ho do kostry, pokiaľ existuje hrana, {u,v}, že u patrí do kostry a v nepatrí do kostry, pridaj najlahšiu takú hranu spolu s vrcholom v do kostry

Question 27

Kruskalúv algoritmus

Answer 27

Všetky vrcholy patria do kostry, zoraď hrany podľa ich váhy, iteruj cez zoradené váhy a ak hrana spája dve komponenty, pridaj hranu do kostry

Question 28

Sled v grafu G

Answer 28

Posloupnost (v0, e1, v1, e2, . . . , en, vn) se nazývá sled (nebo také v0vn-sled) v orientovaném grafu G, pokud vi∈V pro všechna i∈{0, . . . , n} a ei= (vi−1, vi)∈E(G) pro všechna i∈{1, . . . , n}.
Délka l(S) sledu S je součet ohodnocení hran, které na něm leží. Pro neorientované grafy je definice analogická

Cesta je sled v ktorom sa neopakujú vrcholy

Question 29

Dijkstra

Answer 29

Pro zadaný ohodnocený (orientovaný) graf G a počáteční vrchol v0, nalezni vzdálenosti všech vrcholů grafu G od vrcholu v0. Budíky - moja vzdialenosť + vzdialenosť do skúmaného vrcholu, vždy od manjemnšje vzdialenosti

Algoritmus předpokládá nezáporné ohodnocení hran.

Question 30

Bellman-Ford

Answer 30

Upravená Dijkstra bez prioritnej fronty s normálnou forntou - funguje pre záporné hrany bez záporných cyklov.
Implementačne SimpleBellmanFord pre 1 - počet vrcholov prejdi všetky hrany a relaxuj

Question 31

Zakořeněný strom, předek, potomek, otec, syn, hladina

Answer 31

Zakořeněný strom je strom T, ve kterém je jeden vrchol r∈V(T) označen jako kořen

Leží-li u na (jediné) cestě z v do kořene, pak u je předek v a v je potomek u.

Pokud je navíc {u, v}∈E(T) hrana, říkáme, že u je otec v a v je syn u.

Vrcholy rozdělíme podle vzdálenosti od kořene do hladin: v nulté leží kořen, v první jeho synové, atd.

Question 32

Binární minimová halda

Answer 32

Binární minimová halda je datová struktura tvaru binárního stromu, v jehož každém vrcholu x je uložen jeden klíč k(x), a která splňuje tyto dvě vlastnosti:

1. Tvar haldy: Strom má všechny hladiny kromě poslední plně obsazené. Poslední hladina je zaplněna od levého okraje směrem k pravému.
2. Haldové uspořádání: Je-li v vrchol a s jeho syn, platí k(v)≤k(s).

Binární halda s n prvky má log n + 1 hladin.
Binární halda s n prvky má n/2 (zaokrúhlené hore) listů a n/2 (zaokrúhlené dole) vnitřních vrcholů

HeapInsert - BubbleUp
HeapExtractMin - BubbleDown
HeapFindMin - vráť koreň

Question 33

Binomiálni halda

Answer 33

Binomiální halda (BH) obsahující n prvků je uspořádaná množina binomiálních stromů T=T1, . . . , T`, kde platí:

• Stromy Ti jsou v T uspořádány vzestupně podle svých řádů.
• n=|V(T1)|+···+|V(T`)|.
• Pro každé nezáporné k se v množině T vyskytuje nejvýše jeden binomiální strom řádu k.
• Každý vrchol v v každém stromu obsahuje klíč k(v).
• Pro každý strom Ti platí haldové uspořádání klíčů, čili ∀v∈V(Ti) a ∀ jeho syny sj, j= 1, , . . . , m, platí k(v)≤k(sj).

Question 34

Binomiálni strom

Answer 34

Binomiální strom řádu k (značíme Bk) je uspořádaný (t.j. záleží na pořadí synů) zakořeněný strom, pro který platí:

1. B0 je tvořen pouze kořenem.
2. Pro k≥1 získáme Bk ze stromů B0, B1, . . . , Bk−1 tak, že přidáme nový kořen a kořeny těchto stromů uděláme (takto popořadě) syny nového kořene.

Počet hladin stromu Bk je roven k+ 1, stupeň kořene je k, a počet vrcholů Bk je roven 2^k.
Binomiální strom s n vrcholy má hloubku log n a počet synů kořene také log n.

Question 35

Binární vyhledávací strom (BVS)

Answer 35

Binární vyhledávací strom (BVS) je binární strom, v jehož každému vrcholu v je uložen unikátní klíč k(v). Přitom pro každý vrchol v musí platit:
Pokud a∈L(v), pak k(a) < k(v). Pokud b∈R(v), pak k(b)> k(v). (tj. menší prvok do ľavého podstrum, väčší do pravého)

Question 36

Dokonale vyvážený BVS

Answer 36

BVS nazveme dokonale vyvážený, pokud pro každý jeho vrchol u platí∣|L(u)|−|R(u)|∣≤1

Dokonale vyvážený BVS o velikosti n má hloubku log n

Question 37

AVL strom, rotácie

Answer 37

BVS je AVL stromem, pokud pro každý jeho vrchol v platí∣h(`(v))−h(r(v))∣≤1.

Ľavá, pravá, ľavo-pravá, pravo-ľavá

Question 38

Tabulky s rozptylováním

Answer 38

Riešenie kolízií:

1. reťazenie
2. otvorené adresovanie

α=n/m,n < m, je faktor naplnění.