The aim of studying and bibliography

The main aim of study: The aim of the course is to present theoretical and practical methods of graph and network theory

The general information about the module:

Bibliography required to complete the module

Bibliography used during lectures

1	A. Włoch, I. Włoch	Matematyka dyskretna- podstawowe metody i algorytmy teorii grafów	Oficyna Wydawnicza Politechniki Rzeszowskiej, Rzeszów.	2004.
2	K. Ross, Ch. Wright	Matematyka dyskretna	PWN, Warszawa.	1996.
3	V. Bryant	Aspekty kombinatoryki	WNT, Warszawa.	2005.
4	P.N. de Souza, R.J. Fateman, J. Moses, C. Yapp	The Maxima Book	http://maxima.sourceforge.net.
5	R.J. Wilson	Wprowadzenie do teorii grafów	PWN, Warszawa.	2000.

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: Knowledge of linear algebra

Basic requirements in category skills: basic mathematical knowledge

Basic requirements in category social competences:

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 theorems and algorithms of graphs and networks and can use concepts of graph and network.	lecture, classes, laboratory	wriitten test, computer works	K_W01+ K_W03+ K_U02+ K_U03+ K_K01+ K_K02+ K_K05+	P6S_KK P6S_KO P6S_UW P6S_WG
02	The student can build a model of discrete problem	lecture, classes, laboratory	written test, computer work	K_W01+ K_W03+ K_U02+ K_U03+ K_K01+ K_K02+ K_K05+	P6S_KK P6S_KO P6S_UW P6S_WG
03	The student can generate graphs and determine their properties using CAS Maxima	laboratory	computer work	K_W01+ K_W03+ K_U02+ K_U03+ K_K01+ K_K02+ K_K05+	P6S_KK P6S_KO P6S_UW P6S_WG

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	The definition of a graph and the graph geometrical representation. Basic concepts of graph theory. Types of graphs, complement of a graph, weighted graphs, graphs products, isomorphism of graphs. Matrix representations of a graph, adjacency matrix, incidence matrix.	W1-W3, C1-C3, L1-L3	MEK01 MEK02 MEK03
2	TK02	Paths and cycles in graphs. Conected graphs. Eulerian graphs, Hamiltonian graphs. Travelling salesman problem.	W4-W5, C4-C5, L4-L5	MEK01 MEK02 MEK03
2	TK03	Trees- definition and basic properties. Binary trees, Spanning trees. Trees coding methods. Counting of trees. Caley Theorem. Trees as a data stucture sytems.	W6-W7, C6-C7, L6-L7	MEK01 MEK02 MEK03
2	TK04	Topological graph theory. Planar Graphs. Graphs on surfaces. Planar graphs parameters.	W8, C8, L8	MEK01 MEK02 MEK03
2	TK05	Independence in graphs. Independent sets and Fibonacci numbers. Matchings, Hall's Theorem. Domination in graphs. Dominating sets, dominating number. Packing and covering in graphs.	W9-W10, C9-C10, L9-L10	MEK01 MEK02 MEK03
2	TK06	Graph colouring. Vertex colouring, edge colourins. Chromatic number, chromatic index. Chromatic polynomial. Four Colour Theorem.	W11, C11, L11	MEK01 MEK02 MEK03
2	TK07	Digraphs, basic concepts. Euler's digraphs. Tournaments.	W12, C12, L12	MEK01 MEK02 MEK03
2	TK08	Networks, Minimax theorems.	W13-W14, C13-C14, L13-L14	MEK01 MEK02 MEK03
2	TK09	Applications of graph in data analysis	W15, C-15, L15	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. 2)	The preparation for a test: 3.00 hours/sem.	contact hours: 15.00 hours/sem.
Class (sem. 2)	The preparation for a Class: 5.00 hours/sem. The preparation for a test: 2.00 hours/sem.	contact hours: 15.00 hours/sem.
Laboratory (sem. 2)	The preparation for a Laboratory: 3.00 hours/sem. The preparation for a test: 2.00 hours/sem.	contact hours: 15.00 hours/sem.
Advice (sem. 2)
Credit (sem. 2)

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

The type of classes	The way of giving the final grade
Lecture
Class
Laboratory
The final grade	To complete the coures it is necessary to pass wtitten test and computer works. The final degree is the arithetic average of partial degrees..

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: no