Course Outline
In computer science, graph theory is used extensively. The intention of this course is to introduce the subject of graph theory to computer science students in a thorough way. While the course will cover all elementary concepts such as colouring, covering, hamiltonicity, planarity, connectivity and so on, it will also introduce the students to some advanced concepts including Minimum Connector Problem (building roads at minimum cost), the Marriage Problem (matching men and women into compatible pairs), the Assignment Problem (filling n jobs in the best way), the Network Flow Problem (maximizing flow in a network), the Committee Scheduling Problem (using the fewest time slots), the Four Colour Problem (colouring maps with four colours so that adjacent regions have different colours), and the Travelling Salesman Problem (visiting n cities with minimum cost).Prerequisites
Students registering for CSE 3101 must have previously completed course on Discrete Mathematics.Topics Covered
- Fundamental Concepts
Definition, Paths, cycles and trails, vertex degrees and counting
- Trees and Distance
Basic properties, Spanning trees and enumeration, Optimization and Trees
- Matchings and Factors
matching and covers, algorithms and applications, Matching in general graphs
- Connectivity and Paths
Cuts and connectivity, k-connected graphs, Network flow problems
- Colouring of Graphs
Vertex colouring and upper bounds, structure of k-chromatic graphs, enumerative aspects
- Planar Graphs
Embeddings and Euler's formula, Characterizations of planar graphs, Parameters of planarity
- Edges and Cycles
Line graphs and edge colouring, Hamiltonian cycles, Planarity, colouring and cycles
Textbook
Text Book: Douglas B. West, "Introduction to Graph Theory, Pearson Education, 2nd edition, 2008.Grading
- Final Exam: 60%
- Class Test: 20%
- Project: 20%