Skip to main content
Skip header

Discrete Mathematics

Type of study Bachelor
Language of instruction Czech
Code 470-2301/01
Abbreviation DIM
Course title Discrete Mathematics
Credits 6
Coordinating department Department of Applied Mathematics
Course coordinator doc. Mgr. Petr Kovář, Ph.D.

Subject syllabus

Lectures:

Part I - Introduction to discrete mathematics.

The scope and goals of Discrete mathematics. Sets, elements, k-combinations, k-permutations, related formulas.

Discrete probability: tossing coins, random choice, shuffling cards. Probability space and random event.

Integers and mathematical induction, the concept of proofs. Proving the formulas for numbers of subsets, k-combinations, k-permutations.

Formal foundations of dicscrete math: relations, mappings, equivalence relations, partial orders.

Algorithmic aspects: practical implementation of sets and relations.
Generating all possible subsets k-combinations, and k-permutations.


Part II - Introduction to graph theory

Graphs and relations. Subgraphs, isomorphism, degrees, implementation. Directed graphs.

Graph connectivity, algorithms for searching. Higher degrees of connectivity, edge-connectivity. Eulerian graphs and their applications.

Distance in graphs, Dijkstra's algorithm, graph metric and its enumeration.

Trees and their characterizations, rooted trees, tree isomorphism.
Spanning trees, MST problem. Basic algorithms for MST.

Planar embeddings of graphs, Euler's formula and its applications.
Graph coloring, bipartite graphs, recognition.

Network flows: formulation and application to real life problems. Ford-Fulkerson's algorithm for maximum flow. Further applications to matching and system of representatives.

Exercises:
Following the course content.

Project:
Each student will prepare one project which contains a part concerning Discrete mathematics and a part concernig Graph Theory.

E-learning

Core materials are available on the instructor's website: http://homel.vsb.cz/~kov16/predmety_dm.php

Literature

P. Kovář: Lecture slides online http://homel.vsb.cz/~kov16/files/dim_kapitoly_all_en.pdf
J.Matoušek, J.Nešetřil. Invitation to Discrete Mathematics, Oxford University Press, ISBN 0-19-850208-7.

Advised literature

K.H.Rosen, Discrete Mathematics and Its Applications - 6th ed., McGraw-Hill, New York NY, (2007), ISBN-10 0-07-288008-2.
P. Kovář: Lecture slides online http://homel.vsb.cz/~kov16/files/dim_kapitoly_all_en.pdf
P. Kovář, T. Kovářová: Solved exercises http://homel.vsb.cz/~kov16/files/dim_solved_exercises.pdf