Quiz Space

Advanced Algorithms · Quiz 2 · 6 Aug 2023 · May 2023 term

Advanced Algorithms Quiz 2 6 Aug 2023 — Question 10

Question 10

+2 marksOne correct option
  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 15 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 2 paper sat on 6 Aug 2023, in the May 2023 term (IIT M DEGREE AN3 EXAM QPE3 06 Aug 2023). It carries 2 marks.

More questions from this paper

  1. Q1For the following sets of timings of dance classes, figure out what is the largest number of classes that you can atten…
  2. Q2Consider 4 sets as follows: W = {w_1, w_2, w_3}, X = {x_1, x_2}, Y = {y_1, y_2, y_3} and Z = {z_1, z_2}. Given capacity…
  3. Q3Let G be a simple, undirected, unweighted graph. We use V(G) to denote the vertex set of G and E(G) to denote the edge …
  4. Q4Let G be a simple, undirected, unweighted graph. We use V(G) to denote the vertex set of G and E(G) to denote the edge …
  5. Q5There are N stones, numbered 1, 2, \ldots, N. For each (1 \leqslant i \leqslant N), the height of stone i is h_i. Assum…
  6. Q6There are N stones, numbered 1, 2, \ldots, N. For each (1 \leqslant i \leqslant N), the height of stone i is h_i. Assum…
  7. Q7There are N stones, numbered 1, 2, \ldots, N. For each (1 \leqslant i \leqslant N), the height of stone i is h_i. Assum…
  8. Q8There are N stones, numbered 1, 2, \ldots, N. For each (1 \leqslant i \leqslant N), the height of stone i is h_i. Assum…
  9. Q9Which of the following statements is true?\ Statement 1: For every graph G and every maximum flow on G, there always ex…
  10. Q11Figure question
  11. Q12Consider the following definitions: A vertex cover is a subset S of V(G) such that for all (u,v) \in E(G), S \cap {u,v}…
  12. Q13Figure question
  13. Q14Figure question
  14. Q15Consider a different rounding strategy for the LP relaxation of the vertex cover problem. Instead of rounding up every …