The aim of studying and bibliography

The main aim of study: The aim of the course is to introduce students with the basic methods of discrete mathematics.

The general information about the module: The module contains methods of solving recurrence equations and basic concepts and algorithms of graph theory.

Bibliography required to complete the module

Bibliography used during lectures

1	A. Włoch, I. Włoch	Matematyka dyskretna	Oficyna Wydawnicza Politechniki Rzeszowskiej, Rzeszów .	2004
2	K. Ross, Ch. Wright	Matematyka dyskretna	PWN Warszawa.	1996

Bibliography used during classes/laboratories/others

1

R. J. Wilson

Wprowadzenie do teorii grafów

PWN Warszawa.

2000

Bibliography to self-study

1

R. Diestel

Graph Theory

Springer-Verlag, Heidelberg, New York.

2005

Basic requirements in category knowledge/skills/social competences

Formal requirements: The student satisfies the formal requirements set out in the study regulations

Basic requirements in category knowledge: Mastering the basics of calculus and calculus matrix.

Basic requirements in category skills: Ability to use the basic mathematical apparatus of mathematical analysis and algebra.

Basic requirements in category social competences: A student can work in group.

Module outcomes

MEK	The student who completed the module	Types of classes / teaching methods leading to achieving a given outcome of teaching	Methods of verifying every mentioned outcome of teaching	Relationships with KEK	Relationships with PRK
01	Student knows basic combinatorial objects, their number and generating methods.	lecture, classes	test	K_W06+ K_U29+ K_K01+	P6S_KK P6S_UK P6S_UW P6S_WG
02	Student knows the basic concepts, theorems and algorithms of the graph theory.	lecture, classes	test	K_W04+++ K_U29+ K_K01+	P6S_KK P6S_UK P6S_UW P6S_WG P6S_WK
03	Student can consider combinatorial objects in three aspects: the existence, number and systematic generating.	classes	test	K_W01+ K_U29+ K_K01+	P6S_KK P6S_UK P6S_UW P6S_WK
04	Student can build a model of the problem and solve it.	classes	test	K_W02+ K_W03+ K_W05+ K_U29+++ K_K01+	P6S_KK P6S_UK P6S_UW P6S_WG P6S_WK

Attention: Depending on the epidemic situation, verification of the achieved learning outcomes specified in the study program, in particular credits and examinations at the end of specific classes, can be implemented remotely (real-time meetings).

The syllabus of the module

Sem.	TK	The content	realized in	MEK
2	TK01	Mathematical induction. Recursive equations.	W01, C01	MEK03 MEK04
2	TK02	Combinatorial objects, the representation of combinatorial objects, the generation of combinatorial objects and counting.	W02, W03, C02	MEK01 MEK03 MEK04
2	TK03	Generating functions.	W04, C02	MEK04
2	TK04	The concept graph, geometric interpretation. Graph types, power and complement graph, weighted graphs, products of two graphs. Isomorphism of graphs. The matrix representation of the graph: adjacency matrix, incidence matrix.	W05, W06, C03	MEK01 MEK03 MEK04
2	TK05	Paths and cycles in graphs.	W07, W08, C04	MEK02 MEK03 MEK04
2	TK06	Trees. Definitions and basic properties. Binary Tree. Tree encoding method, Cayley theorem.	W09, C04	MEK01 MEK02 MEK03 MEK04
2	TK07	Spanning tree, the methods of determining the minimum spanning tree.	W10, C05	MEK01 MEK02 MEK03 MEK04
2	TK08	Topological graph theory. Planar graphs. Graphs on surfaces.	W11, C05	MEK02 MEK04
2	TK09	Independence. Independent sets. Matchings.	W12, W13, C06	MEK01 MEK02 MEK03 MEK04
2	TK10	Coloring of graphs. Vertex coloring. Edge coloring.	W14, W15, C07	MEK01 MEK02 MEK03 MEK04
2	TK11	Test	C08	MEK01 MEK02 MEK03 MEK04

The student's effort

The type of classes	The work before classes	The participation in classes	The work after classes
Lecture (sem. 2)		contact hours: 30.00 hours/sem.
Class (sem. 2)	The preparation for a Class: 10.00 hours/sem. The preparation for a test: 5.00 hours/sem.	contact hours: 15.00 hours/sem.	Finishing/Studying tasks: 15.00 hours/sem.
Advice (sem. 2)
Credit (sem. 2)		The written credit: 2.00 hours/sem.

The way of giving the component module grades and the final grade

The type of classes	The way of giving the final grade
Lecture	A credit for the lecture is based on attendance at the lectures.
Class	Student has to get at least 50% points on the test during classes.
The final grade	The final grade is the grade of classes.

Sample problems

Required during the exam/when receiving the credit
(-)

Realized during classes/laboratories/projects
(-)

Others
(-)

Can a student use any teaching aids during the exam/when receiving the credit : no

The contents of the module are associated with the research profile: yes

1	P. Bednarz; M. Pirga	On Proper 2-Dominating Sets in Graphs	2024
2	P. Bednarz	Relations between the existence of a (2 − d)-kernel and parameters γ2(G), α(G)	2022
3	P. Bednarz	On (2-d)-Kernels in the Tensor Product of Graphs	2021
4	P. Bednarz; A. Michalski	On Independent Secondary Dominating Sets in Generalized Graph Products	2021
5	P. Bednarz; N. Paja	On (2-d)-Kernels in Two Generalizations of the Petersen Graph	2021