Obsah

Zadání

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.

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

+ váhovaný graf, multigraf

Reprezentace grafů

Seznamy následníků
Maticí sousednosti

Souvislost grafu

Silně souvislá komponenta je takový maximální podgraf orientovaného grafu, v němž pro každou dvojici vrcholů u, v existuje sled.

Řezy

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 \chi(G) (= velké chí).

Rovinné grafy (= planární)

Věta (Eulerova formule): V rovinném grafu G=(V, E) platí:
1. |V| − |E| + s = |E|+2. (s = počet stěn)
2. |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.

Algoritmy

Včetně složitosti a základní myšlenky důkazů korektnosti!

n= |V|

m = |E|

Prohledávání grafu

algoritmus složitost
BFS \mathcal{O}(m + n)
DFS \mathcal{O}(m + n)

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: \mathcal{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í \mathcal{O}(n)
  • seznam sousedů vrcholu se prochází, jen když je vrchol odstraňován z fronty, takže dohromady \mathcal{O}(m)
  • = \mathcal{O}(m+n)

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).

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ů

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)
algoritmus (1-to-n) složitost typ grafu
BFS \mathcal{O}(m+n) vzdálenost = počet hran
Dijkstrův algoritmus \mathcal{O}(m + n * \log n) nezáporné délky hran
Bellman-Ford \mathcal{O}(m * n)
algoritmus (n-to-n) složitost typ grafu
Násobení matic \mathcal{O}(n^3 * \log n)
Floyd-Warshall \mathcal{O}(n^3)
Johnson \mathcal{O}(n^2 * \log n + m * n)
Hledání nejkratších cest z jednoho vrcholu do všech

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)]

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
Hledání nejkratších cest mezi všemi vrcholy

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)

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)

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

Kostry

Pravidla použitá při definici/důkazech:
(viz slidy MA015)

Cut Property

Pokud je e nejlehčí hrana přes nějaký řez G, pak e \in M.

Blue rule: Pro daný řez bez modrých hran vybereme neobarvenou hranu a obarvíme ji modře.

Cycle Property

Pokud je e nejtěžší hrana nějakého cyklu v G, pak e \notin M.

Red rule: Pro daný cyklus neobsahující žádnou červenou hranu vybereme maximální neobarvenou hranu a obarvíme ji na červeno.

algoritmus složitost
Borůvka \mathcal{O}(m * \log n)
Kruskal \mathcal{O}(m * \log n)
Jarník \mathcal{O}(m * |DECREASE-KEY| + n * |EXTRACT-MIN|)
Fredman-Tarjan (Jarník + Fibonacciho halda) \mathcal{O}(m + n * \log n)
Fredman-Tarjan (limit velikosti haldy) \mathcal{O}(m * \beta (m, n))
Gabow et al. (F-T + packeting) \mathcal{O}(m * \log \beta (m, n))

Kruskal

  • Budujeme modrý les.
  • 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í

Jarník (Prim)

  • Budujeme modrý strom.
  • 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.

Borůvka

  • Budujeme modré stromy 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ýš \log n fází
  • každá fáze zabere \mathcal{O}(m) (musíme projít přes všechny hrany)
  • celkem: \mathcal{O}(m * \log n)

Toky v sítích

Flow network („toková síť“) je čtveřice (G,s,t,c):

Network flow (tok v síti) je funkce f:E \rightarrow R^{+} splňující:

Ford-Fulkerson: MAX-FLOW=MIN-CUT

hodnota maximálního toku = kapacita minimálního řezu

Reziduální síť

Reziduální graf
  • graf G_f = (V,E_f), kde pro každou hranu e = (u,v) \in E obsahuje E_f:
    • e = (u,v) pokud f(e) \textless c(e)
    • e^R = (v,u) pokud f(e) \textgreater 0

Reziduální kapacita

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}

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 e hodnotu přičteme
  • pro e^R hodnotu odečteme
algoritmus složitost
Ford-Fulkerson \mathcal{O}(nm * C) C – nejvyšší kapacita
Edmonds-Karp (FF + shortest aug. path) \mathcal{O}(m^2n)
Dinitz (saturate all s-t paths in G_f)\mathcal{O}(mn^2)
MPM (three indians)\mathcal{O}(n^3)
push-relabel\mathcal{O}(mn^2)

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 Reá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

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

Předměty

Související otázky