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

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


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.