## 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
```