Networks and flows

Question 1

What is a bipartite graph?

Answer 1

A graph whose node set can be partitioned into two sets, X and Y, such that every edge connects a node in X to a node in Y.

Question 2

What is a matching in a bipartite graph?

Answer 2

A set of edges with the property that no node appears in more than one edge.

Question 3

What is a perfect matching?

Answer 3

A matching where every node in the graph is matched to exactly one edge.

Question 4

What is the Bipartite Matching Problem?

Answer 4

The problem of finding the largest matching in a bipartite graph.

Question 5

How does bipartite matching relate to network flow?

Answer 5

It can be formulated as a maximum-flow problem in a flow network derived from the bipartite graph.

Question 6

What is a flow network?

Answer 6

A directed graph with edge capacities, a source node, and a sink node.

Question 7

What are the two main properties a flow must satisfy in a flow network?

Answer 7

1. Capacity conditions: 0 ≤ f(e) ≤ c(e) for each edge e.\n2. Conservation conditions: For each internal node, inflow = outflow.

Question 8

What is the goal of the Maximum-Flow Problem?

Answer 8

To find a flow with the maximum possible value from the source to the sink.

Question 9

What is the Ford-Fulkerson Algorithm?

Answer 9

An algorithm to find the maximum flow in a network by repeatedly augmenting flow along paths in the residual graph.

Question 10

What is the residual graph?

Answer 10

A graph that represents the remaining capacity for flow augmentation in a flow network.

Question 11

What is an augmenting path?

Answer 11

A simple path from the source to the sink in the residual graph, used to increase the flow.

Question 12

What is the bottleneck of an augmenting path?

Answer 12

The smallest residual capacity of any edge on the path.

Question 13

What happens during an augmentation in the Ford-Fulkerson Algorithm?

Answer 13

Flow is increased along forward edges and decreased along backward edges of the augmenting path.

Question 14

What is the Max-Flow Min-Cut Theorem?

Answer 14

In a flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut.

Question 15

How is the value of a flow defined?

Answer 15

It is the total flow leaving the source (or equivalently, the total flow entering the sink).

Question 16

What is a cut in a flow network?

Answer 16

A partition of the nodes into two sets such that the source is in one set and the sink is in the other.

Question 17

What is the capacity of a cut?

Answer 17

The sum of the capacities of all edges going from the source-side of the cut to the sink-side.

Question 18

How can you prove the Ford-Fulkerson Algorithm terminates?

Answer 18

By showing that the flow value increases by at least 1 in each iteration and is bounded by the total capacity of outgoing edges from the source.

Question 19

Why can the Ford-Fulkerson Algorithm fail with real-valued capacities?

Answer 19

Because the flow value may increase in arbitrarily small increments, leading to infinite iterations.

Question 20

What is the importance of integer capacities in the Ford-Fulkerson Algorithm?

Answer 20

It guarantees termination since the flow increases by at least 1 unit in each iteration.

Question 21

How do you compute a minimum s-t cut given a maximum flow?

Answer 21

Identify all nodes reachable from the source in the residual graph and partition the nodes based on this reachability.

Question 22

Design a flow network with 6 nodes where the maximum flow is 10.

Answer 22

Create a graph with nodes {s, a, b, c, d, t} and edges with capacities: s->a: 5, s->b: 5, a->c: 5, b->d: 5, c->t: 5, d->t: 5. Maximum flow: 10.

Question 23

Given a bipartite graph with 4 jobs and 4 machines, formulate it as a flow network.

Answer 23

Add a source connected to all jobs, a sink connected to all machines, and edges between jobs and machines representing possible assignments, all with capacity 1.

Question 24

Explain why the residual graph is crucial for the Ford-Fulkerson Algorithm.

Answer 24

It tracks remaining capacities and allows for backward adjustments to flow, enabling iterative improvement.

Question 25

Create an example where augmenting paths affect the flow solution.

Answer 25

In a graph with nodes {s, u, v, t} and edges s->u: 10, u->v: 5, v->t: 10, initial augmentation uses s->u->v->t with bottleneck 5, but a different path s->v->t could use 10 directly.