CourseItem

Description

The course introduces graphs in all their flavours: undirected graphs, directed graphs, multigraphs, and weighted graphs.  Numerous fundamental graph concepts  are presented: adjacency, incidence, vertex degrees, walks, tours, paths, cycles, Euler tours and Hamilton cycles, trees, spanning trees, graph connectivity, bipartite graphs, vertex and edge colourings, matching, planarity, flows, optimal paths, and planar embeddings.  An emphasis is placed on the algorithmic aspects of Graph Theory and on its practical aspects.  Every significant graph problem is demonstrated as an abstraction of a particular real-life problem.  The most fundamental algorithmic problems on graphs are discussed in detail: graph traversal, minimum spanning tree, shortest and longest paths, topological sorting, maximum matching, the edge coloring of bipartite graphs, various transportation problems, the Chinese postman problem, the colorability of planar graphs.  Numerous algorithms are presented and analysed: BFS, DFS, Prim’s and Kruskal’s algorithms for MST, Dijkstra’s algorithm for shortest paths, the construction of Eulerian tours, several max-flow algorithms, algorithms for maximum matchings on bipartite graphs.  To that end, the fundamentals of algorithm analysis are presented briefly with emphasis on polynomial-time complexity. 

Lecturer's Team

Teachers