COURSE AIMS AND OBJECTIVES:
To understand fundamental concepts, theorems, and algorithms in graph theory and to solve related problems.
COURSE DESCRIPTION AND SYLLABUS:
- Vertex and edge connectivity, 2-connectivity, Mader's theorem, Menger's theorem, Ford-Fulkerson algorithm
- Matchings, Hall's theorem, Kőnig's theorem, Tutte's condition, minimum matching algorithm in bipartite graphs
- Graph coloring, greedy coloring, Brooks' theorem, Five-Color theorem, Gallai-Roy theorem, Vizing's theorem
- Matrix-tree theorem, Cauchy-Binet formula
- Algebraic methods, eigenvalues of graphs, strongly regular graphs, PageRank algorithm
- Probabilistic method and Ramsey theory
- Extremal graph theory: Turán's theorem, Kővári-Sós-Turán theorem
|
Pristupačnost
