Network Flows and Ford-Fulkerson Algorithm

We will label all the vertices different from \( s \) and \( t \) with letters \( A \), \( B \), \( C \), \( D \), \( E \), \( F \), \( G \), \( H \), \( I \), \( J \), \( K \), \( L \), \( M \), \( N \). We label them column by column starting from left. The first column contains \( A \) and \( B \), the second contains \( C \), \( D \), and \( E \), etc. Consider the sets \( S=\left\{s, A,B,C,D,E, G\right\} \) and \( T=\left\{F, H, I,J,K,L,M,N,t\right\} \). Observe that \( [S,T] \) is a source/sink cut and that its capacity is 35. Observe that the flow \( f \) that satisfies: \begin{eqnarray*} && f(s,A)=10, f(A,C)=10, f(C,F)=10, f(F,J)=10, f(J,M)=10,\newline && f(s,B)=25, f(B,E)=25, f(E,I)=15, f(I,L)=15, f(L,N)=5,\newline && f(N,t)=5, f(E,D)=10, f(D,G)=10, f(G,H)=10, f(H,L)=10,\newline && f(L,K)=20, f(K,M)=20, f(M,t)=30 ,\newline && f(e)=0,\mbox{ for every other edge }e \end{eqnarray*} has value equal to 35. Since the capacity of every cut is greater than or equal to the value of every flow, we conclude that the maximal value of a flow is \( 35 \).

We will label all the vertices different from \( s \) and \( t \) with letters \( A \), \( B \), \( C \), \( D \), \( E \), \( F \), \( G \), \( H \), \( I \), \( J \), \( K \), \( L \), \( M \), \( N \). We label them column by column from top to bottom starting from left. The first column contains \( A \) and \( B \), the second contains \( C \), \( D \), and \( E \), etc. Consider the sets \( S=\left\{s, A,B,C,D,E, H\right\} \) and \( T=\left\{F, G, I,J,K,L,M,N,t\right\} \). Observe that \( [S,T] \) is a source/sink cut and that its capacity is 25. Observe that the flow \( f \) that satisfies: \begin{eqnarray*} && f(s,A)=10, f(A,C)=10, f(C,F)=10, f(F,J)=10,\newline && f(s,B)=15, f(B,E)=15, f(E,I)=5, f(I,L)=5,\newline && f(L,N)=5, f(N,t)=5, f(E,D)=10, f(D,H)=10,\newline && f(H,G)=10, f(G,J)=10, f(J,M)=20, f(M,t)=20,\newline && f(e)=0,\mbox{ for every other edge }e \end{eqnarray*} has value equal to 25. Since the capacity of every cut is greater than or equal to the value of every flow, we conclude that the maximal value of a flow is \( 25 \).

An augmenting path is \((s,C,B,t)\). Its tolerance is \(10\). The improved flow has the following values: \(f(s,A)=10\), \(f(A,B)=10\), \(f(B,t)=10\), \(f(B,C)=0\), \(f(A,C)=10\), \(f(C,t)=10\). The total value of this flow is \(20\). This new flow has maximal value because there is a cut with capacity \(20\). Such cut has \(S=\{s,A,B,C\}\) and \(T=\{t\}\).