CMPE177 Syllabus -- Fall 04
- The basics.
Graph definitions. Representations.
Bipartite graphs.
Paths and cycles.
(Sections 1.1-1.8)
- Trees
Characterizations.
Cayley's formula. Minimum Spanning Trees.
Shortest paths.
(Sections 2.1-2.5)
- Graph Search
Depth First and Breadth First numbering.
(supplementary handouts)
- Connectivity
Edge and vertex connectivity. Biconnectivity. Finding
biconnected components.
(Sections 2.2, 2.6 and supplementary handouts)
- Directed graphs
Definitions, direct paths.
Topological sort. Strong connectivity.
Finding strongly connected components.
(Section 7.1, 7.2 and supplementary handouts)
- Network Flow
Flows and cuts. Max-flow min-cut theorem. Augmenting paths. Menger's
theorems.
(Sections 8.1-8.3)
- Euler Tours and Hamiltonian Cycles
Undirected and directed. Chinese Postman problem. Traveling
salesperson problem.
(Sections 3.1-3.4, 7.2, 7.3)
- Planar Graphs
Embeddings. Duals. Euler's formula. Bridges and Kuratowski's theorem.
(Sections 5.1-5.4,5.6)
- Matchings
Maximum matchings. Perfect matchings. Matchings in bipartite graphs.
(Sections 4.1-4.3)
- Colorings (time permitting)
Vertex and edge colorings. (Sections from Chapters 6 and 8.)
The section numbers are from the text,
A First Look at Graph Theory by John Clark and Derek Allan Holton.
The CMPE177 Web:
Copyright 2004; Department of Computer Engineering,
University of California, Santa Cruz.
Comments to:
martine@cse.ucsc.edu