Discrete Structures20815 marks
What is network flow? Give an example of saturated edge, unsaturated edge, and slack.
What is network flow? Give an example of saturated edge, unsaturated edge, and slack. [5]
A network flow (or transport network) is a directed graph G = (V, E) where each edge e has an associated capacity C(e) 0, a designated source node S (only outgoing flow) and a sink/destination node D (only incoming flow). All other vertices are called intermediate vertices. The network flow probl...