## Goodbye Graphs

### A fond farewell

#### Andy Novocin

## Problem of the day

### A matching in a graph is a set of disjoint edges (i.e. edges that do not share any vertices). Give a linear-time algorithm to find a maximum matching in a tree.

## Interview Question

####
Six pirates must divide $300 among themselves.
The division is to proceed as follows.
The senior pirate proposes a way to divide the money. Then the pirates vote.
If the senior pirate gets at least half the votes he wins, and that division remains.
If he doesn't, he is killed and then the next senior-most pirate gets a chance
to do the division. Now you have to tell what will happen and why
(i.e. how many pirates get killed and how is the money divided).
All the pirates are intelligent and the first priority is to stay alive
and the next priority is to get as much money as possible
(and they want to elevate their rank only after that).

## No class Tuesday (4th)

## AND Test2 Thursday (6th)

##### Graph flavors (simple, directed, weighted, acyclic, sparse)

##### Adjacency Matrices vs Adjacency Lists

##### Traversal (BFS, DFS, and Riding the rails)

##### Edge classifications (Tree, Forward, Back, Cross)

##### BFS: Finding short paths, Root distance

##### BFS: Bipartite detection

##### BFS: Connected Components

##### DFS: Ancestry, Parentheses property

##### DFS: Find cycles

##### DFS: Find articulation vertices

##### DFS: Topological Sorting

##### Strongly Connected Components

##### Minimum Spanning Trees

##### Graph Cuts, "Safe" edges, Bridges

##### Prim, Kruskal, Boruvka

##### Union-Find

##### Weighted Short Paths

##### Dijkstra, Floyd-Warshall

##### Transitive Closure

##### Matchings

##### Maximum Flow / Minimum Cut

##### Principles for spotting graph problems

### Don't forget (final is cumulative) you also have the powers of:

##### RAM model

##### big-Oh Analysis

##### Logarithms

##### Counter-Examples and Correctness

##### Arrays vs Linked-Lists

##### Stacks vs Queues

##### Dictionaries

##### Binary Search Trees

##### Priority Queues

##### Hash Tables

##### Heaps

##### Selection and Insertion Sorts

##### Merge Sort

##### Quicksort

##### Binary Search and friends

##### Techniques for applying these

## So what next?

### 1) A taste of real world graph theory

### 2) Practice for the test

### THEN (11th) We start the hard stuff!

## Explore these

### Art Gallery Guarding (Open for results)

### Stable Marriage Problem (Nobel prize)

### Graph Isomorphism (Don't know if P or NP)

### Ramsey Numbers (At a party of at least 6 people some 3 will know each other or not know each other).

### Transfer Matrix Method (How many words of length k in letters a and b don't have consecutive b's?)

### Random Walks on graphs!

## Practice Problems

### Work any problems from chapter 5 or chapter 6 with weight \( \leq 5\)