0
$\begingroup$

Given: $D = (V,A)$ a directed graph and $s,t \in V$
Problem: Show that the maximum number of pairwise arc-disjoint directed $s-t$ paths is equal to the maximum value of the flow $f$ where $f$ is subject to capacity function $c$.
Approach: first show "$\leq$" and then show ''$\geq$''

"$\leq$":
$$\begin{array}{l} \text{Take } c =1 \text{ for all arcs}. & (1) \\ \text{ Let }P_1,..,P_k \text{ be arc-disjoint directed } s-t \text{ paths.} &(2) \\ \text{Then } f = \chi ^{A(P_1)} +...+ \chi ^{A(P_n)} \text{ is an } s-t \text{ flow and } 0\leq f \leq c & (3) \\ [f \leq c \text{ since } P_1,..,P_k \text{ are arc-disjoint] } &(4) \\ \text{ Moreover, } \text{value($f$)} = k &(5) \\ \end{array}$$

This is how it was written down by my teacher. But I don't understand how he concludes this less of equal inequality. In line 2 you begin with $k $- paths and then in line (5) you conclude that value(f) = k , but why does "$\leq$" hold ?

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.