|
This course introduces Graph Theory to develop in students capability of modeling real world problems using graphs and solve them by using graph algorithms. In addition the course develops intuitive ideas in students to solve problems.
By the end of the course, students will be able to:
learn graph-theoretic concepts and important theorems and results. learn how to formulate and model problems using graphs. solve problems using graph algorithms. learn examples of application of graph theory to computer problems.
In addition, students will be required to solve exercises in groups in order to inspire interaction and brainstorming for reaching a destination.
The course covers the following topics:
Fundamental Concepts: what is a graph, paths, cycles, trails, Bipartite graphs, Eulerian circuits, degrees and counting, Extremal problems, graphics sequences Directed graphs: Eulerian digraphs, tournaments
Trees and Distances: properties of trees, distances and disjoint trees, spanning trees and enumerations, spanning trees in graphs
Optimization and Trees: minimum spanning trees, shortest paths, trees in computer science, other spanning trees
Matchings and Covers: maximum matching, Hall’s matching condition, min-
max theorems, independent sets and covers, dominating sets.
Algorithms and Applications: Maximum bipartite matching, weighted bipartite matching, stable matching, faster bipartite matching(optional)
Matching in General Graphs: Tutte’s 1-factor theorem, f-factors of a graph(optional), Edmond’s blossom algorithm
Connectivity and Paths: cuts and connectivity, k-connected graphs, applications of Menger’s theorem
Network Flow problems: Maximum network flow, integral flows, supplies and demands(optional)
Colouring of Graphs, Planar Graphs: embeddings and Euler formula, characterization of planar graphs, parameters of planarity
Edges and Cycles: Line graphs, Hamiltonian cycles, planarity, colouring and cycles
Matroids: Hereditary systems, properties of matroids span function, dual of a matroid, matriod intersection, matroid union
Ramsey Theory: Pigeonhole principle, Ramsey’s theorem, Ramsey number, Graph Ramsey Theory
Eigenvalues of graphs: characteristic polynomial, linear algebra of real matrix, eigenvalues and graph parameters, eigenvalues of regular parameters
Recapitulation of the material and Open problems.
| 