
Computing
Discrete Mathematics 1
- Class 60
- Practice 6
- Independent work 114
Course title
Discrete Mathematics 1
Lecture type
Obligatory
Course code
183396
Semester
3
ECTS
6
Lecturers and associates
Course objectives
Fibonacci's sequence; Homogeneous recursive relations.
Homogeneous recursive relations.
Non-homogeneous recursive relations.
Notion of a graph. Main definitions and examples. Graph isomorphism.
Connectivity. Paths. Eulerian and hamiltonian graphs; Optimization algorithms. Shortest path problem. Chinese postman problem. Travelling salesman problem.
Different characterizations of trees.
Labelled trees. Prüfer code; Minimum spanning tree. Algorithms.
Midterm exam.
Kuratowski's theorem; Euler's formula.
Dual graphs; Planarity testing algorithms.
Vertex colourings. Brooks' theorem; Edge colourings.
Face colourings of planar graphs. Four colour theorem.
Notion of a digraph. Connectivity and strong connectivity; Critical path problem. Algorithms; Tournaments.
Marriage problem; Hall's theorem; Transversals; Application to latin squares.
Final exam.
Required reading
(.), D. Kovačević, D. Žubrinić, Uvod u diskretnu matematiku, Element, Zagreb, 2014.,
(.), A. Nakić, M.-O. Pavčević, Uvod u teoriju grafova, Element, Zagreb, 2014.,
(.), J.M. Aldous, R.J. Wilson, Graphs and Applications - An Introductory Approach, Springer, 2004.,
(.), G. Chartrand, L. Lesniak, Graphs and Digraphs, CRC Press, 2005.,
Online education during epidemiological measures
- Study program duration
- 6 semesters (3 years)
- Semester duration
- 15 weeks of active teaching + 5 examination weeks
- Total number of ECTS points
- 180
- Title
- Bacc.ing.comp (Bachelor of Science in Computing)
Academic calendar
Minimal learning outcomes
- To solve homogeneous and non-homogeneous linear recursion.
- Apply the recursive way of thinking on the appropriate combinatorial problems.
- Describe and manipulate with basic notions from graph theory.
- Describe and solve appropriate engineering problems in terms of graph theory.
- Solve problems algorithmically using computers.