Back to Teaching Page
Graph Theory and Combinatorics
Courses
Remark: You have to upload the homework given in lectures on Google Classroom. Each homework has a deadline and there are NO deadlines extensions.
Subscribe (if you haven't done this already) by using the code gnte7tu. See there the link for participating to the online meetings.
- Lecture 1 Introduction. Counting Principles. Permutations and Combinations. Binomial and Multinomial Numbers
- Lecture 2 Generating Permutations. Ranking and Unranking Permutations. The Pigeonhole Principle. The Inclusion and Exclusion Principle
- Lecture 3 Permutations with repetition. Combinations. Enumeration, ranking and unranking algorithms
- Lecture 4 The Cycle Structure of Permutations. Advanced Counting Techniques
- Lecture 5 Polya theory
- Lecture 6 Polya’s enumeration formula. Stirling cycle numbers. Stirling set numbers
- Revision and solutions
- Partial exam
- Lecture 9 Introduction to Graph Theory. Distance in Graphs. Trees
- Lecture 10 Kinds of graphs. Data structures for graph representation. Connectivity. The naive algorithm and Warshall algorithm. Bipartite graphs
- Lecture 11 Connectivity: Dijkstra's algorithm. Flow Networks. Maximum flow algorithms. Applications and extensions
- Lecture 12 Eulerian trails and circuits. Hamiltonian paths and cycles
- Lecture 13 Matchings. Definitions. Hall's Theorem and SDRs. Perfect matchings. Spanning trees and minimum spanning trees. Prim's algorithm and Kruskal's algorithm
- Lecture 14 Planar graphs. Graph colorings. Chromatic polynomials. Revision
Laboratories & Seminars
Remark: Homework given in one lab/seminar are checked and discussed during the next lab/seminar. You do not have to upload them.
- Seminar 1
- Laboratory 2 and some examples in Mathematica
- Seminar 3
- Laboratory 4 & 5 and some examples in Mathematica
- Seminar 6 and some examples in Mathematica pdf and notebook file
- Seminar 7 and part 2
Bibliography
- S. Pemmaraju, S. Skiena. Combinatorics and Graph Theory with Combinatorica. Cambridge University Press 2003
- http://www3.cs.stonybrook.edu/~skiena/combinatorica
- J.M. Harris, J.L. Hirst, M.J. Mossinghoff. Combinatorics and Graph Theory. Second Edition. Springer. 2008