Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- mgr-szz:in-pds:1-pds [2019/06/12 17:02]
lachmanfrantisek formátování, doplnění, tabulky algoritmů
+++ mgr-szz:in-pds:1-pds [2020/04/12 16:56] (aktuální)
@@ Řádek 49: / Řádek 49: @@
 Barvení grafu se zabývá přiřazováním barev nejčastěji vrcholům (příp. hranám či stěnám).
-Nechť G = (V, E) je graf, k přirozené číslo. Zobrazení b: V → {1, ..., k} nazveme obarvením grafu G pomocí k barev, pokud pro každou hranu {x, y} ∈ E platí b(x) ≠ b(y). Barevnost grafu (také **chromatické číslo**) G je minimální počet barev potřebný pro obarvení G. Značí se Χ(G) (= velké chí).
+Nechť G = (V, E) je graf, k přirozené číslo. Zobrazení b: V → {1, ..., k} nazveme obarvením grafu G pomocí k barev, pokud pro každou hranu {x, y} ∈ E platí b(x) ≠ b(y). Barevnost grafu (také **chromatické číslo**) G je minimální počet barev potřebný pro obarvení G. Značí se <math>\chi(G)</math> (= velké chí).
 === Rovinné grafy (= planární) ===
@@ Řádek 81: / Řádek 81: @@
 <box 90% blue|BFS>
-  * procházení grafu metodou **backtrackingu**
-  * vždy expanduje prvního následníka každého vrcholu, pokud jej ještě nenavštívil
-  * vrcholy k procházení ukládá do zásobníku (LIFO)
-  * pokud nenajde v aktuálním vrcholu nenavštívené následníky, vrací se zpět **backtrackingem** (vyjme další prvek ze zásobníku)
-**Algoritmus**
   * Q – fronta z vrcholů
@@ Řádek 117: / Řádek 110: @@
 <box 90% blue|Depth-First Search (DFS)>
+  * procházení grafu metodou **backtrackingu**
+  * vždy expanduje prvního následníka každého vrcholu, pokud jej ještě nenavštívil
+  * vrcholy k procházení ukládá do zásobníku (LIFO)
+  * pokud nenajde v aktuálním vrcholu nenavštívené následníky, vrací se zpět **backtrackingem** (vyjme další prvek ze zásobníku)
+**Algoritmus**
   * incializace vynuluje čas + všechny obarví na bílo a nastaví předchůdce na nil
   * hlavní část algoritmu iteruje přes všechny vrcholy grafu a nad bílými spouští podproceduru Visit
@@ Řádek 139: / Řádek 140: @@
 </box>
-^ algoritmus ^ složitost ^ typ grafu ^
+^ algoritmus (1-to-n)^ složitost ^ typ grafu ^
 | BFS | <math>\mathcal{O}(m+n)</math> | vzdálenost = počet hran |
-| Dijkstrův algoritmus | <math>\mathcal{O}(m \times \log n)</math> | nezáporné délky hran |
+| Dijkstrův algoritmus | <math>\mathcal{O}(m + n * \log n)</math> | nezáporné délky hran |
+| Bellman-Ford | <math>\mathcal{O}(m * n)</math>| |
+^ algoritmus (n-to-n)^ složitost ^ typ grafu ^
 | Násobení matic | <math>\mathcal{O}(n^3 * \log n)</math> | |
 | Floyd-Warshall | <math>\mathcal{O}(n^3)</math> | |
 | Johnson | <math>\mathcal{O}(n^2 * \log n + m * n)</math> | |
+== Hledání nejkratších cest z jednoho vrcholu do všech ==
 <box 90% blue|Dijkstrův algoritmus>
@@ Řádek 155: / Řádek 160: @@
   * inicializace O(n), naplnění Q O(n), zpracování všech vrcholů O(n), relaxace všech hran O(m) + aktualizace hodnot v Q O(log n) pro každou hranu
   * uvažujeme binární haldu, kde vložení je v průměru v O(1), odstranění minima O(log n) a aktualizace O(log n)
-  * = O(m * log n)
+    * = O(m * log n)
+  * s využitím fibonacciho haldy: O(m + n * log n)
 **Korektnost**
@@ Řádek 175: / Řádek 181: @@
   * BF vrátí true, protože platí trojúhelníková nerovnost; (jinak) pokud obsahuje dosažitelný negativní cyklus, vrátí false
 </box>
+== Hledání nejkratších cest mezi všemi vrcholy ==
 <box 90% blue|Násobení matic>
@@ Řádek 223: / Řádek 231: @@
 ^ algoritmus ^ složitost ^
-| Borůvka | <math>\mathcal{O}(m \times \log n)</math> |
+| Borůvka | <math>\mathcal{O}(m * \log n)</math> |
-| Kruskal | <math>\mathcal{O}(m \times \log n)</math> |
+| Kruskal | <math>\mathcal{O}(m * \log n)</math> |
-| Jarník |<math>\mathcal{O}(m \times |DECREASE-KEY| + n \times |EXTRACT-MIN|)</math>|
+| Jarník |<math>\mathcal{O}(m * |DECREASE-KEY| + n * |EXTRACT-MIN|)</math>|
-| Fredman-Tarjan (Jarník + Fibonacciho halda) |<math>\mathcal{O}(m + n \times \log n)</math>|
+| Fredman-Tarjan (Jarník + Fibonacciho halda) |<math>\mathcal{O}(m + n * \log n)</math>|
-| Fredman-Tarjan (limit velikosti haldy) | <math>\mathcal{O}(m \times \beta (m, n))</math> |
+| Fredman-Tarjan (limit velikosti haldy) | <math>\mathcal{O}(m * \beta (m, n))</math> |
-| Gabow et al. (F-T + packeting) | <math>\mathcal{O}(m \times \log \beta (m, n))</math> |
+| Gabow et al. (F-T + packeting) | <math>\mathcal{O}(m * \log \beta (m, n))</math> |
 <box 90% blue|Kruskal>
@@ Řádek 280: / Řádek 288: @@
     * => nejvýš <math>\log n</math> fází
   * každá fáze zabere <math>\mathcal{O}(m)</math> (musíme projít přes všechny hrany)
-  * celkem: <math>\mathcal{O}(m \times \log n)</math>
+  * celkem: <math>\mathcal{O}(m * \log n)</math>
 </box>
 === Toky v sítích ===
-  * **R**eálný tok – podmínky: kapacitní ohraničení (tok na hraně ≤ kapacita hrany), podmínka kontinuity (co přitéká = co odtéká); |f| = z s vytéká − vrací
+**Flow network** ("toková síť") je čtveřice <math>(G,s,t,c)</math>:
+  * <math>G=(V,E)</math>: orientovaný graf
+  * <math>s \in V</math>: zdroj (source)
+  * <math>t \in V</math>: stok (cíl); <math>s \neq t</math>
+  * <math>c: E \rightarrow R^{+}</math>: funkce určující kapacity hran
+**Network flow** (tok v síti) je funkce <math>f:E \rightarrow R^{+}</math> splňující:
+  * kapacitní podmínku (tok přes hranu je nezáporný a maximálně roven kapacitě hrany)
+  * podmínku kontinuity (všechny vrchol krom //s// a //t// mají součet vstupních kapacit roven součtu výstupních)
+  * Hodnota toku //f// je <math>|f| = \sum_{(s,v) \in E}{f(s,v)} = \sum_{(w,t) \in E}{f(w,t)}</math>
+  * Problémem je hledání maximálního toku -- toku s maximální hodnotou.
+<box 90% red|Ford-Fulkerson: MAX-FLOW=MIN-CUT>
+hodnota maximálního toku = kapacita minimálního řezu
+</box>
+<box 90% red|Reziduální síť>
+**Reziduální graf**
+  * graf <math>G_f = (V,E_f)</math>, kde pro každou hranu <math>e = (u,v) \in E</math> obsahuje <math>E_f</math>:
+    * <math>e = (u,v)</math> pokud <math>f(e) \textless c(e)</math>
+    * <math>e^R = (v,u)</math> pokud <math>f(e) \textgreater 0</math>
+**Reziduální kapacita**
+<math>c_f(e)=\begin{cases} c(e)-f(e) \mbox{ pokud } e \in E_f \\
+f(e) \mbox{ pokud } e^R \in E_f \end{cases} </math>
+**Augmentující cesta**
+Cesta z //s// do //t// v reziduálním grafu.
+**Augmentace toku**
+Upravíme tok na základě **bottleneck** kapacity augmentující cesty.
+  * pro <math>e</math> hodnotu přičteme
+  * pro <math>e^R</math> hodnotu odečteme
+</box>
+^ algoritmus ^ složitost ^
+| Ford-Fulkerson |<math>\mathcal{O}(nm * C)</math> C -- nejvyšší kapacita|
+| Edmonds-Karp (FF + shortest aug. path) | <math>\mathcal{O}(m^2n)</math>|
+|Dinitz (saturate all s-t paths in <math>G_f</math>)|<math>\mathcal{O}(mn^2)</math>|
+|MPM (three indians)|<math>\mathcal{O}(n^3)</math>|
+|push-relabel|<math>\mathcal{O}(mn^2)</math>|
 <box 90% blue|Ford-Fulkerson>
+Hledáme augmentujeme tok pomocí augmentujících cest dokud ještě síť nějakou augmentující cestu má.
+**Algoritmus**
   * reziduální kapacita – kolik dalšího toku se dá ještě hranou vést
   * nemusí skončit, pokud jsou **R**eálné kapacity; síť s racionálními kapacitami lze převést na síť s celočíselnými

mgr-szz/in-pds/1-pds.1560351731.txt.gz · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru