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