 Study

# Computing

## Discrete Mathematics 1

• Class 60
• Practice 6
• Independent work 114
Total 180

### Course title

Discrete Mathematics 1

Obligatory

183396

3

6

### 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.

(.), 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.,

#### 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.