# VSFS:B_DMa Discrete mathematics - Course Information

## B_DMa Discrete mathematics

**University of Finance and Administration**

Winter 2024

**Extent and Intensity**- 2/2/0. 6 credit(s). Type of Completion: zk (examination).
**Teacher(s)**- RNDr. Eva Ulrychová, Ph.D. (seminar tutor)
**Guaranteed by**- RNDr. Eva Ulrychová, Ph.D.

Department of Computer Science and Mathematics – Departments – University of Finance and Administration

Contact Person: Ivana Plačková **Prerequisites**- There are no prerequisites for this course
**Course Enrolment Limitations**- The course is offered to students of any study field.
**Course objectives**- At the end of this course students will be able to: - Apply the proofs of mathematical relations, especially proofs using contradiction and/or mathematical induction. - Understand binary relations: ordering and equivalence. Functions onto and one-to-one. - Combinatorial counting. -Know basic algebraic structures. - Remember the definition of unoriented graph, basic terminology of graphs. - Search for the shortest paths using Dijkstra‘s algorithm, matching in graph and its change. - Apply the score of graph and its conversions, solve the Euler trail and the task of a Chinese Mailman. - Explain properties of the special class of graphs, i.e. trees. Utilize different algorithms of the lightest spanning tree of an evaluated graph. - Apply Kruscal, Jarník/Prim and Borůvka algorithms finding the lightest spanning trees and discuss their effectivity. - Draw plannar graphs, construct and describe dual graphs. Try to color maps, verticie and edges, the four-color problem. - Oriented graph and its symetrisation, acyclic graph, condensation of graph, De Bruijn sequences. - Search in a network for the maximum flow and the minimum cut.
**Learning outcomes**- At the end of this course students are able to: Understand the proofs of logical formulae. Apply the proofs of mathematical relations, especially proof of a statements using contradiction and/or mathematical induction. Understand binary relations: ordering and equivalence. Functions onto and one-to-one. Use Combinatorial counting, Remember the definitions of different types of unoriented graphs and/or their parts, i.e. basic terminology of graphs. - Search for the shortest paths in the graph using Dijkstra‘s and Floyd‘s algorithms, matching in graph and its change. Apply the score of graph and its conversions, solve the Euler trail and the task of a “Chinese Mailman”. Explain properties of the special class of graphs, i.e. trees. Utilize different algorithms of the lightest spanning tree of an evaluated graph, apply Kruscal, Jarník/Prim and Borůvka algorithms of the finding the lightest spanning trees of graphs and discuss their effectivity. - Draw plannar graphs, construct the dual graphs. Try to color maps, verticie and edges, the four-color problem. - Oriented graph and its symetrisation, acyclic graph, condensation of graph, De Bruijn sequences, search in a network for the maximum flow and for the minimum cut.
**Syllabus**- 1. Mathematical proofs, sets.
- 2. Binary relations and functions.
- 3. Combinatorial counting and discrete probability.
- 4. Algebraic structures.
- 5. The definition and basic types of undirected graph.
- 6. The lightest path in graph (Dijstra algorithm) and matching in graph.
- 7. Euler graphs and connectivity of graphs.
- 8. Special class of graphs - trees.
- 9. The algorithms for finding the lightest spanning tree of a graph, plannar graphs.
- 10. Coloring of a map, the four color theorem.
- 11. The oriented graphs.
- 12. Flows in a network.

**Literature**- HAVLÍČEK, Ivan. Diskrétní matematika. Praha: VŠFS - Eupress, 2007.
- MILKOVÁ, Eva. Teorie grafů a grafové algoritmy. Hradec Králové: Gaudeamus, 2013. ISBN 978-80-7435-267-6.

*required literature*- MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. Páté, upravené a doplněné vydání. Praha: Univerzita Karlova, nakladatelství Karolinum, 2022. ISBN 978-80-246-5084-5.
- DEMEL, Jiří. Grafy a jejich aplikace, 3. (elektronické) vydání, 2019.
- KOSMÁK, Ladislav a Radovan POTŮČEK. Úvod do algebry. Ostrava: Key Publishing, 2012. Učebnice (Key Publishing). ISBN 978-80-7418-162-7.

*recommended literature***Teaching methods**- Lectures and seminars in full-time study; tutorials in part-time study; compulsory seminar participation is 75% in full-time study, compulsory tutorial participation is 50% in part-time study
**Assessment methods**- Credit (75% participation in the exercise), written exam (50% correct answers) and oral examen.
**Language of instruction**- Czech
**Further comments (probably available only in Czech)**- The course can also be completed outside the examination period.

Information on the extent and intensity of the course: 14 hodin KS/semestr.

- Enrolment Statistics (Winter 2024, recent)
- Permalink: https://is.vsfs.cz/course/vsfs/winter2024/B_DMa