Maximum Flow Problem Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Maximum Flow Problem”.

1. What does Maximum flow problem involve?
a) finding a flow between source and sink that is maximum
b) finding a flow between source and sink that is minimum
c) finding the shortest path between source and sink
d) computing a minimum spanning tree
View Answer

2. A network can have only one source and one sink.
a) False
b) True
View Answer

3. What is the source?
a) Vertex with no incoming edges
b) Vertex with no leaving edges
c) Centre vertex
d) Vertex with the least weight
View Answer

4. Which algorithm is used to solve a maximum flow problem?
a) Prim’s algorithm
b) Kruskal’s algorithm
c) Dijkstra’s algorithm
d) Ford-Fulkerson algorithm
View Answer

5. Does Ford- Fulkerson algorithm use the idea of?
a) Naïve greedy algorithm approach
b) Residual graphs
c) Minimum cut
d) Minimum spanning tree
View Answer

6. The first step in the naïve greedy algorithm is?
a) analysing the zero flow
b) calculating the maximum flow using trial and error
c) adding flows with higher values
d) reversing flow if required
View Answer

7. Under what condition can a vertex combine and distribute flow in any manner?
a) It may violate edge capacities
b) It should maintain flow conservation
c) The vertex should be a source vertex
d) The vertex should be a sink vertex
View Answer

8. Find the maximum flow from the following graph.

a) 22
b) 17
c) 15
d) 20
View Answer

9. A simple acyclic path between source and sink which pass through only positive weighted edges is called?
a) augmenting path
b) critical path
c) residual path
d) maximum path
View Answer

10. In what time can an augmented path be found?
a) O(|E| log |V|)
b) O(|E|)
c) O(|E|²)
d) O(|E|² log |V|)
View Answer

11. Dinic’s algorithm runs faster than the Ford-Fulkerson algorithm.
a) true
b) false
View Answer

12. What is the running time of an unweighted shortest path algorithm whose augmenting path is the path with the least number of edges?
a) O(|E|)
b) O(|E||V|)
c) O(|E|²|V|)
d) O(|E| log |V|)
View Answer

13. Who is the formulator of Maximum flow problem?
a) Lester R. Ford and Delbert R. Fulkerson
b) T.E. Harris and F.S. Ross
c) Y.A. Dinitz
d) Kruskal
View Answer

14. What is the running time of Dinic’s blocking flow algorithm?
a) O(V²E)
b) O(VE²)
c) O(V³)
d) O(E max |f|)
View Answer

15. How many constraints does flow have?
a) one
b) three
c) two
d) four
View Answer

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]