Predavanje 6.4.
Primer.
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
node [label=""]
SFO [xlabel=s]
JFK [xlabel=t]
SFO -> DEN [taillabel=1, headlabel=0, color=red]
SFO -> IAH [taillabel=2, headlabel=0]
DEN -> ATL [taillabel=2, headlabel=0, color=red]
DEN -> ORD [taillabel=3, headlabel=0]
IAH -> ATL [taillabel=3, headlabel=0]
ATL -> JFK [taillabel=1, headlabel=0, color=red]
ORD -> JFK [taillabel=2, headlabel=0]
}
Povečamo pretok na izbrani poti za 1:
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
SFO [label="", xlabel=s]
DEN [label=""]
IAH [label=""]
ATL [label=""]
ORD [label=""]
JFK [label="", xlabel=t]
SFO -> DEN [taillabel=0, headlabel=1, style=bold]
SFO -> IAH [taillabel=2, headlabel=0, color=red]
DEN -> ATL [taillabel=1, headlabel=1, color=red]
DEN -> ORD [taillabel=3, headlabel=0, color=red]
IAH -> ATL [taillabel=3, headlabel=0, color=red]
ATL -> JFK [taillabel=0, headlabel=1, style=bold]
ORD -> JFK [taillabel=2, headlabel=0, color=red]
}
Najbolj nas omejuje obratna povezava - spet povečamo pretok za $1$:
digraph G {
rankdir=LR
nodesep=0.5
ranksep=1
node [label=""]
SFO [xlabel=s]
JFK [xlabel=t]
SFO -> DEN [taillabel=0, headlabel=1, style=bold]
SFO -> IAH [taillabel=1, headlabel=1]
DEN -> ATL [taillabel=2, headlabel=0]
DEN -> ORD [taillabel=2, headlabel=1]
IAH -> ATL [taillabel=2, headlabel=1]
ATL -> JFK [taillabel=0, headlabel=1, style=bold]
ORD -> JFK [taillabel=1, headlabel=1]
}
Takih poti ni več - imamo optimalno rešitev.
Definicija. Za problem maksimalnega pretoka na usmerjenem grafu $G = (V, E)$ ter začetnim vozliščem $s$ in končnim vozliščem $t$ je množica $C \subseteq V$ je prerez, če velja $s \in C$, $t \not\in C$.
Za vsaki vozlišči $u, v \in V$, tako da velja $uv \not\in E$, naj velja $x_{uv} = 0$. Potem lahko Kirchhoffove zakone pišemo kot $$ \forall w \in V \setminus \{s, t\}: \ \sum_{u \in V} x_{uw} = \sum_{v \in V} x_{wv} $$
Seštejmo za vsak $w \in C \setminus \{s\}$: $$ \sum_{\substack{u \in V \\ v \in C \setminus \{s\}}} x_{uv} = \sum_{\substack{u \in C \setminus \{s\} \\ v \in V}} x_{uv} $$
Členi $x_{uv}$, kjer $u, v \in C \setminus \{s\}$, se pojavijo na obeh straneh in se jih lahko znebimo: $$ \sum_{\substack{u \not\in C \setminus \{s\} \\ v \in C \setminus \{s\}}} x_{uv} = \sum_{\substack{u \in C \setminus \{s\} \\ v \not\in C \setminus \{s\}}} x_{uv} $$
Ker $s$ ni končno vozlišče nobene povezave, velja $$ \sum_{\substack{u \in C \\ v \not\in C}} x_{uv} - \sum_{\substack{u \not\in C \\ v \in C}} x_{uv} = \sum_{v \not\in C} x_{sv} + \sum_{\substack{u \in C \setminus \{s\} \\ v \not\in C \setminus \{s\}}} x_{uv} - \left(\sum_{\substack{u \not\in C \setminus \{s\} \\ v \in C \setminus \{s\}}} x_{uv} - \sum_{v \in C} x_{sv}\right) = \sum_{v \in V} x_{sv} = F $$
Prostornina pretoka torej zadošča enakosti $$ F = \sum_{\substack{u \in C \\ v \not\in C}} x_{uv} - \sum_{\substack{u \not\in C \\ v \in C}} x_{uv} $$
Definirajmo še kapaciteto prereza $C$ kot $$ K = \sum_{\substack{u \in C \\ v \not\in C}} d_{uv} $$
Trditev. Naj bosta $x$ in $C$ pretok s prostornino $F$ in prerez s kapaciteto $K$ za problem maksimalnega pretoka. Potem velja $F \le K$.
Dokaz. $$ F = \sum_{\substack{u \in C \\ v \not\in C}} x_{uv} - \sum_{\substack{u \not\in C \\ v \in C}} x_{uv} \le \sum_{\substack{u \in C \\ v \not\in C}} d_{uv} - \sum_{\substack{u \not\in C \\ v \in C}} 0 = K $$
Opomba. Primerjaj s šibkim izrekom o dualnosti!
Posledica. Če velja $F = K$, je $x$ maksimalen pretok, $C$ pa minimalen prerez.
Govorimo torej o problemu maksimalnega pretoka in minimalnega prereza (angl. maximal flow/minimal cut).
Izrek. Za problem maksimalnega pretoka in minimalnega prereza velja natanko ena od sledečih možnosti.
- Problem maksimalnega pretoka je neomejen, kapaciteta vsakega prereza je $\infty$.
- Obstajata maksimalen pretok $x$ in minimalen prerez $C$, tako da je prostornina $x$ enaka kapaciteti $C$.
Opomba. Primerjaj s krepkim izrekom o dualnosti!
Dokaz. Problem maksimalnega pretoka na usmerjenem grafu $G = (V, E)$ s pretočnostmi $d_e$ ($e \in E$) ter začetnim vozliščem $s$ in končnim vozliščem $t$ je dopusten linearni program, saj je ničelni pretok dopustna rešitev. Če je neomejen, po zgornji trditvi ne obstaja prerez s končno kapaciteto (sicer bi imeli zgornjo mejo za prostornino).
V nasprotnem primeru naj bo $x$ optimalna drevesna rešitev pridruženega problema razvoza z omejitvami za drevo $T = (V, E')$. Naj bodo $y$ razvozne cene. Ker velja $d_{ts} = \infty$, povezava $ts$ ni nasičena. Ker velja $c_{ts} = -1$, sledi $y_t \ge y_s + 1 > y_s$. Potem je $$ C = \{v \in V \mid y_v \le y_s\} $$ prerez, saj velja $s \in C$ in $t \not\in C$. Določimo prostornino pretoka $x$.
- Če $u \in C$, $v \not\in C$, potem $y_u + c_{uv} \le y_s < y_v$, torej $uv \not\in E'$ in $x_{uv} = d_{uv}$ (nasičena povezava).
- Če $u \not\in C$, $v \in C$, potem $y_u + c_{uv} > y_s \ge y_v$, torej $uv \not\in E'$ in $x_{uv} = 0$ (prazna povezava).
Tako velja $$ F = \sum_{\substack{u \in C \\ v \not\in C}} x_{uv} - \sum_{\substack{u \not\in C \\ v \in C}} x_{uv} = \sum_{\substack{u \in C \\ v \not\in C}} d_{uv} = K $$ Sledi, da je $x$ maksimalni pretok in $C$ minimalni prerez.