1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2019/2020
4. Mathematics - First-cycle studies leading to Bachelor's degree
5. Discrete Mathematics 2

Generate PDF for this page

Discrete Mathematics 2 - course description

Aim of the course

The course introduces advance notions and ideas of discrete mathematics in theoretic and algorithmic aspects.

Prerequisites

Save changes

Discrete Mathematics 1

Scope

LECTURE

1. Some classes of graphs, their properties and applications.
2. Various dominating sets in graphs.
3. Graph colouring, graph list-colouring, Theorems of Brooks, Szekeres-Wilf, Vizing, and Thomasen
4. Matroids and their properties. Rado-Edmond’s Theorem, Rado’s Theorem.
5. Definition and basic notations of digraphs. Acyclic and transitive digraphs.

CLASSES

1. The properties of intersection graphs, chordal graphs and their applications.
2. The properties of the chromatic number, the choice number, the domination numbers and their applications in tasks and practical issues. The basic graph colouring algorithms.
3. Classes of digraphs and their properties. Basic algorithms for digraphs.
4. Definition of the matroid, examples of matroids. The  greedy algorithm for the

Teaching methods

Lecture: problem lecture

Classes: solve of exercises, discussion

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Class. The final grade is issued on the points obtained during the classes and activity during the classes.

Lecture. The final grade is issued on the points of the final test.

Final course grade.The final grade consists of the class grade (50%) and the class grade (50%). The condition of passing the subject is a positive grade from both: the class and the lecture.

Recommended reading

1. J. Bang-Jensen,  G. Gutin, Digraphs, Theory, Algorithms and Applications, Springer, 2001.
2. R. Diestel, Graph Theory, Springer-Verlag, New York, 1997.
3. D. J. A. Welsh, Matroid Theory, Academic Press, Inc., New York, 2010

Further reading

K.A. Ross, Ch.R.B. Wright, Discrete Mathematic, Pearson Education, New Jersey, 2003

Notes

Modified by dr Alina Szelecka (last modification: 19-10-2020 13:47)