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