Quiz Space

Advanced Algorithms · Quiz 1 · 29 Oct 2023 · September 2023 term

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

Question 1

+3 marksOne correct option

Which of the following statements is true?

Statement 1: For every graph GG and every maximum flow on GG, 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)(s,t)-flow of some graph has value ff. Now we increase the capacity of every edge by 1. Then the maximum (s,t)(s,t)-flow in this modified graph will have value at most f+1f + 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 1 of 21 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 1 paper sat on 29 Oct 2023, in the September 2023 term (IIT M DEGREE AN2 EXAM QPE2 29 Oct 2023). It carries 3 marks.

More questions from this paper

  1. Q2Consider the following instance of the stable matching problem for 4 men (PQRS) and 4 women (WXYZ). P: W > X > Y > Z\ Q…
  2. Q3Consider 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}. Suppose we are…
  3. Q4Figure question
  4. Q5Figure question
  5. Q6Figure question
  6. 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…
  7. 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…
  8. Q9There 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. Q10Consider the following process. At all times you have a single positive integer x, which is initially equal to 1 . In e…
  10. Q11Consider the following process. At all times you have a single positive integer x, which is initially equal to 1 . In e…
  11. Q12Consider the following process. At all times you have a single positive integer x, which is initially equal to 1 . In e…
  12. Q13A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  13. Q14A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  14. Q15A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  15. Q16A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  16. Q17A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  17. Q18A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  18. Q19A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  19. Q20A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …
  20. Q21A game of Nim is played with n heaps that have a_1, \ldots, a_n stones (in other words, the i-th heap has a_i stones). …