Answer: As given, we have a flow network G(V,E) with source s and sink t, and all edges have a capacity of one, that is, ce=1 for all e∈E.
To find the maximum number of edge-disjoint paths from s to t in G, we can use the Ford-Fulkerson algorithm, which works as follows:
Start with an empty flow f(e) = 0 for all e ∈ E.
While there exists an augmenting path from s to t in the residual graph Gf:
a. Find an augmenting path p in Gf from s to t.
b. Compute the bottleneck capacity b of path p.
c. Update the flow along path p by adding b to each forward edge and subtracting b from each backward edge.
The maximum flow from s to t is equal to the sum of flow along all edges leaving s in the final residual graph Gf.
To find the maximum number of edge-disjoint paths, we can repeatedly run the Ford-Fulkerson algorithm on G, while removing the edges that are used in the paths found so far. We can stop when we are unable to find any more paths from s to t in the residual graph.
Each path found by the Ford-Fulkerson algorithm corresponds to a single edge-disjoint path from s to t in the original graph G, as the flow along each edge is either 0 or 1. Therefore, the maximum number of edge-disjoint paths from s to t in G is equal to the maximum flow from s to t in G.
Since all edges in G have a capacity of 1, the maximum flow from s to t in G will be equal to the maximum number of edge-disjoint paths from s to t. We can use the Ford-Fulkerson algorithm to compute this value.