Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze | ||
mgr-szz:in-pds:1-pds [2019/06/12 12:32] lachmanfrantisek math u základních pojmů |
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). | 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í) === | === Rovinné grafy (= planární) === | ||
Řádek 67: | Řádek 67: | ||
**Včetně složitosti a základní myšlenky důkazů korektnosti!** | **Včetně složitosti a základní myšlenky důkazů korektnosti!** | ||
- | === BFS === | + | <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ů | * Q – fronta z vrcholů | ||
* d[u] – vzdálenost u od s | * d[u] – vzdálenost u od s | ||
Řádek 73: | Řádek 87: | ||
* color[u] ∈ {white, gray, black} – pomocné | * color[u] ∈ {white, gray, black} – pomocné | ||
- | == Algoritmus == | ||
* inicializace pro všechny mimo počáteční vrchol s: obarvení na bílo, nekonečná vzdálenost, předchůdce nil | * 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 | * 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 | * 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 == | + | **Složitost** |
- | * incializace: O(n) | + | * 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í O(n) | + | * žá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 O(m) | + | * seznam sousedů vrcholu se prochází, jen když je vrchol odstraňován z fronty, takže dohromady <math>\mathcal{O}(m)</math> |
- | * = O(m + n) | + | * = <math>\mathcal{O}(m+n)</math> |
- | == Korektnost == | + | **Korektnost** |
- | G = (V, E) | + | |
* BFS objeví každý z s dosažitelný vrchol, nedosažitelné nebudou objeveny. | * BFS objeví každý z s dosažitelný vrchol, nedosažitelné nebudou objeveny. | ||
* Po zastavení d[v] = δ(s, v) ∀v ∈ V. | * Po zastavení d[v] = δ(s, v) ∀v ∈ V. | ||
Řádek 95: | Řádek 107: | ||
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). | 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** | ||
- | === DFS === | ||
* incializace vynuluje čas + všechny obarví na bílo a nastaví předchůdce na nil | * 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 | * 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 | * 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 == | + | **Složitost** |
* inicializace O(n), vynulování času O(1), iterace nad vrcholy O(n) | * 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) | * 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) | * = O(m + n) | ||
- | == Korektnost == | + | **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 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) | * 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ů | 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 === | === Nejkratší vzdálenosti === | ||
- | * relaxace = if d[v] > d[u] + w(u, v) → d[v] = d[u] + w(u, v); π[v] = u (w = váha hrany) | ||
- | == Dijkstrův algoritmus == | + | <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ů | * 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 | * 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 | * nefunguje pro záporně ohodnocené hrany | ||
- | = Složitost = | + | **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 | * 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) | * 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 = | + | **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)] | 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> | ||
- | == Bellman-Ford == | ||
* (|V| - 1)-krát iteruje přes všechny hrany a každou relaxuje | * (|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) | * iteruje přes všechny hrany a kontroluje, jestli graf neobsahuje dosažitelný negativní cyklus (ano → vrátí false) | ||
- | = Složitost = | + | **Složitost** |
* inicializace O(n), relaxace hran O(m * n), kontrola na negativní cyklus O(m), ukončení O(1) | * inicializace O(n), relaxace hran O(m * n), kontrola na negativní cyklus O(m), ukončení O(1) | ||
* = O(m * n) | * = O(m * n) | ||
- | = Korektnost = | + | **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)] | * 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] | * (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 | * BF vrátí true, protože platí trojúhelníková nerovnost; (jinak) pokud obsahuje dosažitelný negativní cyklus, vrátí false | ||
+ | </box> | ||
- | == Další == | + | == Hledání nejkratších cest mezi všemi vrcholy == |
- | * BFS | + | |
- | == Násobení matic == | + | <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 | * 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 | * celé se to opakuje, dokud nedostaneme násobek alespoň n-1 | ||
* složitost: O(n^3 * log n) | * složitost: O(n^3 * log n) | ||
+ | </box> | ||
- | == Floyd-Warshall == | + | <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á | * 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)) | * 3 zanořené cykly {1..n} a vevnitř: d_ij^(k) ← min(d_ij^(k-1), d_ik^(k-1) + d_kj^(k-1)) | ||
Řádek 155: | Řádek 196: | ||
* společně s délkou nejkratších cest se stejným způsobem počítá i matice předchůdců | * 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) | * složitost: O(n^3) | ||
+ | </box> | ||
- | == Johnson == | + | <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 | * 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 | * složitost: O(n^2 * log n + m * n) → pro řídké grafy efektivnější než FW | ||
+ | </box> | ||
=== Kostry === | === Kostry === | ||
- | == Kruskal == | + | * **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 | * 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čí | * 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 = | + | **Složitost** |
* použijeme strukturu Union-Find | * použijeme strukturu Union-Find | ||
* inicializace O(n) a utřídění hran O(m * log m) | * inicializace O(n) a utřídění hran O(m * log m) | ||
Řádek 172: | Řádek 251: | ||
* = O(m * log n) [protože m < n^2, tedy log m = O(log n)] | * = O(m * log n) [protože m < n^2, tedy log m = O(log n)] | ||
- | = Korektnost = | + | **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 | * 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í | * 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** | ||
- | == Jarník == | ||
* 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 | * 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 | * 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 = | + | **Složitost** |
* použijeme binární haldu | * 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) | * 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) | ||
Řádek 186: | Řádek 271: | ||
* s fibonacciho haldou by šlo zlepšit na O(m + n * log n) díky amortizované O(1) složitosti snižování ceny | * 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 = | + | **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]. | 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. | 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 === | === 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í | ||
- | == Ford-Fulkerson == | + | **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 | * 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 | * 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 | ||
Řádek 200: | Řádek 348: | ||
* + 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) | * + 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 = | + | **Složitost** |
* inicializace O(m), každá iterace cyklu O(m) | * inicializace O(m), každá iterace cyklu O(m) | ||
* Edmonds-Karp O(m * n) | * 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) | * zjemňování stupnice O(m^2 * log_2 C); C=SUMA[přes v z V] c(s, v) | ||
- | = Korektnost = | + | **Korektnost** |
* ukáže se, že kapacitní ohraničení a podmínka kontinuity zůstanou splněny | * 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 | * že na konci obdržím skutečně maximální tok – v reziduální síti už neexistuje cesta z s do t | ||
+ | </box> | ||
- | == Push-Relabel == | + | <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 | * 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 | * 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 | * inicializace: výšky, aktivity, toky | ||
- | = Složitost = | + | **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 | * 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) | * = O(n^2 * m) | ||
- | = Korektnost = | + | **Korektnost** |
V průběhu celého výpočtu platí: | V průběhu celého výpočtu platí: | ||
- | - výška vrcholu nikdy neklesá; | + | * výška vrcholu nikdy neklesá; |
- | - f je pseudotok a pokud kapacity jsou celočíselné, tak i f je; | + | * 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). | + | * 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. | 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 | * 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 | * 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 ===== | ===== Předměty ===== |