Lecturer(s)


Čada Roman, Doc. Ing. Ph.D.

Tomiczková Světlana, RNDr. Ph.D.

Course content

1. basic concepts of set theory, binary relations 2. mappings (functions), basic algebraic structures 3. tolerance relation and equivalence, congruence relation 4. ordering relation, partial and total ordering, Hasse diagram 5. supremum and infimum, lattice, distributive lattice 6. complemented lattice, Boolean algebra, Boolean calculus, Stone's representation theorem for Boolean algebras 7. direct product of Boolean algebras, Boolean functions, Boolean polynomials, disjunctive and conjunctive normal form 8. graph, oriented and nonoriented graph, graph homomorphisms and related concepts, paths in graphs, degree of a vertex, Eulerian graph, trees 9. oriented graphs, weak and strong connectivity, acyclic graphs, condensation graph 10. incidence matrix of an oriented graph, Laplacian matrix, counting spanning trees, incidence matrix of a nonoriented graph 11. cycle and cut space of a graph 12. adjacency matrix, counting walks 13. labeled graphs, distance in a graph, Dijkstra's algorithm

Learning activities and teaching methods

Interactive lecture, Lecture, Practicum
 Contact hours
 52 hours per semester
 Preparation for formative assessments (220)
 30 hours per semester
 Preparation for an examination (3060)
 56 hours per semester

prerequisite 

professional knowledge 

An active knowledge of linear algebra in a range of the course KMA/LAA or KMA/LAA and of combinatorics at high school level is assumed. 
learning outcomes 

A student will be able to:  solve basic problems of combinatorics,  use actively the concept of a relation and a function,  apply basic facts of group theory,  solve linear congruence equations,  identify partial ordering relation,  define lattices and Boolean algebras,  deal with Boolean functions,  use actively basic concepts of graph theory,  describe a graph with help of matrices and use them to determine properties of the graph,  apply linear algebra in graph theory,  solve critical path problem. 
teaching methods 

Lecture 
Interactive lecture 
Practicum 
assessment methods 

Combined exam 
Test 
Skills demonstration during practicum 
Recommended literature


Gross, Jonathan; Yellen, Jay. Graph theory and its applications. Boca Raton : CRC Press, 1999. ISBN 0849339820.

Matoušek, Jiří; Nešetřil Jaroslav. Invitation to discrete mathematics. Oxford University Press, USA, 1998. ISBN 9780198502081.

Scheinerman, Edward R. Mathematics: A discrete introduction. Brooks Cole, 2005. ISBN 9780534398989.

Van Lint, J. H.; Wilson, R. M. A course in combinatorics. Cambridge : Harvard University Press, 2001. ISBN 0521006015.
