Back to Teaching Page

Graph Theory and Combinatorics

Courses

Remark: The code for subscribing on Google Classroom is 6mn5e47.
  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
  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 (video)
  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