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