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.
  1. Lecture 1 Introduction. Counting Principles. Permutations and Combinations. Binomial and Multinomial Numbers
  2. Lecture 2 Generating Permutations. Ranking and Unranking Permutations. The Pigeonhole Principle. The Inclusion and Exclusion Principle
  3. Lecture 3 Permutations with repetition. Combinations. Enumeration, ranking and unranking algorithms
  4. Lecture 4 The Cycle Structure of Permutations. Advanced Counting Techniques
  5. Lecture 5 Polya theory
  6. Lecture 6 Polya’s enumeration formula. Stirling cycle numbers. Stirling set numbers
  7. Revision and solutions
  8. Partial exam
  9. Lecture 9 Introduction to Graph Theory. Distance in Graphs. Trees
  10. Lecture 10 Kinds of graphs. Data structures for graph representation. Connectivity. The naive algorithm and Warshall algorithm. Bipartite graphs
  11. Lecture 11 Connectivity: Dijkstra's algorithm. Flow Networks. Maximum flow algorithms. Applications and extensions
  12. Lecture 12 Eulerian trails and circuits. Hamiltonian paths and cycles
  13. Lecture 13 Matchings. Definitions. Hall's Theorem and SDRs. Perfect matchings. Spanning trees and minimum spanning trees. Prim's algorithm and Kruskal's algorithm
  14. 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.
  1. Seminar 1
  2. Laboratory 2 and some examples in Mathematica
  3. Seminar 3
  4. Laboratory 4 & 5 and some examples in Mathematica
  5. Seminar 6 and some examples in Mathematica pdf and notebook file
  6. Seminar 7 and part 2

Bibliography

  1. S. Pemmaraju, S. Skiena. Combinatorics and Graph Theory with Combinatorica. Cambridge University Press 2003
  2. http://www3.cs.stonybrook.edu/~skiena/combinatorica
  3. J.M. Harris, J.L. Hirst, M.J. Mossinghoff. Combinatorics and Graph Theory. Second Edition. Springer. 2008