|
Study

Computing

Back to Lecture Plan

Discrete Mathematics 1

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

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

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.
SHARE : Facebook Twitter