Quiz Space

Advanced Algorithms · Quiz 1 · 13 Jul 2025 · May 2025 term

Question 10: Given a flow network (G, s, t, c) and a flow f, how will…

Question 10

+4 marksOne correct option

Given a flow network (G, s, t, c) and a flow f, how will you determine if f is maximum flow?

  1. A

    If there is any edge that is not saturated to full capacity, then we can conclude that f is not a maximum flow.

  2. B

    If the residual graph does not have any augmenting paths then f is a maximum flow.

  3. C

    If the value of the flow f is not the sum of the capacities of the edges coming out of the source s then f is not a maximum flow.

  4. D

    If the value of the flow f is not the sum of the capacities of the edges coming into the sink t then f is not a maximum flow.

Show answer

Correct answer

  • B

    If the residual graph does not have any augmenting paths then f is a maximum flow.

See the whole paperTake it as a mock test

Question 10 of 26 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 1 paper sat on 13 Jul 2025, in the May 2025 term (IIT M DEGREE AN EXAM QDB2 13 July 2025). It carries 4 marks.

More questions from this paper

  1. Q1Based on the above data, answer the given subquestions.
  2. Q2Based on the above data, answer the given subquestions.
  3. Q3Based on the above data, answer the given subquestions.
  4. Q4Consider the given problem, called BoxDepth: Given a set of n axis-aligned rectangles in the plane, how big is the larg…
  5. Q5Consider the given problem, called BoxDepth: Given a set of n axis-aligned rectangles in the plane, how big is the larg…
  6. Q6Consider the given problem, called BoxDepth: Given a set of n axis-aligned rectangles in the plane, how big is the larg…
  7. Q7Suppose your friend comes up with an algorithm to solve Partition in time O(nM), where n is the size of the input set a…
  8. Q8The problem AllOrNothing3Sat asks, given a 3CNF boolean formula, whether there is an assignment to the variables such t…
  9. Q9Which of the following statements is true about a flow network?
  10. Q11In this question, we consider a card game called SWISH.\ In the commercial version of SWISH, there are 60 transparent c…
  11. Q12In this question, we consider a card game called SWISH.\ In the commercial version of SWISH, there are 60 transparent c…
  12. Q13In this question, we consider a card game called SWISH.\ In the commercial version of SWISH, there are 60 transparent c…
  13. Q14In this question, we consider a card game called SWISH.\ In the commercial version of SWISH, there are 60 transparent c…
  14. Q15Let n and N be positive integers, and let \mathcal{F} be an arbitrary nonempty family of subsets of the universe {1, \l…
  15. Q16Let n and N be positive integers, and let \mathcal{F} be an arbitrary nonempty family of subsets of the universe {1, \l…
  16. Q17Let n and N be positive integers, and let \mathcal{F} be an arbitrary nonempty family of subsets of the universe {1, \l…
  17. Q18Let n and N be positive integers, and let \mathcal{F} be an arbitrary nonempty family of subsets of the universe {1, \l…
  18. Q19Let n and N be positive integers, and let \mathcal{F} be an arbitrary nonempty family of subsets of the universe {1, \l…
  19. Q20Let n and N be positive integers, and let \mathcal{F} be an arbitrary nonempty family of subsets of the universe {1, \l…
  20. Q21Let n and N be positive integers, and let \mathcal{F} be an arbitrary nonempty family of subsets of the universe {1, \l…
  21. Q22Let n and N be positive integers, and let \mathcal{F} be an arbitrary nonempty family of subsets of the universe {1, \l…
  22. Q23Let n and N be positive integers, and let \mathcal{F} be an arbitrary nonempty family of subsets of the universe {1, \l…
  23. Q24Let n and N be positive integers, and let \mathcal{F} be an arbitrary nonempty family of subsets of the universe {1, \l…
  24. Q25Let n and N be positive integers, and let \mathcal{F} be an arbitrary nonempty family of subsets of the universe {1, \l…
  25. Q26Let n and N be positive integers, and let \mathcal{F} be an arbitrary nonempty family of subsets of the universe {1, \l…