MA2BP_PDM1 Discrete Mathematics 1

Faculty of Education
Autumn 2017
Extent and Intensity
2/0/0. 3 credit(s). Type of Completion: k (colloquium).
Teacher(s)
RNDr. Břetislav Fajmon, Ph.D. (lecturer)
Guaranteed by
doc. RNDr. Jaroslav Beránek, CSc.
Department of Mathematics – Faculty of Education
Supplier department: Department of Mathematics – Faculty of Education
Timetable
Mon 15:45–17:25 učebna 10
Prerequisites
Basic notions of discrete mathematics as introduced in the subjects Algebra 1 and Algebra 2
Course Enrolment Limitations
The course is only offered to the students of the study fields the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
At the end of the course students should be able to understand and explain the basics of graph theory and use some graph algorithms in problem solving.
Syllabus
  • 0. Some graph algorithms (minimum spanning tree, shortest route, transport problem, Critical Path Method). 1. Basic notions of graph theory, isomorphism. 2. Connected (components) and 2-connected (blocks) graphs. 3. Bipartite and Hamiltonian graphs. 4. Eulerian graphs, walk through a labyrinth, Eulerian walk through a graph. 5. Planar graphs, Euler theorem, graph colouring. 6. Trees, root trees, searching through a graph.
Literature
  • FUCHS, Eduard. Diskrétní matematika pro učitele. 1st ed. Brno: Masarykova univerzita, 2001, 178 pp. ISBN 80-210-2703-7. info
  • VRBA, Antonín. Grafy : pro III. ročník tříd gymnázií se zaměřením na matematiku, na matematiku a fyziku a pro seminář a cvičení z matematiky ve IV. ročníku gymnázií. 1. vyd. Praha: Státní pedagogické nakladatelství, 1989, 75 s. info
  • DEMEL, Jiří. Teorie grafů. Vyd. 1. Praha: Ediční středisko ČVUT, 1982, 198 s. info
  • NEŠETŘIL, Jaroslav. Teorie grafů. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1979, 316 s. URL info
Teaching methods
Lectures presenting definitons, algorithms and mathematical theories. Cooperation with the subject MA2BP_CDM1, the SS individually or in the discussion with the teacher solve the tasks and work with the notions given.
Assessment methods
Oral exam at the end of the term, in which the students prove their understanding of the subject matter. The student will be admitted to the colloqium after a successful completion of the test in the subject MA2BP_CDM1.
Language of instruction
Czech
Further comments (probably available only in Czech)
Study Materials
The course is taught annually.
The course is also listed under the following terms Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2018.
  • Enrolment Statistics (Autumn 2017, recent)
  • Permalink: https://is.muni.cz/course/ped/autumn2017/MA2BP_PDM1