Toky

Max Flow

Ford-Fulkerson
Capacity Scaling
Shortest Augmenting Path
Push Relabel
Applications

Flow network

Pětice $G = (V, E, s, t, c)$ , kde

$(V, E)$ je orientovaný graf,
$s \in V$ je source (zdroj),
$t \in V$ je sink (odtok),
$c (e) : E \to X$ , kde $X$ jsou obvykle $N_{0}$ nebo $R_{0}^{+}$ , je kapacita hrany $e$ .

$s t$ -řezy

Je rozklad vrcholů na $(A, B)$ takový, že $s \in A$ a $t \in B$ .

Kapacita $s t$ -řezu

Součet kapacit hran na rozhraní $A$ a $B$ :

cap (A, B) = e ven z A \sum c (e)

$s t$ -toky

Funkce $f$ taková, že:

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

Hodnota toku

val (f) = e ven z s \sum f (e) - e do s \sum f (e)

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^{reverse} : f (e) > 0}$ ,
pokud $e = (u, v) \in E$ , $e^{reverse} = (v, u)$ ,
$c_{f} = {c (e) - f (e) f (e) e \in E e^{reverse} \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
}

Max-flow min-cut theorem

Hodnota maximálního toku je rovna kapacitě minimálního řezu.

Ford-Fulkerson vs Goldberg

Ford-Fulkerson	Goldberg
global character	local character
update flow along an augmenting path	update flow on edges
flow conservation	preflow

Ford-Fulkerson

Goldberg

global character

local character

update flow along an augmenting path

update flow on edges

flow conservation

preflow

Ford-Fulkersonova metoda (augmenting path method)

$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
}

Goldbergova metoda (push-relabel method)

Pre-flow

Funkce $f$ taková, že

platí kapacitní podmínka: $(\forall e \in E) (0 \leq f (e) \leq c (e))$ ,
platí relexová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$ .

Tip

Lemma: Pokud je $f$ preflow a $h$ je height function kompatibilní s $f$ , pak neexistuje $s ⇝ t$ cesta v $G_{f}$ .
Důkaz: Nejdelší jednoduchá $s ⇝ t$ cesta má $n$ vrcholů a $n - 1$ hran. Z definice $h$ plyne (kombinací nerovností) $h (s) \leq h (t) + n - 1$ . Protože $h (t)$ je z definice 0, pak $h (s) < n$ , což je spor, protože $h (s) = n$ .

Tip	Lemma Pokud je $f$ flow (tedy zejména preflow) a $h$ je height function kompatibilní s $f$ , pak je $f$ maximální tok.

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

Generic Push-Relabel

Generic-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
}

Amortizovaná složitost Push-Relabel

$O (V^{2} E)$ operací Push nebo Relabel.