The aim of studying and bibliography

The main aim of study: Familiarising students with chosen issues concering the theory of digraphs and networks

The general information about the module: Subject of classes was chosen by students.

Bibliography required to complete the module

Bibliography used during lectures

1	R.J. Wilson	Wprowadzenie do teorii grafów	PWN, Warszawa.	2000
2	R. Diestel	Graph Theory	Springer GTM 173, 5th edition.	2016
3	A. Włoch, I. Włoch	Matematyka dyskretna. Podstawowe metody i algorytmy teorii grafów	Oficyna Wydawnicza Politechniki Rzeszowskiej, Rzeszów .	2017

Bibliography used during classes/laboratories/others

1	R.J. Wilson	Wprowadzenie do teorii grafów	PWN, Warszawa.	2000
2	R. Diestel	Graph Theory	Springer GTM 173, 5th edition.	2016
3	A. Włoch, I. Włoch	Matematyka dyskretna. Podstawowe metody i algorytmy teorii grafów	Oficyna Wydawnicza Politechniki Rzeszowskiej, Rzeszów .	2017

Bibliography to self-study

1

J. Bang-Jensen, G.Z. Gutin

Digraphs: theory, algorithms and applications

Springer Science & Business Media.

2008

Basic requirements in category knowledge/skills/social competences

Formal requirements: Requirements accordant with Rules and Regulations of studies

Basic requirements in category knowledge: Student has knowledge in the fields of discrete mathematics.

Basic requirements in category skills: Student knows, understands and can apply concepts of discrete mathematics.

Basic requirements in category social competences: Student has the ability to independent and collaborative lerning, is aware of the level of his knowledge and understands the need of self-learning.

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	The student knows basic definitions and theorems of digraph theory	lecture, classes	test	K_W01+ K_W02++ K_W03+ K_W04+ K_W05+ K_W06+ K_U01+ K_K01+	P6S_KK P6S_UK P6S_WG P6S_WK
02	The student knows selected algorithms in digraphs related to optimization problems	lecture, classes	test	K_W02+ K_W03+ K_W04+ K_W05+ K_W06+ K_U01+ K_K01+	P6S_KK P6S_UK P6S_WG P6S_WK
03	The student can use methods of digraph theory for solving discrete problems	lecture, classes	test	K_W01+ K_W04+ K_W05+ K_K01+	P6S_KK 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
5	TK01	Basic concepts of graph theory. Introduction to digraph theory. Connectivity and strong connectivity of digraphs, directed trees, tournaments, Euler and Hamilton cycles in digraphs.	W01-W10, C01-C05	MEK01 MEK02 MEK03
5	TK02	weighted digraphs. Algorithms for finding distances in digraphs. Breadth-first search, Dijkstra's algorithm, the Bellman-Ford-Moore algorithm. Diameter, radius and kings in digraphs. The travelling salesman problem and the Chinese postman problem.	W11-W20, C06-C10	MEK01 MEK02 MEK03
5	TK03	Networks and flows. The residual network. The maximum flow problem. The Ford-Fulkerson algorithm. Minimum cost flows. The Busacker-Gowen algorithm. Application of flows. The Chinese postman problem and maximum matchings in bipartite graphs.	W21-W30, C11-C13	MEK01 MEK02 MEK03

The student's effort

The type of classes	The work before classes	The participation in classes	The work after classes
Lecture (sem. 5)		contact hours: 30.00 hours/sem.	complementing/reading through notes: 6.00 hours/sem.
Class (sem. 5)	The preparation for a Class: 15.00 hours/sem.	contact hours: 15.00 hours/sem.
Advice (sem. 5)	The preparation for Advice: 6.00 hours/sem.	The participation in Advice: 3.00 hours/sem.
Credit (sem. 5)

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