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 [2014/10/27 09:07]
127.0.0.1 upraveno mimo DokuWiki
+++ mgr-szz:in-pds:1-pds [2020/04/12 16:56] (aktuální)
@@ Řádek 1: / Řádek 1: @@
-====== Zadanie ======
+===== Zadání =====
-Hardwarové platformy pro paralelní výpočty a související typy paralelních algoritmů. Návrh paralelních algoritmů: míra a úroveň paralelizace, typy komunikace a jejich vlastnosti, synchronizace a serializace. Analýza paralelních algoritmů: zrychlení (speedup), škálovatelnost, komunikační složitost versus lokalita a jejich vliv na výkon paralelní implementace.
+Grafy a grafové algoritmy. Formalizace základních grafových pojmů, reprezentace grafů. Souvislost grafu, barevnost, rovinné grafy. Algoritmy (včetně složitosti a základní myšlenky důkazů korektnosti): prohledávání grafu do šířky a do hloubky, nejkratší vzdálenosti, kostry, toky v sítích.
-====== Vypracovanie ======
+===== Vypracování =====
+**Upozornění:** bez nároku na úplnost a korektnost. Podle hesla „lepší něco než nic“. Ale snaha byla o co nejlepší výsledek.
+==== Základní grafové pojmy ====
+  * graf – uspořádaná dvojice <math>(V, E)</math> množin vrcholů a hran
+  * vrchol – jeden z prvků množiny určující graf; mohou z něj vést hrany
+  * hrana – dvouprvková podmnožina množiny vrcholů. (Orientovaný graf: <math>E \subseteq V \times V</math>.) Když <math>v \in e</math>, tak <math>v</math> je incidentní s <math>e</math>.
+  * řídký graf – <math>|E|</math> je mnohem menší než <math>|V|^2</math> (→ preferuje proto seznamy následníků)
+  * hustý graf – <math>|E|</math> je blízko <math>|V|^2</math> (→ preferuje proto matici sousednosti)
+  * smyčka – hrana <math>(a, a)</math>
+  * cesta v grafu – posloupnost <math>P = (v_0, e_1, v_1, ...)</math>, kde <math>e_i = { v_i-1, v_i }</math>, navíc <math>v_i != v_j</math> pro <math>i != j</math>
+  * tah – cesta, v níž se mohou opakovat vrcholy
+  * sled – cesta, v níž se mohou opakovat vrcholy i hrany
+  * cyklus/kružnice – uzavřená cesta (netriviální)
+  * sousední vrchol – spojený hranou
++ váhovaný graf, multigraf
+=== Reprezentace grafů ===
+== Seznamy následníků ==
+  * máme pole o |V| prvcích – pro každý vrchol u ∈ V jeden a je jím seznam prvků v $ (u, v) ∈ E
+  * paměťová náročnost: Θ(V + E)
+== Maticí sousednosti ==
+  * matice velikosti |V| × |V|
+  * prvek matice a_ij = 1, pokud (i, j) ∈ E, jinak a_ij = 0
+=== Souvislost grafu ===
+  * souvislý graf – (neorientovaný) graf, v němž platí, že pro každé dva vrcholy x, y existuje sled z x do y.
+  * slabá souvislost – graf je slabě souvislý, pokud jeho symetrizace (= odstranění orientovanosti) je souvislý graf.
+  * silná souvislost – graf je silně souvislý, pokud pro každé dva vrcholy x, y existuje cesta z x do y i z y do x.
+Silně souvislá komponenta je takový //maximální// podgraf orientovaného grafu, v němž pro každou dvojici vrcholů u, v existuje sled.
+  * Dvojitý DFS – první mi určí pořadí (na G^R) pro volání druhého (na G) (sestupné finishing časy), který mi vytiskne jednotlivé komponenty.
+== Řezy ==
+  * vrcholový řez (= separátor) – taková množina U ⊆ V, že graf G = (V\U, E) není souvislý
+  * hranový řez
+  * vrcholová (hranová) souvislost – velikost minimálního vrcholového (hranového) řezu
+  * graf je vrcholově/hranově k-souvislý, pokud jeho vrcholová/hranová je ≥ k
+=== Barevnost ===
+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 <math>\chi(G)</math> (= velké chí).
+=== Rovinné grafy (= planární) ===
+  * pro rovinný graf existuje takové rovinné nakreslení, kdy se žádné dvě hrany nekříží
+  * duální graf – (multi)graf, jehož vrcholy tvoří stěny jiného rovinného grafu
+  * stěna – souvislý kus roviny určený rovinným nakreslením grafu
+Věta (Eulerova formule): V rovinném grafu G=(V, E) platí:
+. |V| − |E| + s = |E|+2.		(s = počet stěn)
+. |E| ≤ 3|V|−6.
+Věta (o 4 barvách): Vrcholy rovinného grafu lze obarvit 4 barvami tak, aby žádná hrana nespojovala dva vrcholy stejné barvy.
+  * aplikace: návrh jednovrstvých tištěných spojů (= PCB) (VLSI designs)
+==== Algoritmy ====
+**Včetně složitosti a základní myšlenky důkazů korektnosti!**
+<note tip>
+<math>n= |V|</math>
+<math>m = |E|</math>
+</note>
+=== Prohledávání grafu ===
+^ algoritmus ^ složitost ^
+| BFS | <math>\mathcal{O}(m + n)</math> |
+| DFS | <math>\mathcal{O}(m + n)</math> |
+<box 90% blue|BFS>
+  * Q – fronta z vrcholů
+  * d[u] – vzdálenost u od s
+  * π[u] – předchůdce u
+  * color[u] ∈ {white, gray, black} – pomocné
+  * inicializace pro všechny mimo počáteční vrchol s: obarvení na bílo, nekonečná vzdálenost, předchůdce nil
+  * inicilalizace s: šedý, vzdálenost 0, předchůdce nil, zařadí se do Q
+  * dokud se Q nevyprázdní, vezmu z Q u, projdu všechny jeho bílé sousedy, ošedím je, nastavím vzdálenost (d[u] + 1) a předchůdce (u), zařadím do Q a u přebarvím na černo
+**Složitost**
+  * incializace: <math>\mathcal{O}(n)</math>
+  * žádný vrchol se pak již nepřebarví na bílo, takže jde do i z Q nejvýše jednou → operace s frontou tedy stojí <math>\mathcal{O}(n)</math>
+  * seznam sousedů vrcholu se prochází, jen když je vrchol odstraňován z fronty, takže dohromady <math>\mathcal{O}(m)</math>
+  * = <math>\mathcal{O}(m+n)</math>
+**Korektnost**
+  * BFS objeví každý z s dosažitelný vrchol, nedosažitelné nebudou objeveny.
+  * Po zastavení d[v] = δ(s, v) ∀v ∈ V.
+  * Pro každé v ∈ V dosažitelné z s je lib. nejkratší s-π[v]-cesta následovaná hranou (π[v], v) jednou z nejkratších s-v-cest.
+Právě vrcholy zařazené do Q mají d[v] < ∞. Pokud v nedosažitelné z s, tak d[v] >= δ(s, v) = ∞, proto v nebude objeven.
+V_k = {v ∈ V | δ(s, v) = k}, k ∈ N_0, → indukcí vzhledem ke k.
+IK: Pokud v jde do Q, d[v], π[v] se již nikdy nemění. Jsou-li vrcholy zařazovány do Q v pořadí v_1, ..., v_r, pak d[v_1] ≤ ... ≤ d[v_r]. Nechť v ∈ V_k (k ≥ 1), tj. je objeven až po objevení všech z V_k-1. Poněvadž δ(s, v) = k, ex. cesta s, ..., u (∈ V_k-1), v délky k. Nechť u je první takový objevený. V jistém okamžiku se u objeví na čele Q, v je objeven při prohlídce sousedů u. Tedy pro v ∈ V_k je π[v] ∈ V_k-1, a proto d[v] = d[π[v]] + 1. Nejkratší cestu do v tak získáme tím, že půjdeme po nejkratší cestě do π[v], a pak po hraně (π[v], v).
+</box>
+<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
+  * ta: inkrementuje čas, nastaví discovery time, ošedí vrchol; projde všechny sousedy a bílým nastaví předchůdce a spustí nad nimi opět Visit; nakonec uzel očerní, inkrementuje čas a nastaví finishing time
+**Složitost**
+  * inicializace O(n), vynulování času O(1), iterace nad vrcholy O(n)
+  * Visit: nastavení parametrů – pro každý vrchol O(1); procházení sousedů O(m); nastavení parametrů – pro každý vrchol O(1)
+  * = O(m + n)
+**Korektnost**
+  * věta o závorkách (discovery a finishing časy dvou uzlů jsou buď zcela disjunktní nebo tak či onak zanořené, pokud v DF-tree jde o následníka)
+  * věta o bílé cestě (pokud v je v DF-forest následníkem u, tak v čase d[u] vede od u k v cesta po čistě bílých vrcholech)
+DF-forest = predecessor subgraph, kde hrany = { (π[v], v) | v ∈ V ∧ π[v] ≠ nil } → forest, protože DFS může být opakováno z více vrcholů
+</box>
+=== Nejkratší vzdálenosti ===
+<box 90% red|relaxace>
+ if d[v] > d[u] + w(u, v) → d[v] = d[u] + w(u, v); π[v] = u (w = váha hrany)
+</box>
+^ 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 + 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>
+  * udržuje množinu vrcholů, do kterých už byla vzdálenost spočítána; vyžaduje minimovou prioritní frontu – z dosud nezpracovaných vrcholů
+  * zpracovává postupně vrcholy mající nejnižší cenu (vzdálenost od s) a každou hranu z daného vrcholu relaxuje
+  * nefunguje pro záporně ohodnocené hrany
+**Složitost**
+  * 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)
+  * s využitím fibonacciho haldy: O(m + n * log n)
+**Korektnost**
+Ukážeme, že d[v] = δ(s, v) v okamžiku přidání v do S; (a že) rovnost je pak zachována. [dokazuje se na u jako prvním vrcholu, pro který to neplatí, na cestě je pak nějaké y z V\S (stejně jako u), kde přes d[y] = δ(s, y) ≤ δ(s, u) ≤ d[u], ale pak dostaneme rovnost, protože y není v S v okamžiku, kdy se tam dostává u (tj. spor s volbou u)]
+</box>
+<box 90% blue|Bellman-Ford>
+  * (|V| - 1)-krát iteruje přes všechny hrany a každou relaxuje
+  * iteruje přes všechny hrany a kontroluje, jestli graf neobsahuje dosažitelný negativní cyklus (ano → vrátí false)
+**Složitost**
+  * inicializace O(n), relaxace hran O(m * n), kontrola na negativní cyklus O(m), ukončení O(1)
+  * = O(m * n)
+**Korektnost**
+  * ukáže se, že po skončení d[v] = δ(s, v) pro všechny v z V [dokazuje se indukcí po nejkratší s-v-cestě (vrcholy se na ní neopakují (→ nejvýše |V|-1 hran)) – d[v_i] se po i-té iteraci relaxaci už nemění (zrelaxuje se tedy celá cesta)]
+  * (G_π je strom nejkratších cest) [nevím jak]
+  * 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>
+  * místo sčítání počítá minimum, místo násobení sčítá, čímž dostaneme algoritmus pro výpočet nejkratších cest
+    * celé se to opakuje, dokud nedostaneme násobek alespoň n-1
+  * složitost: O(n^3 * log n)
+</box>
+<box 90% blue|Floyd-Warshall>
+  * využívá dynamického programování; (bez záporných cyklů – detekce na diagonále); princip: nejkratší cesta z a do b obsahuje nejkratší cesty mezi vrcholy, z nichž se skládá
+  * 3 zanořené cykly {1..n} a vevnitř: d_ij^(k) ← min(d_ij^(k-1), d_ik^(k-1) + d_kj^(k-1))
+  * k = 0 jsou samotné váhy hran
+  * společně s délkou nejkratších cest se stejným způsobem počítá i matice předchůdců
+  * složitost: O(n^3)
+</box>
+<box 90% blue|Johnson>
+  * vytvoří graf G', který má navíc nový vrchol s a hrany (s, v) s váhou 0 do všech vrcholů v – z tohoto vrcholu se pak spustí BF pro detekci záporného cyklu; pokud takový cyklus v grafu není, každá hrana (u, v) se převáhuje: w(u, v) + δ(s, u) − δ(s, v); z každého vrcholu se pak spustí Dijkstra. Výsledek se pak převáhuje zpět a uloží do matice
+  * složitost: O(n^2 * log n + m * n) → pro řídké grafy efektivnější než FW
+</box>
+=== Kostry ===
+  * **Spanning Tree** (kostra) grafu <math>G=(V,E)</math> je podgraf <math>T \subseteq G</math> t.ž. <math>V(T) = V(G)</math> a <math>T</math> je strom.
+  * **Minimum Spanning Tree (MST; minimální kostra)** grafu <math>G</math> je kostra <math>M</math> t.ž. <math>w(M) \leq w(T)</math> pro všechny kostry <math>G</math>.
+    * <math>w</math> značí váhu kostry = součet vah jednotlivých hran
+Pravidla použitá při definici/důkazech:
+(viz slidy MA015)
+<box 90% red|Cut Property>
+Pokud je //e// nejlehčí hrana přes nějaký řez //G//, pak <math>e \in M</math>.
+⬇
+<color blue>Blue rule: Pro daný řez bez modrých hran vybereme neobarvenou hranu a obarvíme ji modře.</color>
+</box>
+<box 90% red|Cycle Property>
+Pokud je //e// nejtěžší hrana nějakého cyklu v //G//, pak <math>e \notin M</math>.
+⬇
+<color red>Red rule: Pro daný cyklus neobsahující žádnou červenou hranu vybereme maximální neobarvenou hranu a obarvíme ji na červeno.</color>
+</box>
+^ algoritmus ^ složitost ^
+| Borůvka | <math>\mathcal{O}(m * \log n)</math> |
+| Kruskal | <math>\mathcal{O}(m * \log n)</math> |
+| Jarník |<math>\mathcal{O}(m * |DECREASE-KEY| + n * |EXTRACT-MIN|)</math>|
+| Fredman-Tarjan (Jarník + Fibonacciho halda) |<math>\mathcal{O}(m + n * \log 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 * \log \beta (m, n))</math> |
+<box 90% blue|Kruskal>
+  * Budujeme <color blue>modrý les</color>.
+  * umístí každý vrchol do samostatné množiny a utřídí hrany podle váhy do neklesající posloupnosti
+  * prochází jednu hranu po druhé, pokud její vrcholy patří do různých množin, přidá hranu do kostry a množiny sloučí
+**Složitost**
+  * použijeme strukturu Union-Find
+  * inicializace O(n) a utřídění hran O(m * log m)
+  * pro každou hranu provádíme dvě Find operace, které stojí O(log n), a eventuálně Union, který je rovněž v O(log n)
+  * = O(m * log n) [protože m < n^2, tedy log m = O(log n)]
+**Korektnost**
+  * kostra: K je podgraf souvislého grafu G, K nemá cyklu, protože je v jednom podstromu, ne ve dvou; je souvislý, jinak by algoritmus přidal první hranu, která spojuje dvě komponenty K
+  * minimální: indukcí „množina hran F vybraná algoritmem je podmnožinou nějaké minimální kostry T“. Alg. vybere další hranu e, která není v T, tak T+e tvoří cyklus, který obsahuje hranu f, která není v F. Obě ale mají stejnou váhu, takže T-f+e je strom o stejné váze jako T, takže je to minimální kostra obsahující F+e a vlastnost opět platí
+</box>
+<box 90% blue|Jarník (Prim)>
+  * Budujeme <color blue>modrý strom</color>.
+  * Začneme budovat strom z jednoho vrcholu a přidáme vždy nejlehčí odchozí hranu.
+**Algoritmus**
+  * při inicializaci nastaví klíče vrcholů na nekonečno a rodiče na nil; r.key = 0 pro počáteční vrchol; naplní Q
+  * vybírá z Q vrcholy s minimálním cenou, prochází jejich sousedy a do těch, do kterých se umí dostat z daného vrcholu levněji, nastaví nového rodiče a cenu
+**Složitost**
+  * použijeme binární haldu
+  * incializace O(n), pro všechny vrcholy odstranění z Q O(n * log n), procházení všech hran a snižování ceny O(m * log n)
+  * = O(m * log n)
+  * s fibonacciho haldou by šlo zlepšit na O(m + n * log n) díky amortizované O(1) složitosti snižování ceny
+**Korektnost**
+T je nějaká minimální kostra G a K je výstup Jarníkova algoritmu. K = T triviální. Pokud K != T, pak nechť e je první, která je v K, ale ne v T. V je množina vrcholů přidaných do K před e – pak jeden konec e je ve V, druhý ne. V T ale musí existovat cesta spojující oba konce – na této cestě se musí nacházet hrana f spojující vrchol ve V s vrcholem, který ve V ještě není. V okamžiku, kdy je e přidána ke K, mohla by být přidána i hrana f, pokud by vážila méně. Z jejího nepřidání plyne, že d[e] <= d[f].
+V T je možné vyměnit hranu f za e – výsledný strom zůstane souvislý, obsahuje stejný počet hran a váha jeho hran se nezvýší. Tedy je rovněž minimální kostrou G. Opakováním tohoto postupu dojdeme k tomu, že K je rovno minimální kostře G.
+</box>
+<box 90% blue|Borůvka>
+  * Budujeme <color blue>modré stromy</color> ze všech vrcholů na ráz.
+  * Na začátku vytvoříme ze všech vrcholů modré stromy.
+  * V každé fázi vybereme pro každý strom nejlehčí odchozí hranu a přidáme ji ke stromu. (Spojíme propojené stromy.)
+  * Končíme, pokud nám zbyl pouze jeden strom.
+**Složitost**
+  * Počet komponent v prvním tahu: //n//
+  * každá přidaná hrana spojí nejméně dvě komponenty
+    * => 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 * \log n)</math>
+</box>
+=== Toky v sítích ===
+**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
+  * alg: inicializuje toky na hranách na 0; dokud existuje zlepšující cesta, tak na ní zvýší tok o minimální společnou reziduální kapacitu (tj. o maximum)
+  * + Edmonds-Karp (BFS po nenasycených hranách)/nejširší cesty (maximální reziduální kapacita)/zjemňování stupnice (upřednostňuje cesty s nejvyšším potenciálem pro zlepšení; filtr 2^i, postupně se snižuje)
+**Složitost**
+  * inicializace O(m), každá iterace cyklu O(m)
+  * Edmonds-Karp O(m * n)
+  * zjemňování stupnice O(m^2 * log_2 C); C=SUMA[přes v z V] c(s, v)
+**Korektnost**
+  * ukáže se, že kapacitní ohraničení a podmínka kontinuity zůstanou splněny
+  * že na konci obdržím skutečně maximální tok – v reziduální síti už neexistuje cesta z s do t
+</box>
+<box 90% blue|Push-Relabel>
+  * pracuje s pseudotokem (nesplňuje podm. kontinuity = aktivní vrchol) a výškami vrcholů – tok se přesouvá od vyšších k nižším
+  * pokud je možné protlačit nějaký tok od aktivního vrcholu k nižším, tak Push, jinak Relabel tohoto vrcholu
+  * inicializace: výšky, aktivity, toky
+**Složitost**
+  * nanejvýš 2n^2 počet relabel, 2nm saturujících push (přetlačování v reziduální síti), 4mn^2 nesaturujících push; push i relabel lze realizovat v konstatní složitosti
+  * = O(n^2 * m)
+**Korektnost**
+V průběhu celého výpočtu platí:
+  * výška vrcholu nikdy neklesá;
+  * f je pseudotok a pokud kapacity jsou celočíselné, tak i f je;
+  * pseudotok a výška jsou kompatibilní (tj. h(t) = 0, h(s) = n, pro hrany (v, w) platí h(v) <= h(w) + 1).
+Pokud alg. vrátí pseudotok, tak je to maximální tok.
+→
+  * Push respektuje kapacitní ohraničení hrany a do reziduálního grafu přidá hranu, která nemusí splňovat výškový rozdíl
+  * Relabel zvyšuje výšku vrcholu v právě když v reziduální síti nevede z v do žádného vrcholu s menší výškou
+</box>
+===== Předměty =====
+  * [[https://is.muni.cz/auth/predmet/fi/MA010|MA010 Graph Theory]]
+  * [[https://is.muni.cz/auth/predmet/fi/MA015|MA015 Graph Algorithms]]
+===== Související otázky =====
+  * [[mgr-szz:in-tei:5-tei]]
+~~DISCUSSION~~

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

Nahoru