Grafy a grafové algoritmy

Note	Reprezentace grafů. Souvislost grafu, rovinné grafy. Prohledávání grafu do šířky a do hloubky, nejkratší vzdálenosti, kostry, toky v sítích. Algoritmy: Bellman-Ford, Dijkstra, Ford-Fulkerson, Push-Relabel, maximální párování v bipartitních grafech. IB000, IB002, IV003

Tip	Tahle otázka má solidní překryv s bakalářskými otázkami Grafy a Grafové problémy.

Terminologie

Graf

Dvojice $G = (V, E)$ kde:

$V$ je množina vrcholů; $∣ V ∣ = n$ ,
$E$ je množina hran; $∣ E ∣ = m$ ,
hrana $e \in E$ je dvojice vrcholů $e = (u, v)$ .

Váha grafu

Váha grafu je součet vah hran grafu $G$ .

w (G) = e \in E (G) \sum w (e)

Bipartitní graf

Graf jehož vrcholy lze rozdělit do dvou disjunktních množin tak, že všechny hrany vedou z jedné množiny do druhé.

Obrázek 1. Example of bipartite graph without cycles by Watchduck

(Silná) souvislost grafu / (strongly) connected graph

Graf $G$ je souvislý, pokud pro každé dva vrcholy $u, v \in V (G)$ existuje cesta z $u$ do $v$ .

Slabá souvislost grafu / weakly connected graph

Graf $G$ je slabě souvislý, pokud je souvislý jeho podgraf $G^{'}$ vzniklý odebráním orientace hran.

Je souvislý alespoň, pokud zapomeneme, že hrany mají směr?

Silně souvislá komponenta / strongly connected component

Silně souvislá komponenta grafu $G$ je jeho maximální podgraf $G^{'}$ takový, že je silně souvislý. Jinými slovy pro každé dva vrcholy $u, v \in V (G^{'})$ existuje cesta z $u$ do $v$ .

Planární / rovinný graf

Graf $G$ je planární, pokud se dá nakreslit do roviny tak, že se žádné dvě hrany nekříží.

Platí v nich Eulerova formule:

∣ V ∣ - ∣ E ∣ + ∣ F ∣ = 2

Kde $∣ F ∣$ je počet stěn — oblastí ohraničených hranami.

Vrcholy planárního grafu lze vždy obarvit 4 barvami tak, že žádné dva sousední vrcholy nebudou mít stejnou barvu.

(Hranový) řez / (edge) cut

Množina hran $C \subseteq E (G)$ taková, že po odebrání hran $C$ se graf $G$ rozpadne na více komponent — $G^{'} = (V, E ∖ C)$ není souvislý.

Analogicky se definuje i vrcholový řez / vertex cut.

Reprezentace grafů

Seznam následníků / adjacency list: Pro každý vrchol $v \in V$ máme seznam (např. dynamic array nebo linked list) $N (v)$ jeho následníků.

Zabírá $Θ (∣ V ∣ + ∣ E ∣)$ paměti.
Matice sousednosti / adjacency matrix: Máme matici velikosti $∣ V ∣ \times ∣ V ∣$ kde $A_{u, v} = 1$ pokud existuje hrana mezi $u$ a $v$ , jinak $A_{u, v} = 0$ .

Dá se pěkně použít k uložení vah.
Matice incidence / incidence matrix: Máme matici velikosti $∣ V ∣ \times ∣ E ∣$ kde $A_{u, e} = 1$ pokud $u$ je vrcholem hrany $e$ , jinak $A_{u, e} = 0$ .

Dá se z ní pěkně určit stupeň vrcholu.

Prohledávání grafu

Prohlédávání do šířky / breadth-first search (BFS)

Od zadaného vrcholu navštíví nejprve vrcholy vzdálené 1 hranou, poté vrcholy vzdálené 2 hranami, atd.

Prohledávání po "vrstvách".
Je implementovaný pomocí fronty (queue / FIFO).
Časová složitost je $O (∣ V ∣ + ∣ E ∣)$ .

def dfs(graph: List[List[bool]], stamps: List[int], vertex: int) -> None:
    if stamps[vertex] == -1:
        stamps[vertex] = 0
    stamp = stamps[vertex]
    for i in range(0, len(graph)):
        if graph[vertex][i] and stamps[i] != -1:
            stamps[i] = stamp + 1
            dfs(graph, stamps, i)

Prohlédávání do hloubky / depth-first search (DFS)

Od zadaného vrcholu rekurzivně navštěvuje jeho nenavštívené následníky.

Prohledání po "slepých uličkách".
Vynořuje se teprve ve chvíli, kdy nemá kam dál (backtrackuje).
Je implementovaný pomocí zásobníku (stack / LIFO).
Časová složitost je $O (∣ V ∣ + ∣ E ∣)$ .

def bfs(graph: List[List[bool]], stamps: List[int], vertex: int) -> None:
    stamp = 0
    queue = deque()
    queue.append(vertex)
    while len(queue) > 0:
        current = queue.popleft()
        stamps[current] = stamp
        stamp += 1
        for i in range(0, len(graph)):
            if graph[current][i] and stamps[i] == -1:
                queue.append(i)

Nejkratší vzdálenosti

Problém nalezení buď nejkratší cesty mezi dvěma vrcholy nebo nejkratší cesty z jednoho vrcholu do všech ostatních.

Relaxace hrany $(u, v)$: Zkrácení vzdálenosti k vrcholu $v$ průchodem přes vrchol $u$ . Musí platit $u .distance + w (u, v) < v .distance$ . Hrana $(u, v)$ je v takovém případě napjatá.

Bellman-Fordův algoritmus

Hledá nejkratší cesty z jednoho vrcholu do všech ostatních.

Využívá relaxaci hran.
Funguje i na grafech se zápornými hranami.
Má časovou složitost $O (∣ V ∣ \cdot ∣ E ∣)$ .

def bellmanford(graph: List[List[Tuple[int, int]]], s: int) \
        -> Tuple[bool, List[int], List[int]]:
    # graph is an adjacency list of tuples (dst, weight)
    distance = [float('inf') for i in range(0, len(graph))]
    distance[s] = 0
    parent = [-1 for i in range(0, len(graph))]

    # relax all edges |V| - 1 times
    for _ in range(1, len(graph)):
        for u in range(0, len(graph)):
            for edge in graph[u]:
                (v, w) = edge
                if distance[u] + w < distance[v]:
                    distance[v] = distance[u] + w
                    parent[v] = u

    # check for negative cycles
    for u in range(0, len(graph)):
        for edge in graph[u]:
            (v, w) = edge
            if distance[u] + w < distance[v]:
                return (False, None, None)

    return (True, distance, parent)

Dijkstrův algoritmus

Hledá nejkratší cesty z jednoho vrcholu do všech ostatních.

Je podobný BFS, ale používá prioritní frontu.
Funguje pouze na grafech bez záporných hran.

Tip	Složitost závisí na implementaci prioritní fronty. Je to $Θ (V)$ insertů, $Θ (V)$ hledání nejmenšího prvku, $Θ (E)$ snížení priority.

Note	Implementace níže používá pole (resp. Pythoní `list`), tedy složitost je $Θ (V^{2})$ , jelikož hledání minima je lineární.

def dijkstra(graph: List[List[Tuple[int, int]]], s: int) \
        -> Tuple[List[int], List[int]]:
    # graph is an adjacency list of tuples (dst, weight)
    distance = [float('inf') for i in range(0, len(graph))]
    distance[s] = 0
    parent = [-1 for i in range(0, len(graph))]

    queue = list(range(0, len(graph)))
    while len(queue) > 0:
        u = min(queue, lambda v: distance[v])
        queue.remove(u)
        for edge in graph[current]:
            (v, w) = edge
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                parent[v] = u
    return (distance, parent)

V binární haldě by to bylo $Θ (V lo g V + E lo g V)$ a ve Fibonacciho haldě $Θ (V lo g V + E)$ .

Dijkstrův algoritmus lze optimalizovat, pokud nás zajímá jen nejkratší cesta mezi dvěma konkrétními vrcholy:

Funkce vrátí výsledek, jakmile je cílový vrchol vytažen z fronty.
Můžeme hledat zároveň ze začátku a konce pomocí dvou front a skončit, jakmile se někde potkají.
Můžeme přidat potenciál — dodatečnou heuristickou váhu.

Important
Téhle variantě se říká A* (A star). Věnuje se mu část otázky Umělá inteligence v počítačových hrách.

Kostry

Spanning tree / kostra

Kostra grafu $G = (V, E)$ je podgraf $T \subseteq G$ takový, že $V (T) = V (G)$ je $T$ je strom.

Minimum spanning tree (MST) / minimální kostra

Je kostra $M$ grafu $G$ s nejmenší možnou váhou. Tedy pro každou kostru $T$ grafu $G$ :

w (M) \leq w (T)

Fundamental cycle

Fundamental cycle je cyklus $C$ v grafu $G$ takový, že odebráním libovolné hrany $e \in C$ získáme kostru.

Fundamental cutset / řez

Fundamental cutset je množina hran $D$ v grafu $G$ taková, že přidáním libovolné hrany $e \in D$ získáme kostru.

Red rule

Najdi cyklus bez červených hran, vyber v něm neobarvenou hranu s nejvyšší cenou a obarvi ji červeně.

Blue rule

Najdi řez bez modrých hran, vyber v něm neobarvenou hranu s nejmenší cenou a obarvi ji modře.

Greedy algoritmus

Nedeterministicky aplikuj red rule a blue rule, dokud to jde (stačí $n - 1$ iterací). Modré hrany tvoří MST.

Jarníkův / Primův algoritmus

Speciální případ greedy algoritmu, kdy aplikujeme pouze blue rule. Princip:

Vyber libovolný vrchol $v$ a přidej ho do kostry $S$ .
Opakuj $n - 1$ krát:
1. Vyber hranu $e$ s nejmenší cenou, která má právě jeden vrchol v $S$ .
2. Přidej druhý vrchol $e$ do $S$ .

Složitost: použijeme binární haldu

Inicializace ( $\infty$ jako cena hrany mezi prázdnou kostrou a každým vrcholem): $O (∣ V ∣)$
Odstranění minima z binární haldy pro každý vrchol ve $V$ : $O (∣ V ∣ lo g ∣ V ∣)$
Procházení každé hrany z $E$ a snižování ceny: $O (∣ E ∣ lo g ∣ V ∣)$
Celková složitost: $O (∣ E ∣ lo g ∣ V ∣)$
S Fibonacciho haldou jde zlepšit na: $O (∣ E ∣ + ∣ V ∣ lo g ∣ V ∣)$

Kruskalův algoritmus

Princip: Seřaď hrany podle ceny vzestupně. Postupně přidávej hrany do kostry, vynechej ty, které by vytvořily cyklus.

Seřad hrany podle ceny vzestupně.
Použij union-find na udržování komponent grafu.
Procházej hrany postupně. Pokud oba konce hrany patří do různých množin, přidej ji.

Je to speciální případ greedy algoritmu.

Složitost:

Inicializace union-findu: $O (∣ V ∣)$
Seřazení hran: $O (∣ E ∣ lo g ∣ E ∣)$
Pro každou hranu provádíme dvakrát find ( $O (lo g ∣ V ∣)$ ) a eventuálně union ( $O (lo g ∣ V ∣)$ ): $O (∣ E ∣ lo g ∣ V ∣)$
Celková složitost: $O (∣ E ∣ lo g ∣ V ∣)$

Borůvkův algoritmus

Je "paralelní". Buduje modré stromy ze všech vrcholů naráz.

Pro každý vrchol inicializuj modrý strom.
Dokud nemáš jen jeden modrý strom, opakuj fázi:
1. Pro každý modrý strom najdi nejlevnější odchozí hranu a přidej ji (propojíš tak dva stromy).

Je to speciální případ greedy algoritmu, který spamuje jen blue rule.

Složitost:

Počet komponent v první fázi: $∣ V ∣$ .
V každé fázi se zmenší počet komponent na polovin. Tím pádem bude $lo g ∣ V ∣$ fází.
Každá fáze zabere $O (∣ E ∣)$ času, protože procházíme všechny hrany.
Celková složitost: $O (∣ E ∣ lo g ∣ V ∣)$

Tip	Kruskal sice taky buduje stromy na více místech najednou, ale není "paralelní", protože minimalita kostry spoléhá na to, že hrany jsou seřazené. Borůvka takový požadavek nemá, a proto je paralelizovatelnější.

Tabulka 1. Složitosti algoritmů
Algoritmus	Časová složitost	Prostorová složitost
Jarník (Prim) s prioritní frontou	$O (∣ E ∣ lo g ∣ V ∣)$	$O (∣ V ∣)$
Jarník (Prim) s Fibonacciho haldou	$O (∣ E ∣ + ∣ V ∣ lo g ∣ V ∣)$	$O (∣ V ∣)$
Kruskal	$O (∣ E ∣ lo g ∣ V ∣)$	$O (∣ V ∣)$
Borůvka	$O (∣ E ∣ lo g ∣ V ∣)$	$O (∣ V ∣)$

Toky v sítích

Síť toků / flow network

Je čtveřice $(G, s, t, c)$ , kde:

$G = (V, E)$ je orientovaný graf,
$s \in V$ je zdroj / source,
$t \in V$ je cíl / stok / sink; $s \neq = t$ ,
$c : E \to R^{+}$ je funkce udávající kapacitu hran.

Network flow / tok

Je funkce $f : E \to R^{+}$ , která splňuje:

podmínku kapacity: $(\forall e \in E) (f (e) \geq 0 \land f (e) \leq c (e))$
- tok hranou je nezáporný a nepřevyšuje povolennou kapacitu
podmínku kontinuity: $(\forall v \in V ∖ {s, t}) (\sum_{e \in δ^{+} (v)} f (e) = \sum_{e \in δ^{-} (v)} f (e))$
- tok do vrcholu je stejný jako tok z vrcholu

Hodnota toku $f$

∣ f ∣ = (s, v) \in E \sum f (s, v) = (w, t) \in E \sum f (w, t)

Ford-Fulkerson

Residual network

Síť, která vzniká, když je už část kapacity hrany využívána tokem $f$ . Umožnuje algoritmům změnit přechozí rozhodnutí a získat využitou kapacitu zpět.

Je to pětice $G_{f} = (V, E_{f}, s, t, c_{f})$ , kde

$E_{f} = {e \in E : f (e) < c (e)} \cup {e^{R} : f (e) > 0}$ ,
pokud $e = (u, v) \in E$ , $e^{R} = (v, u)$ ,
$c_{f} (e) = {c (e) - f (e) f (e) pokud e \in E pokud e^{R} \in E$

Augmenting path $P$

Jednoduchá $s ⇝ t$ cesta v residuální síti $G_{f}$ .

Note	T.j. cesta která může jít i proti směru toku $f$ .

Bottleneck kapacita je nejmenší kapacita hran v augmenting path $P$ .

To krásné na augmenting cestách je, že pro flow $f$ a augmenting path $P$ v grafu $G_{f}$ , existuje tok $f^{'}$ takový, že $val (f^{'}) = val (f) + bottleneck (G_{f}, P)$ . Nový tok $f^{'}$ lze získat takto:

Augment(f, c, P)
{
    delta = bottleneck(P)
    foreach(e in P)
    {
        if(e in E)
        {
            f[e] = f[e] + delta
        }
        else
        {
            f[reverse(e)] = f[reverse(e)] - delta
        }
    }
    return f
}

Algoritmus Ford-Fulkerson

Hledá maximální tok. Augmentuje cestu v residuální síti dokud to jde.

$f (e) = 0$ pro každou $e \in E$ .
Najdi $s ⇝ t$ cestu $P$ v reziduální síti $G_{f}$ .
Augmentuj tok podél $P$ .
Opakuj dokud se nezasekneš.

Ford-Fulkerson(G)
{
    foreach (e in E)
    {
        f(e) = 0
    }

    G_f = reziduální síť vzniklá z G vzhledem k toku f
    while (existuje s ~> t cesta v G_f)
    {
        f = Augment(f, c, P)
        Updatuj G_f
    }
    return f
}

Push-Relabel

Pre-flow

Ne-tak-docela tok.

Funkce $f$ taková, že

platí kapacitní podmínka: $(\forall e \in E) (0 \leq f (e) \leq c (e))$ ,
platí relaxováné zachování toku: $(\forall v \in V - {s, t}) (\sum_{e do v} f (e) \geq \sum_{e ven z v} f (e))$ .

Overflowing vertex

Takový vertex $v \in V - {s, t}$ , do kterého více přitéká než odtéká.

e do v \sum f (e) > e ven z v \sum f (e)

Excess flow

To, co je v overflowing vertexu navíc.

e_{f} (v) = e do v \sum f (e) - e ven z v \sum f (e)

Height function

Funkce $h : V \to N_{0}$ . Řekneme, že $h$ je kompatibilní s preflow $f$ , právě když

source: $h (s) = ∣ V ∣ = n$ ,
sink: $h (t) = 0$ ,
height difference: $(\forall (v, w) \in E_{G_{f}}) (h (v) \leq h (w) + 1)$ .

Note
Pokud mezi dvěma vrcholy $(v, w)$ v reziduální síti vede hrana, pak je $v$ nejvýše o jednu úroveň výš než $w$ .

Push operace

Pro (reziduálně-grafovou) hranu $(v, w)$ se pokusí přesunout excess flow z $v$ do $w$ , aniž by porušil (reziduální) kapacitu $(v, w)$ .

// Assumptions: e_f[v] > 0, c_f( (v, w) > 0) > 0, h[v] > h[w]
Push(f, h, v, w)
{
    delta_f = min(e_f[v], c_f(v, w))
    if( (v, w) in E)
        f[(v, w)] += delta_f
    else
        f[(w, v)] -= delta_f
    e_f[v] -= delta_f
    e_f[w] += delta_f
}

Relabel operace

Zvýší výšku $h (v)$ natolik, aby neporušil kompatibilitu $h$ s $f$ .

// Assumptions:
//   - v is overflowing: e_f[v] > 0
//   - all residual neighbors of v the same height or higher:
//     forall (v, w) in E_f: h[v] <= h[w]
Relabel(f, h, v)
{
    h[v] = 1 + min(h[w] | (v, w) in E_f)
}

Algoritmus Push-Relabel (Goldberg-Tarjan)

Hledá maximální tok.

Princip: Pokud je nějaký vrchol overflowing, tak ho pushni nebo relabeluj. Pokud ne, tak jsi našel maximální tok.

Push-Relabel(V, E, s, t, c)
{
    // initialize preflow — default values
    for(v in V)
    {
        h[v] = 0    // height function
        e_f[v] = 0  // excess flow
    }
    n = |V|
    h[s] = n

    for(e in E)
    {
        f[e] = 0    // (pre)flow
    }

    // initialize preflow — saturate connections from s
    for( (s, v) in E)
    {
        f[(s, v)] = c(s, v) // preflow maxes out all capacity
        e_f[v] = c(s, v)    // presume all of it excess
        e_f[s] -= c(s, v)   // yes, it will be negative
    }

    // the juicy part
    while(any vertex is overflowing)
    {
        v = an overflowing vertex (has e_f[v] > 0)
        if(v has a neighbor w in G_f such that h(v) > h(w))
        {
            Push(f, h, v, w)
        }
        else
        {
            Relabel(f, h, v)
        }
    }
    return f
}

Korektnost: V průběhu výpočtu platí:

Výška vrcholu nikdy neklesá.
Pre-flow a výšková funkce jsou kompatibilní.

Složitost:

Nejvýše $2^{n}$ Relabelů.
$2 nm$ saturujících Push.
$4 n^{2} m$ nesaturujících Push.
Relabel i Push jsou v $O (1)$ .
Celkem: $O (n^{2} m)$ .

⁂

Tabulka 2. Srovnání algoritmů Ford-Fulkerson a Push-Relabel
Ford-Fulkerson	Push-Relabel (Goldberg)
global character	local character
update flow along an augmenting path	update flow on edges
flow conservation	preflow

Maximální párování v bipartitních grafech

Párování / matching

Množina $M \subseteq E$ taková, že žádné dvě hrany v $M$ nemají společný vrchol. [4]

Prázdná množina je párováním na každém grafu. Graf bez hran má pouze prázdné párování.

Obrázek 2. Příklad párování, které je zároveň maximální by RRPPGG

Maximální párování

Takové párování, které má nejvyšší počet hran. Graf může mít několik maximálních párování.

Perfektní párování

Takové párování, které páruje všechny vrcholy grafu. Každé perfektní párování je zároveň maximální.

Maximum cardinality matching (MCM) v bipartitním grafu

Problém nalezení maximálního párování v grafu. Ve speciálním případě, kdy graf je bipartitní, se tento problém dá převést na problém nalezení maximálního toku v síti: [5]

Mejmě bipartitní graf $G = (X + Y, E)$ .
Přidej zdroj $s$ a hranu $(s, v)$ pro každý vrchol $v$ z $X$ .
Přidej stok $t$ a ranu $(v, t)$ pro každý vrchol $v$ z $Y$ .
Každé hraně dej kapacitu 1.
Spusť algoritmus Ford-Fulkerson.