Flow, matching and tours

Questions 1 to 5 of 8

1. 1. Which statements about one phase of Dinic's method are true?

   Pick every answer that is true.

   The BFS levels are computed on the residual graph, using only edges with positive remaining capacity.The DFS in the phase keeps only edges that go from level k to level k + 1.The current-arc pointer of each vertex moves forward only, and it is reset once per phase.The BFS of the next phase can reuse the levels of this phase, so it does not need to run again.
2. 2. A network has vertices 0 to 3, source 0 and sink 3. The edges are 0 to 1 with capacity 3, 0 to 2 with capacity 2, 1 to 2 with capacity 5, 1 to 3 with capacity 2, and 2 to 3 with capacity 3. What is the maximum flow from 0 to 3?

   Type a number.

3. 3. An AI writes a matching for workers and jobs. It goes through the edges in input order and takes an edge when neither end is used yet. For the edges 0-0, 0-1 and 1-0 it prints 1. What is the best answer, and what is wrong with the code?

   1 is correct, because greedy matching always gives the largest matching in a bipartite graph.2 is correct, because edges 0-1 and 1-0 can both be used. Greedy only gives a lower bound, so the code needs augmenting paths, as in max flow or Hopcroft-Karp.2 is correct, because sorting the edges by the left vertex fixes greedy.3 is correct, because each vertex can be matched twice in a bipartite graph.
4. 4. Which statements about König's theorem are true for a bipartite graph?

   Pick every answer that is true.

   The size of a maximum matching equals the size of a minimum vertex cover.The cover is built by an alternating search that starts from every free left vertex.The theorem holds for any graph, including a triangle.If you find a matching of size 3 and a vertex cover of size 3, no larger matching exists.
5. 5. Match each edge in a min cut construction with what it means.

   Choose the matching item for each row.

   A project with profit p > 0Choose…An edge from the project to the sink, with capacity -pAn edge from the cell to the sink, with capacity c1An edge from i to j with infinite capacityAn edge from the source to the project, with capacity pA project with profit p < 0Choose…An edge from the project to the sink, with capacity -pAn edge from the cell to the sink, with capacity c1An edge from i to j with infinite capacityAn edge from the source to the project, with capacity pProject i needs project jChoose…An edge from the project to the sink, with capacity -pAn edge from the cell to the sink, with capacity c1An edge from i to j with infinite capacityAn edge from the source to the project, with capacity pA grid cell labelled 1, at cost c1Choose…An edge from the project to the sink, with capacity -pAn edge from the cell to the sink, with capacity c1An edge from i to j with infinite capacityAn edge from the source to the project, with capacity p