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?
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\).
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.
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 Flows
So how do we do that?
Weighted graph with source and sink, figure out the bandwidth.
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.
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.