logo PRZ
Item card
logo WYDZ

Graph and network theory


Some basic information about the module

Cycle of education:
2019/2020
The name of the faculty organization unit:
The faculty Mathematics and Applied Physics
The name of the field of study:
Engineering and data analysis
The area of study:
sciences
The profile of studing:
The level of study:
first degree study
Type of study:
full time
discipline specialities :
The degree after graduating from university:
engineer
The name of the module department :
Departament of Discrete Mathematics
The code of the module:
12320
The module status:
mandatory for teaching programme
The position in the studies teaching programme:
sem: 2 / W15 C15 L15 / 3 ECTS / Z
The language of the lecture:
Polish
The name of the coordinator:
Iwona Włoch, DSc, PhD
office hours of the coordinator:
poniedziałek 10.15-11.45
semester 2:
Adrian Michalski, PhD
semester 2:
Paweł Bednarz, PhD

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
MEK01 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
MEK02 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
MEK03 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

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

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