Graph Flows

Andy Novocin

Problem of the day


Can we modify Dijkstra's algorithm to solve the single-source longest path problem by changing the minimum to maximum? If so, then prove your algorithm correct. If not, then provide a counterexample.

Math Problem of day


Let \(A\) be the adjacency matrix of a simple unweighted graph.


Let \(\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n\) be the eigenvalues of \(A\) (duplicates allowed).


What is the value of \(\sum \lambda_i\)?


What is the value of \(\sum \lambda_i^2 / 2\)?


(Subject: Spectral Graph Theory. Hint: \(\sum \lambda_i^k\) )

Interview Question


You have a computer with only 2Mb of main memory. How do you use it to sort a large file of 500Mb that is on disk?


More nuanced version here

Transitive Closure


The Transitive Closure of \(G = (V, E) \) is the graph \(G' = (V, E')\) with an edge \( (u,v) \in E'\) whenever there is a path from \(u\) to \(v\) in \(G\).

Transitive Closure

TC vs All pairs short path


In Floyd-Warshall we spit out a distance graph \(W\).


How can you read TC from \(W\)?


We can convert \(W\) into the Transitive Closure('s adjacency matrix) by sending any \(W[i,j] == \infty\) to 0, and the others to 1.

ICUP Convert to Boolean TC

W.initialize()//0's and 1's
for k in range(G.V.length):
  for i in range(G.V.length):
    for j in range(G.V.length):
      w_through_k = W[i][k] + W[k][j]
      if w_through_k < W[i][j]:
        W[i][j] = w_through_k
        

Graph Matching


A matching is any subset of edges such that no vertices are shared.


A maximum matching is a matching with the most possible edges.

Maximum matching

ICUP Max Matching

Bipartite Matching


If you can color a graph with two colors (bipartite) then we can reduce the matching problem to a flow problem.


Concept: Create a new node, \(s\), the source, and another, \(t\), the sink.


Make a hose from \(s\) to all of the nodes of one color, and a hose to \(t\) from each of the rest.


Now max flow from \(s\) to \(t\) goes through maximum matching of original graph.

Applications


Bipartite matching is useful for partnering things


Online Dating Services, Jobs to Candidates, Arranged Marriages en Masse, Executive Assistants to Judges, whatever.

Maximum "Bipartite" Flow

Maximum Flows


So how do we do that?


Weighted graph with source and sink, figure out the bandwidth.


(Casual treatment at Irene's coding blog)

Interpretation


The weights are capacity to hold flow.


(It probably required calculus to get this data.)


For instance throughput of a highway, amps flowing through a route in a circuit, cross-sectional area of a sewer pipe, students/hour hostable at office hours, etc.

Min-Cut == Max-Flow


Recall graph cuts, \( S, V - S\), any partition of the vertices.


Suppose \(S\) has \(s\) and \(V-S\) has \(t\) then the total flow from \(S\) to \(V-S\) must be at least as much as the max-flow from \(s \to t\) .


That means EVERY cut gives an upper bound to flow.


The cut which minimizes flow from \(S\) to \(V-S\) ACTUALLY IS the maximum flow from \(s\) to \(t\).

ICUP Find the minimum cut 1/3

ICUP Find the minimum cut 2/3

ICUP Find the minimum cut 3/3

Ford-Fulkerson (Edmonds-Karp)


The classical algorithm for finding max flow will also say how much flow travels through each edge.


I'll explain the name thing in a bit.

High level version


Give each edge an extra attribute for flow (weight is capacity).


Find any possible (the bottleneck capacity is not zero) path (allow backwards) from source to sink.


Send a maximum (bottleneck) amount of flow through that path (reduce capacity attribute and increase flow attribute)


Repeat until no more paths (augmenting paths) are possible.

Helpful Video

Requiring Backwards

Max-Flow Naming


Ford-Fulkerson gave the idea of incrementally increasing the flow with "augmenting paths" from \(s \to t\).


Edmonds-Karp proved a better complexity if you chose your paths via BFS.

ICUP Try it out!

Watch on Visualgo


Watch this slowly