AG1 Flashcards
Zdroj v grafe
Zdroj je takový vrchol orientovaného grafu, do kterého nevede žádnáhrana.
Neorientovaný graf
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
Izomorfismus grafů
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).
Graf je r-regulární, pokud
stupeň každého jeho vrcholu je r.
Graf je regulární, pokud
je r-regulární pro nějaké r.
Podgraf vs indukovaný podgraf
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.
Klika v grafu
Klika v grafu G je podmnožina vrcholů, z nichž každé dva jsou sousední (čili spojeny hranou)
cesta v grafe
- 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).
kružnice v grafu
Podgraf grafu G izomorfní s nějakou kružnicí C se nazývá kružnice v grafu (používá se i název cyklus)
Souvislost grafu
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)
Souvislá komponenta
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.)
Prehľadávanie do hĺbky
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
Orientovaný graf
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.
Symetrizace orientovaného grafu
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.
Slabo súvislý orientovaný graf
Orientovaný graf G= (V, E) nazveme slabě souvislý, pokud je souvislá jeho symetrizace sym(G).
Silno súvislý orientovaný graf
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.
Graf - Strom
Graf G nazveme stromem, pokud je souvislý a neobsahuje žádnou kružnici.
Graf - Les
Graf G nazveme lesem, pokud neobsahuje žádnou kružnici.
List grafu
Vrchol v grafu G nazveme listem, pokud deg G(v) = 1.
Prehľadávanie do šírky
Alternativou pro konstrukci souvislých komponent je prohledávání do šířky (BFS), které jako základní datovou strukturu potřebuje frontu.
Kostra grafu
Nechť G je souvislý graf. Podgraf K grafu G nazveme kostrou grafu G, pokud V(K) =V(G) a K je strom
Vzdielenosť v grafe
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) =∞
Nechť G je orientovaný acyklický graf. Potom G obsahuje
zdroj i stok
Topologické uspořádání
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.
TopSort
Zdroje do fornty, napočítaj vstupné hrany, ak klesne počet vstupných hrán, tak zaraď do fronty
Jarníkúv algoritmus
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
Kruskalúv algoritmus
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
Sled v grafu G
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
Dijkstra
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.
Bellman-Ford
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
Zakořeněný strom, předek, potomek, otec, syn, hladina
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.
Binární minimová halda
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:
- 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.
- 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ň
Binomiálni halda
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).
Binomiálni strom
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í:
- B0 je tvořen pouze kořenem.
- 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.
Binární vyhledávací strom (BVS)
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)
Dokonale vyvážený BVS
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
AVL strom, rotácie
BVS je AVL stromem, pokud pro každý jeho vrchol v platí∣h(`(v))−h(r(v))∣≤1.
Ľavá, pravá, ľavo-pravá, pravo-ľavá
Tabulky s rozptylováním
Riešenie kolízií:
- reťazenie
- otvorené adresovanie
α=n/m,n < m, je faktor naplnění.
