Chapter 7

• Matching in bipartite graphs can model situations in which objects are being assigned to other objects
  • Nodes in X represent jobs, and the nodes in Y represent machines, and an edge (xi,yj) indicates that machine yj is capable of processing job xi.
• Perfect Matching: a way of assigning each job to a machine that can process it
  • Property that each machine is assigned exactly one job
• One of the oldest problems in combinatorial algorithms: determining the size of the largest matching in a bipartite graph G
  • Network Flow Problems: includes the Bipartite Matching Problem as a special case

The Problem

• Transportation Networks: networks whose edges carry some sort of traffic and whose nodes act as “switches” passing traffic between different edges
  • capacities on the edges
  • source nodes in the graph, which generate traffic
  • sink (or destination) nodes, which can “absorb” traffic as it arrives
  • traffic, which is transmitted across the edges

• Flow Networks
  • traffic = flow
  • associated with each edge e is a capacity, ce
  • single source node s in V
  • single sink node t in V
  • all other nodes besides s and t are internal nodes
  • no edge enters s and no edge leaves t
  • at least one edge incident to each edge
  • all capacities are integers
• Defining Flow
  • s-t flow is a function f that maps each edge e to a nonnegative real number, f
    • Flow must follow two properties:
      • Capacity: for each e in E: we have 0 ⇐ f(e) ⇐ ce
      • Conservation: for each node v other than s and t: sum of the flow value f(e) over all edges entering node v = sum of the flow values over all edges leaving node v

• The Maximum-Flow Problem
  • goal: arrange the traffic for maximum efficiency of the available capacity
    • given a flow network, find a flow network
  • Each “cut” of the graph puts a bound on the maximum possible flow value
    • maximum-flow algorithm here will be intertwined with a proof that the maximum flow value equals the minimum capacity of any such division, called the minimum cut.