Notes

Outline

Some graphs you may have met under different circumstances.

Course prerequisites Topological sort gives order to take classes

Maze

Depth first search – Web as graph Avoid loops: don’t repeat nodes. Use some kind of Set ADT

Electronic circuits Edges labelled (resistors, switch, etc) Analyze Zasha’s incompetence in EE

Profiler call frequency info

Compiler analysis – Common Subexpression Elimination

Proofs – best case correct sorting by comparison List is x1,…,x8 Edge is comparison <7 edges à graph not connected Connected components could be on either side. How would the algorithm know?

(small part of) Java class hierarchy

Cheapest Computer Network – Minimum Spanning Tree

Capacity of highways – max flow

TA assignments Bipartite graph – 2 node types (TAs and Courses) Maximal matching (assign as many TAs to as many courses as possible)

Six degrees of Kevin Bacon

Six degrees of Kevin Bacon