03

Applications: Matching, Disjoint Paths, Scheduling

Chapter 3 • Advanced

150 min

Network Flow Applications

Bipartite Matching

Problem

Find maximum matching in bipartite graph.

Reduction to Max-Flow

  1. Add source connected to all left vertices
  2. Add sink connected to all right vertices
  3. Set all edge capacities to 1
  4. Max flow = max matching
python.js
def bipartite_matching(graph, left_size):
    """Maximum bipartite matching using max-flow"""
    n = len(graph)
    # Create flow network
    flow_graph = [[0] * (n + 2) for _ in range(n + 2)]
    source = n
    sink = n + 1
    
    # Connect source to left vertices
    for i in range(left_size):
        flow_graph[source][i] = 1
    
    # Connect right vertices to sink
    for i in range(left_size, n):
        flow_graph[i][sink] = 1
    
    # Original edges
    for u in range(left_size):
        for v in graph[u]:
            flow_graph[u][v] = 1
    
    return ford_fulkerson(flow_graph, source, sink)

Disjoint Paths

Find maximum number of edge-disjoint paths from s to t.

Solution: Set all capacities to 1, find max-flow.

Image Segmentation

Separate foreground from background.

Practice Problems

  1. Maximum bipartite matching
  2. Edge-disjoint paths
  3. Vertex-disjoint paths
  4. Image segmentation
  5. Project selection
Previous
Min-Cut

Related Tutorials