CMPE 177: Applied Graph Theory and Algorithms 
 
Catalog copy 
 CMPE177. Applied Graph Theory and Algorithms. F Basic concepts and
 algorithms are reviewed including trees, Eulerian and Hamiltonian
 graphs, and graph transversal.  Algorithms are explored to solve
 problems in connectivity, routing, matching, and embedding of graphs.
 Graph theory and algorithms are developed around applications in
 computer engineering. Prerequisite(s): Computer Science
 101. M. Schlag

Explanation of pre-requisite: 
 CMPS 101:  The presentation of advanced graph algorithms assumes familiarity 
  with basic algorithms, proofs of correctness and analysis techniques. 
  Students must be familiar with proof techniques (including mathematical
  induction) to understand involved proofs of graph properties and derive
  their own proofs. The ability to construct, debug and manage a large program 
  is required for the class project in which students must implement their
  own approach to solving a graph problem. 

Required skills to pass the course.
 1. Knowledge of basic graph definition and properties.
   a. Characterization of trees.
   b. Characterization of bipartite graphs.
   c. Characterization of planar graphs.
   d. Characterization of Euler graphs.
   e. Properties of directed graphs.
   f. Edge and vertex connectivity properties and relation to flow.
 2. Knowledge of fundamental algorithms including:
   a. Breadth-first search.
   b. Depth-first search.
   c. Shortest path algorithms.
   d. Minimum spanning tree algorithms.
   e. Topological sort.
   f. Ford-Fulkerson network flow.
 3. The ability to recognize and apply graph properties and algorithms
    to solve a problem.
 4. The ability to implement graph algorithms.
 5. The ability to construct proofs of graph properties.

Core topics (must be taught)
 1. Graph definitions.
   a. Directed and undirected graphs.
   b. Paths and cycles.
   c. Complete and bipartite graphs.
 2. Properties of trees.
   a. Characterization of trees.
   b. Cayley's theorem.
   c. Minimum spanning tree algorithms (Prim's and Kruskal's).
 3. Basic graph algorithms.
   a. Breadth-first search.
   b. Depth-first search.
   c. Shortest path algorithms (Djikstra, Floyd-Warshall, Bellman-Ford).
 4. Connectivity
   a. Vertex and edge connectivity properties.
   b. Characterization of biconnected graphs.
   c. Depth-first search for identifying biconnected components.
   d. Depth-first search for identifying strongly connected components.
   e. Topological sorts of directed acyclic graphs.
 5. Eulerian graphs.
   a. Characterization of Eulerian graphs.
   b. Algorithm for constructing Euler circuits.
 6. Hamiltonian graphs.
   a. Characterization of Hamiltonian graphs
 7. Network Flow.
   a. Definition of network flows and cuts. 
   b. Max-Flow Min-Cut Theorem.
   c. Ford-Fulkerson algorithm.
   d. Relation of flow to the number of disjoint paths (Menger's Theorems).
 8. Planar graphs. 
   a. Definition of planarity, embedding, bridge, and Euler number. 
   b. Euler's formula.
   c. Kuratowski's theorem (proof is optional).
   d. Demoucron's algorithm for planarity testing.
 9. Matching.
   a. Definition of matching, maximum matching, and perfect matchings. 
   b. Notion of augmenting path.
   c. Finding maximum matchings in bipartite graphs.

Optional topics 
 1. Matrix-Tree Theorem
 2. Traveling salesman problem.
 3. Chinese postman problem.
 4. Layering algorithm for network flow.
 5. Proof of Kuratowski's theorem.
 6. Graph coloring

Core lab:
 1. Project. 
    Students are given a graph problem which has no known
    efficient solution and are asked to develop and implement  
    a method to solve it using the graph algorithms they have
    learned. They implement their algorithm in either C or C++
    and measure its effectiveness quantitatively.  They submit
    their code along with a project report describing their methods,
    their results, and the strengths and weaknesses of their approach.
  
Comments on related concurrent courses 
  CMPS 102 Introduction to Analysis of Algorithms covers advanced
  algorithms though not focussing on graphs. or graph theory.
  Math 115 Grapth Theory covers graph theory with an emphasis
  on proving mathematical properties of graphs rather than 
  applying them.


Comments on following courses:
  CMPE 177 is one of four options required for CMPS 140 Artificial Intelligence.
  It is also recommended preparation for graduate students 
  before attempting CMPS 201 Analysis of Algorithms.
  

Text 
 John Clark and Derek Allan Holton, "A First Look at Graph Theory" 
 World Scientific 1991. Paperback. ISBN 981-02-0490-6 
 This book covers the required graph theory at a level suitable for
 senior undergraduates.  Its coverage of graph algorithms 
 is weak and so the text is supplemented with handouts on graph algorithms.

 Handouts for the algorithms not provided in the text are supplied on-line.  
 See http://www.cse.ucsc.edu/classes/cmpe177/Fall98.

Prepared by Martine Schlag 10/02.