Potpourri of Graph Things
Andy Novocin
Problem of the day
Suppose we are given an MST of \(G\) with \(n\) vertices and \(m\) edges. A new edge \(e = (u,v)\) of weight \(w\) is added to \(G\). In \(\mathcal{O}(n)\) time find an MST of \(G + e\).
Math Problem of day
Let \(x,y \in \alpha^n\) be \(n\)-letter words in the alphabet \(\alpha\) (a set of characters).
Let \(d(x,y)\) be the Hamming distance between \(x\) and \(y\), that is, the number of positions where they are different.
Show that \(d\) satisfies the properties of a metric. Namely: \(d(x,y) = 0 \iff x = y\); \(d(x,y) = d(y,x)\); and the triangle inequality \(d(x,y) \leq d(x,z) + d(z,y)\).
Interview Question
You are given 12 coins and a balancing scale. One of the 12 is heavier or lighter than the rest. Find it in only 3 weighings.
(Also check out programming pearls)
Programming Assignment 3
Sign up now at:
Steiner Trees
If you were really a phone company laying cable you could put hubs wherever you want.
Given the freedom to create additional nodes, how do you find the minimal minimal spanning tree (the Steiner tree).
Weighted short paths
BFS isn't enough on weighted graphs
The drive home can be improved by taking back roads...
Prim Code
for v in G.V {
v.key = MAXINT;
v.parent = null; }
root.key = 0;
A = [];
PQ = new PriorityQueue(G.V);
while PQ.notEmpty() {
u = PQ.extract-min();
A.push(u);
for v in u.nbrs {
if v in PQ && v.key > weight(u,v) {
v.key = weight(u,v);
v.parent = u; } } }
Dijkstra's Algorithm
for v in G.V {
v.d = MAXINT;
v.parent = null; }
root.d = 0;
A = [];
PQ = new PriorityQueue(G.V);
while PQ.notEmpty() {
u = PQ.extract-min();
A.push(u);
for v in u.nbrs {
if v in PQ && v.d > weight(u,v) + u.d {
v.d = weight(u,v) + u.d;
v.parent = u; } } }
Relaxation concept
Prim, Dijkstra, Bellman-Ford-Moore, Floyd-Warshall all share a concept.
Start with something true but not useful
Iterate, and improve the answer just a bit
Prove that enough iterations will give you an accurate answer.
Bellman-Ford-Moore
for v in G.V {
v.d = MAXINT;
v.parent = null; }
root.d = 0;
for i from 1 to G.V.length - 1 {
for (u,v) in G.E {
if v.d > u.d + weight(u,v):
v.d = weight(u,v) + u.d;
v.parent = u; } }
All pairs shortest path
I could run Dijkstra \(n\) times...
There is a nice slick method though.
Floyd-Warshall
The iteration/relaxation will allow more and more vertices
\(W[i,j]_k\) is the cheapest cost from \(i\) to \(j\) allowing vertices \((1,2,\ldots, k)\)
\(W[i,j]_0\) is just edge cost or \(\infty\).
Key point
Convince yourself that
$$ W[i,j]_k = \min(W[i,j]_{k-1}, W[i,k]_{k-1} + W[k,j]_{k-1})$$
Slick code
W.initialize()
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
ICUP: All pairs shortest paths
HW Problems
I feel the need to work a couple of them for you all.