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:


http://doodle.com/n5hibzvdekycpdxa

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).

Connect These Nodes

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 is key

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.

New toy!


Visualgo

ICUP: Perform Dijkstra

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
        

All Pairs

ICUP: All pairs shortest paths

HW Problems


I feel the need to work a couple of them for you all.