FI:M010 Combinatorics and Graph Theory - Course Information

M010 Combinatorics and Graph Theory

Extent and Intensity

2/0. 2 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Contact Person: doc. RNDr. Jiří Kaďourek, CSc.

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

• Informatics (programme FI, B-IN)
• Informatics (programme FI, M-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
• Information Technology (programme FI, B-IN)

Syllabus

• Elementary combinatorial coefficients.
• The inclusion-exclusion principle.
• The Moebius inversion formula.
• Generating functions.
• Solving linear recurrence formulas.
• Graphs, trees.
• The shortest-path problem.
• The minimum-weight spanning tree problem.
• Eulerian and Hamiltonian graphs.
• Bipartite graphs and matchings.
• Network flow problems.
• Connectivity in graphs.
• Planar graphs.

Language of instruction

Czech

• Enrolment Statistics (Autumn 1997, recent)
  
• Permalink: https://is.muni.cz/course/fi/autumn1997/M010