From 626aa2a2a639f6e354433cce5dedf6555af60cc3 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Tue, 6 May 2014 10:22:20 +0200 Subject: [PATCH] Mer teorem --- flow.tex | 95 +++++++++++++++++++++++++++++++++++++++++++++++-------- total.tex | 2 +- 2 files changed, 82 insertions(+), 15 deletions(-) diff --git a/flow.tex b/flow.tex index b706d4d..5c8ab20 100644 --- a/flow.tex +++ b/flow.tex @@ -254,7 +254,7 @@ operate on to increase the preflow. The algorithm performs two basic operations, the \emph{push} and \emph{relabel} operations, while always maintaining a valid preflow $f$ -and distance labeling $d$. +and a valid distance labeling $d$. \subsubsection{The push procedure} @@ -262,13 +262,15 @@ The push operation moves excess flow from an active vertex along an edge $(u, v) \in E_f$ such that $d(u) = d(v) + 1$, i.e.\ to a vertex with a smaller distance label. We call such edges \emph{admissible}. See Algorithm \ref{alg:push} for a pseudocode implementation of the push -operation. Assuming that $f$ is a valid preflow, it is easy to verify -that $f$ remains a valid preflow after running the push procedure on -some admissible edge $(u, v)$. The capacity constraint is fulfilled -since we at most increase the flow along $(u, v)$ with the residual -capacity $c_f(u,v)$. The preflow constraint is fulfilled since the -excess $e$ increases for $v$, remains non-negative for $u$ and remains -the same for all other vertices. +operation. + +Assuming that $f$ is a valid preflow, it is easy to verify that $f$ +remains a valid preflow after running the push procedure on some +admissible edge $(u, v)$. The capacity constraint is fulfilled since we +at most increase the flow along $(u, v)$ with the residual capacity +$c_f(u,v)$. The preflow constraint is fulfilled since the excess $e$ +increases for $v$, remains non-negative for $u$ and remains the same for +all other vertices. The distance labels are not changed during the push procedure, however, the residual network is changed. The edge $(u, v)$ might disappear, and @@ -279,7 +281,7 @@ $d(u) = d(v) + 1$, so we also have the following d(u) &\leq d(v) + 1 \\ d(v) &\leq d(u) + 1, \end{align} -and $d$ remains a valid labeling. \fixme{not very clear} +and $d$ remains a valid labeling. \fixme{not very clear?} \fixme{Change height $h$ to distance $d$.} @@ -319,15 +321,29 @@ implementation. \label{alg:relabel} \end{algorithm} +\fixme{Relabel: What if the set is empty?} + If $d$ was a valid labeling before running the relabel procedure, then we still have $d(u) \leq d(v) + 1$ for all neighbors $v$ of $u$ in the -residual graph, and $d$ remains a valid labeling. +residual graph, and $d$ remains a valid labeling. The capacity +constraint and preflow constraint remain valid assuming they were +fulfilled before the procedure was started. \subsubsection{Putting it all together} -The idea is now to initialize a valid preflow and distance labeling, and -then run the push and relabel procedures when possible until a maximum -preflow is obtained. - +In the first phase of the algorithm we initialize a valid preflow and +distance labeling by saturating all edges out of the source $s$, and +then setting its distance label $d(s) = N$. We then run the push and +relabel when possible until a maximum preflow is obtained. This phase is +finished when there are no more active nodes. + +\fixme{What is saturated?} + +A node $u$ can only be successfully relabeled to obtain a new label if +the edges outgoing edges of $u$ in the residual network have changed. +This is why the push and relabel procedures often are combined into a +\emph{discharge} procedure as shown in Algorithm \ref{alg:discharge}. +When it is run on an active node $u$, as much as possible of the excess +flow is pushed to other nodes before a relabeling is done. \begin{algorithm} \begin{algorithmic} \Function{Discharge}{$u$} @@ -346,7 +362,58 @@ preflow is obtained. \label{alg:discharge} \end{algorithm} +In the second phase of the algorithm this preflow is turned into a +maximum flow by sending excess flow from inside the network back to the +source. We can skip this part of the algorithm, as we are only +interested in finding a minimum cut, and not the maximum flow. + +The following theorem allows us to find a minimum cut after the firt +phase of the algorithm is finished. +\begin{theorem}[Cut identification] + Given a network $G = (V, E, c)$, assume that the first phase of + the push-relabel algorithm has terminated and no more active nodes + remain. Then there exists an $x \in \mathbb{N} \cap \left(0, + N \right)$ such that there is no vertex with label $x$, and the + vertex sets $S = \{ u : d(u) > x\}$ and $T = V - S$ define a minimum + cut $C = (S, T)$ in $G$. +\end{theorem} +\begin{proof} + \fixme{Sketch of proof, could be nicer, shorter (split up?) and more + rigorous maybe.} + + There are $N$ nodes, the source has label $N$ and the sink has label + $0$, so the $N - 2$ remaining vertices can not occupy all the $N-1$ + other labels, and there must exist an $x$ as described. + + As no vertex has label $x$, the set $T$ contains all (and only) + vertices with labels less than $x$. + + Assume there was an edge non-saturated edge $(u, v) \in E_f$ such + that $u \in S$ and $v \in T$. From the construction of $S$ and $T$, + we have $d(v) \leq d(u) + 2$, which contradicts the valid labeling + constraint stating that $d(u) \leq d(v) + 1$ for every residual + edge. Therefore, no such non-saturated edge from $S$ to $T$ can + exist. From the construction of $E_f$ we now know that all edges + from $S$ to $T$ are saturated, and all edges from $T$ to $S$ have + no flow. This means that the capacity of the cut is equal to the + flow through the cut, i.e.\ $c(S, T) = f(S, T)$. + + Since the first phase of the algorithm has terminated, there can be + no active vertices, and therefore no excess in $T$, except for the + sink. If all flow excess in vertices in $S$ is returned to the + source, we can apply the max-flow min-cut theorem to conclude that + $C = (S, T)$ is a minimum $s$-$t$-cut, since the cut capacity is + equal to the flow from $s$ to $t$. +\end{proof} + +\subsubsection{Complexity} +Bleep bloop. + \subsubsection{Heuristics} +Different heuristics exists that can speed up the algorithm +considerably. Being heuristics, they are not guaranteed to work, and +might perform differently on different kinds of graphs. The most used +heuristics are the gap- and global relabeling heuristics, both \begin{algorithm} \begin{algorithmic} diff --git a/total.tex b/total.tex index a30e159..cf95388 100644 --- a/total.tex +++ b/total.tex @@ -353,7 +353,7 @@ of a possible one-dimensional image. \end{tikzpicture} \caption{Size eight neighborhood.} - \label{fig:c4_grid} + \label{fig:c8_grid} \end{subfigure} \caption{Two common neighborhood stencils.} \label{fig:common_neighborhoods} -- 2.47.3