TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 25

The matrix $W$ corresponds to the weight function $w$ of flow network $G=(V,E,w,s,t)$ and the matrix $\varphi$ to a flow $\varphi$ on $G$.

$W=\left(\begin{array}{ccccccc}0& 5& 7& 8& 0& 0& 0\\ 0& 0& 4& 0& 10& 0& 0\\ 0& 0& 0& 5& 3& 11& 0\\ 0& 0& 0& 0& 0& 6& 0\\ 0& 0& 0& 0& 0& 0& 9\\ 0& 0& 0& 0& 0& 0& 4\\ 0& 0& 0& 0& 0& 0& 0\end{array}\right)$, $\varphi =\left(\begin{array}{ccccccc}0& 5& 6& 0& 0& 0& 0\\ 0& 0& 0& 0& 5& 0& 0\\ 0& 0& 0& 1& 2& 3& 0\\ 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 7\\ 0& 0& 0& 0& 0& 0& 4\\ 0& 0& 0& 0& 0& 0& 0\end{array}\right)$.

1. Determine $v(\varphi )$.
2. Find an augmenting path consisting of forward edges only and an augmenting path with at least one backward edge.
3. Find a minimal cut.
4. Find a maximal flow on $G$.

Solution

Network:

Flow:

a)

$v(\Phi )=\sum _{y\in {\Gamma }^{+}(s)}\Phi (sy)=5+6=11$

b)

The figure below shows an augmenting path with an backward edge (orange) and also a path only consisting of forward edges (blue).

c)

The rectangle in the figure above shows the minimal cut of the flow network.

d)

If we add one of the augmenting paths from “b)” to the given initial flow we get the maximum flow of 12 units.

Materialien

Neues Material hinzufügen

A

• Augmenting Path.png (details)