Graph Theory, part 1

Google Video

Graphs_Intro.pdf Graphs_Intro.sws

1. Definitions, morphisms
2. Basic flavor of graph theory
3. Graph spectra
4. Trees
5. Example algorithm: girth
6. Some suggestions for graph theory projects (see Robert M. if you're interested):
   1. Generate trees in time linear in the output.
   2. Graph visualization.
   3. Other kinds of incidence structures.

   4. Improve G.genus().

   5. Subgraph isomorphism.
   6. Hamiltonian cycles.
   7. Bipartite matching problems.
   8. A distributed eigenvector function.