MA3L302
Undergraduate (ITEP)
· Generally offered: Autumn
Graph theory
L 3 T 1 P 0 Credits 4 Hours 4
Unit I: Isomorphism, incidence and adjacency matrices, Sperner lemma, Trees, Cayley formula,
connector problem, connectivity, constructing reliable communication network.
Unit II: Euler tours, Hamilton cycle, Chinese postman and traveling salesman problems.
Unit III: Matchings and coverings, perfect matchings, edge colouring, Vizing Theorem, time table problem, Independent sets, Ramsey theorem, Turan theorem, Schur theorem, vertex colouring, Brook theorem, Hajos conjecture, chromatic polynomials, storage problem.
Unit IV: Planarity, dual graphs, Euler formula, Kuratowski theorem, five colour theorem, history of four colour theorem, nonhamiltonian planar graphs, planarity algorithm, directed graphs, job sequencing, one way road system, ranking participants in tournaments.
Full syllabus document →
Unit II: Euler tours, Hamilton cycle, Chinese postman and traveling salesman problems.
Unit III: Matchings and coverings, perfect matchings, edge colouring, Vizing Theorem, time table problem, Independent sets, Ramsey theorem, Turan theorem, Schur theorem, vertex colouring, Brook theorem, Hajos conjecture, chromatic polynomials, storage problem.
Unit IV: Planarity, dual graphs, Euler formula, Kuratowski theorem, five colour theorem, history of four colour theorem, nonhamiltonian planar graphs, planarity algorithm, directed graphs, job sequencing, one way road system, ranking participants in tournaments.
0 questions tagged to this course
No questions tagged to this course yet — ask one.