Goal: Developing the student’s conceptualization, abstraction, and problem-solving abilities by learning about the basic topics of discrete mathematics, as well as their applications in problem solving and model creation. The basic concepts of graph algorithms and complexity theory are learned from the theory of algorithms.
Course description: Principle of mathematical induction, pigeonhole principle, principle of inclusion and exclusion. Permutations, variations and combinations, binomial theorem. Generating functions and their basic properties. Linear recurrence relations, Stirling, Catalan, Bell and Fibonacci sequences. The basic properties of graphs, subgraphs, complements and graph isomorphism. Trees, forests, Prüfer code, Euler trails and circuits, Hamilton paths and cycles, Ore’s theorem, Posa’s theorem, extreme graph theory, Turán’s theorem. Graph colouring, Brooks’ theorem, Vizing’s theorem, perfect graphs, planar graphs, dual graphs, Kuratowski’s theorem. Matching theory, Hall’s theorem, König’s theorem, Gallai’s theorem, Hungarian method, flows, maxflow min-cut theorem.
https://nik.uni-obuda.hu/targyleirasok/wp-content/uploads/2026/06/HG_Dismath_2627_1.pdf