1. SylabUZ
2. Faculty of Exact and Natural Sciences
3. winter term 2022/2023
4. WMIiE - oferta ERASMUS - Erasmus programme
5. Discrete Mathematics 1

Generate PDF for this page

Discrete Mathematics 1 - course description

Aim of the course

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

Prerequisites

Save changes

Introduction to mathematics, Linear algebra 1.

Scope

Lecture
1. Basic notions of the graph theory: neighbourhood, adjacency, isomorphism, paths, cycles, connectivity, subgraphs (2 h).
2. Graph matrixes (2 h).
3. Some classes of graphs (2 h).
4. Union, join and complement graph operations (2 h).
5. Trees and their properties (4 h).
6. BFS and DFS algorithms (2 h).
7. Vector spaces of the graph (2 h).
8. n-connectivity (2 h).
9. Eulerian graphs. Hamiltonian Graphs (3 h).
10. Planar graphs, Kuratowski’s Theorem, Harary’s Theorem (3 h).
11. Covers and independence (2 h).
12. Vertex colouring of graphs, list colouring of graphs, Brooks’s Theorem, the Szekeres-Wilf Theorem, Vizing’s Theorem, Thomassen’s Theorem (4 h).

Class
1. Reading information on a graph from its matrixes, adjacency lists, sets of pairs. Interpretation of operations on graph matrixes. Matrixes of graph operations (4 h).
2. Investigation of basic tree’s features. Counting labeled trees, using known algorithms to find a spanning tree of a graph, its sets of fundamental cycles and elementary cut. Generating of cycle and cut spaces of a graph. Construction of a modular decomposition tree of a graph (8 h).
3. Analysis of graph connectivity (2 h).
4. Investigation of Eulerian and Hamiltonian graphs and dependence of these properties on other features of graphs. Using known algorithms to recognize an Euler tour and a Hamilton cycle in a graph (4 h).
5. Recognition of problems associated with graph planarity, independence and covers numbers of a graph in practical exercises. Application of theoretical knowledge in practical problems on this topic (4 h).
6. Recognition of coloring problems in practice. Theoretical and algorithmic approach (6 h).
7. Test completion (2 h).

 

Teaching methods

Conversation lecture, traditional lecture, discussion exercises.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Methods: D - participation in the discussions during the course P1 - essay P2 - written exam PU2 - oral exam S - self-esteem
Assessment of individual classes:
1. Checking of preparedness of students and their activity during exercise (D, S).
2. Colloquium with the tasks of different difficulty, allowing to evaluate whether the students have achieved specified learning outcomes in terms of skills and competencies (P1).
3. Conversation during the lecture in order to verify the effects of higher levels of education in terms of knowledge and skills (D, S).
4. Written exam to verify the learning outcomes in terms of knowledge and skills (P2).
5. Oral exam, which allows to complete student’s written [removed]PU2).
The grade of the module consists of the assessment exercise (50%), exam grade (P2 + PU2) (50%). The condition of the exam is to get a positive assessment of the exercise. The prerequisite to obtain a positive evaluation of the module is the positive evaluation of the exercise and the exam.

Recommended reading

1. J.M. Aldous, R. Wilson, Graphs and applications, Springer, 2000.

2.  D. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River, 2001.

3. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa, 1998.
 

Further reading

1. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa, 1989.

Notes

Modified by dr hab. Ewa Drgas-Burchardt, prof. UZ (last modification: 26-04-2022 14:54)