Networks and flows Flashcards
What is a bipartite graph?
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.
What is a matching in a bipartite graph?
A set of edges with the property that no node appears in more than one edge.
What is a perfect matching?
A matching where every node in the graph is matched to exactly one edge.
What is the Bipartite Matching Problem?
The problem of finding the largest matching in a bipartite graph.
How does bipartite matching relate to network flow?
It can be formulated as a maximum-flow problem in a flow network derived from the bipartite graph.
What is a flow network?
A directed graph with edge capacities, a source node, and a sink node.
What are the two main properties a flow must satisfy in a flow network?
- Capacity conditions: 0 ≤ f(e) ≤ c(e) for each edge e.\n2. Conservation conditions: For each internal node, inflow = outflow.
What is the goal of the Maximum-Flow Problem?
To find a flow with the maximum possible value from the source to the sink.
What is the Ford-Fulkerson Algorithm?
An algorithm to find the maximum flow in a network by repeatedly augmenting flow along paths in the residual graph.
What is the residual graph?
A graph that represents the remaining capacity for flow augmentation in a flow network.
What is an augmenting path?
A simple path from the source to the sink in the residual graph, used to increase the flow.
What is the bottleneck of an augmenting path?
The smallest residual capacity of any edge on the path.
What happens during an augmentation in the Ford-Fulkerson Algorithm?
Flow is increased along forward edges and decreased along backward edges of the augmenting path.
What is the Max-Flow Min-Cut Theorem?
In a flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut.
How is the value of a flow defined?
It is the total flow leaving the source (or equivalently, the total flow entering the sink).
What is a cut in a flow network?
A partition of the nodes into two sets such that the source is in one set and the sink is in the other.
What is the capacity of a cut?
The sum of the capacities of all edges going from the source-side of the cut to the sink-side.
How can you prove the Ford-Fulkerson Algorithm terminates?
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.
Why can the Ford-Fulkerson Algorithm fail with real-valued capacities?
Because the flow value may increase in arbitrarily small increments, leading to infinite iterations.
What is the importance of integer capacities in the Ford-Fulkerson Algorithm?
It guarantees termination since the flow increases by at least 1 unit in each iteration.
How do you compute a minimum s-t cut given a maximum flow?
Identify all nodes reachable from the source in the residual graph and partition the nodes based on this reachability.
Design a flow network with 6 nodes where the maximum flow is 10.
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.
Given a bipartite graph with 4 jobs and 4 machines, formulate it as a flow network.
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.
Explain why the residual graph is crucial for the Ford-Fulkerson Algorithm.
It tracks remaining capacities and allows for backward adjustments to flow, enabling iterative improvement.
Create an example where augmenting paths affect the flow solution.
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.
