Consider a flow network as a directed graph G where each edge (u, v) has a capac

Question

Consider a flow network as a directed graph G where each edge (u, v) has a capacity c(u,v) greaterthanequalto 0. We designate a source node s and a sink node t. Recall that a cut (S,T) is a partition of the nodes into sets S and T with s epslon S and t epslon T. The capacity of the cut (S,T) is the sum of the capacities of the edges that go from a vertex in 5 to a vertex in T. Is it possible to have such a G where the max flow from s to t is 13 and there exists a cut (S,T) with capacity 10? Explain your answer. Consider an directed graph G, containing vertices s,u,t (along with many others). Describe an efficient way to compute the number of edge disjoint paths between s and t that do not go through the vertex u.

Explanation / Answer

Answer:

A)

No it is not possibke because the maximum flow cant be more than the cappacity of the cut..

B)

1. Find the maximum flow in G
2. Start walking from s
3. If a cycle is created eliminate the flow around the cycle
4. If you reach t then output the path you used to reach t

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.