Graphs and Algorithms Outline

Prerequisites: Math 224 or CPSC 141 or CPSC 242. A computing language is desirable.

Course Materials: Course Notes will be placed in the copy store. Several books (listed in order of decreasing relevance to the course) can be used, but only the first book will be needed, mostly for the exercises. Homework assignments will be distributed in class. Some additional materials will also be distributed in class. Texts:

Graphs and Applications, by Joan Aldous and Robin Wilson, 2000, Springer.
Networks and Algorithms: An introductory approach, by Alan Dolan and Joan Aldous, 1993, Wiley.
Discrete and combinatorial mathematics, by Ralph Grimaldi (5th edition), 2004, Pearson. Earlier editions of this text can be equally useful.
Graphs: An introductory approach, by Robin Wilson and John Watkins, 1990, Wiley.

Course Description: The interaction between mathematics and computer science has proved fundamental to the vitality of both fields over the last 40 years; nowhere is this more true than in the area of combinatorics and graph theory. Graph-theoretic tools arise in virtually every area of computational study: Network design and analysis, database theory, artificial intelligence, and matrix computations are just a few of the areas in which sophisticated graph-theoretic tools are routinely used. By the same reason, computational studies have focused much research attention on graph theory. In a sense, the fruitfulness of this interplay is to be expected, since graphs are natural models of the finite structures that computers by their very nature manipulate. Other application of graphs include problems in telecommunication, transportation, oil exploration, scheduling, traffic control and map colouring. The course deals with both mathematical aspects and applications of graph theory.

Topics will be chosen among the following: Graphs, Eulerian and Hamiltonian Graphs, Digraphs, Matchings, Application to Job Assignment Problems, Matrix Representations, Tree Structures, Counting Trees, Greedy Algorithms, Path Algorithms, Introduction to Networks: Network Analysis, Flows and Connectivity, Maximum Flow and Minimum Cost Flow in a Network, Multi-Terminal Flows, Application to Telecommunication Networks; Connectivity, Planarity, Vertex Colourings and Decompositions, Edge Colourings and Decompositions, Scheduling, Combinatorial Generation: Permutations, Combinations, Lexicographic Order; Design of Experiments and Graphs, Survey of Computer Search Methods: Local Search Algorithms: Hill-Climbing, Simulated Annealing, Record-to-Record Travel, Tabu Search, Genetic Algorithms, Problem Dependent Optimization.

Evaluation:

Assignments:	25%
Midterm (Fri, Oct 23):	25%
Final Exam:	50%