Quiz Space

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

Question 9: Which of the following statements is true?\ Statement 1: …

Question 9

+3 marksOne correct option

Which of the following statements is true?
Statement 1: For every graph G and every maximum flow on G, there always exists an edge such that increasing the capacity on that edge will increase the maximum flow that’s possible in the graph.
Statement 2: Suppose the maximum (s, t)-flow of some graph has value f. Now we increase the capacity of every edge by 1. Then the maximum (s, t)-flow in this modified graph will have value at most f + 1.

  1. A

    Statement 1

  2. B

    Statement 2

  3. C

    Both statements

  4. D

    Neither statement

Show answer

Correct answer

  • D

    Neither statement

See the whole paperTake it as a mock test

Question 9 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 3 marks.

This question was also asked in

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. Q10Figure question
  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 …