Graph Theory

Code	Completion	Credits	Range	Language
11Y1TG	KZ	2	2P+0C	Czech

Garant předmětu:

Lucie Kárná

Lecturer:

Lucie Kárná

Tutor:

Lucie Kárná

Supervisor:

Department of Applied Mathematics

Synopsis:

Basic concepts and terminology of graph theory, graph representation. Problems of graph theory, problem instance. Graph search algorithms, trees, minimum spanning tree, shortest path problem, Eulerian path, bipartite graph matching, flow networks, circulations, critical path method, traveling salesman problem. Problem of existence and optimization and algorithms for their solving. Computational complexity, dealing with NP-complete problems, heuristic approach.

Requirements:

Graph theory basics

Syllabus of lectures:

Syllabus of tutorials:

Study Objective:

Deeper understanding of graph theory basics. Learning of bacis concepts and problems in the field of algoritmization. Classical problems of graph theory and algorithms for their solving. Introducing to time complexity and efficiency of algorithms.

Study materials:

Demel, J: Grafy a jejich aplikace, Praha, Academia, 2002

Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky, Praha, Karolinum, 2009

Note:

Time-table for winter semester 2023/2024:

Time-table is not available yet

Time-table for summer semester 2023/2024:

Time-table is not available yet

The course is a part of the following study plans:

2.bl.bak.prez.DS 09/10začátek (compulsory elective course)
2.bl.bak.prez.ME 09/10začátek (compulsory elective course)
2.bl.bak.prez.AI 09/10začátek (compulsory elective course)
2.bl.bak.prez.LD 09/10 (compulsory elective course)
2.bl.bak.prez.DS 05/06 začátek (compulsory elective course)
2.bl.bak.prez.ME 05/06 začátek (compulsory elective course)
2.bl.bak.prez.AI 05/06 začátek (compulsory elective course)
2.bl.bak.prez.LD 05/06začátek (compulsory elective course)
2.bl.bak.prez.DS 06/07 začátek (compulsory elective course)
2.bl.bak.prez.ME 06/07 začátek (compulsory elective course)
2.bl.bak.prez.AI 06/07 začátek (compulsory elective course)
2.bl.bak.prez.LD 06/07 začátek (compulsory elective course)
2.bl.bak.prez.DS 07/08začátek (compulsory elective course)
2.bl.bak.prez.AI 07/08začátek (compulsory elective course)
2.bl.bak.prez.ME 07/08začátek (compulsory elective course)
2.bl.bak.prez.LD 07/08začátek (compulsory elective course)
2.bl.bak.prez.DS 08/09začátek (compulsory elective course)
2.bl.bak.prez.AI 08/09začátek (compulsory elective course)
2.bl.bak.prez.LD 08/09začátek (compulsory elective course)
2.bl.bak.prez.ME 08/09začátek (compulsory elective course)
2.bl.bak.prez.DS 10/11začátek (compulsory elective course)
2.bl.bak.prez.ME 10/11začátek (compulsory elective course)
2.bl.bak.prez.AI 10/11začátek (compulsory elective course)
2.bl.bak.prez.LD 10/11 (compulsory elective course)
2.bl.bak.pres.DS (compulsory elective course)
2.bl.bak.prez.AI (compulsory elective course)
2.bl.bak.prez.LD (compulsory elective course)
2.bl.bak.prez.ME (compulsory elective course)
AUT bak.prez.11/12 (compulsory elective course)
DOS bak.prez.11/12 (compulsory elective course)
ITS bak.prez.11/12 (compulsory elective course)
LED bak.prez.11/12 (compulsory elective course)
MED bak.prez.11/12 (compulsory elective course)
AUT bak. prez.12/13 (compulsory elective course)
DOS bak.prez.12/13 (compulsory elective course)
MED bak.prez.12/13 (compulsory elective course)
ITS bak.prez.12/13 (compulsory elective course)
LED bak.prez.12/13 (compulsory elective course)
AUT bak.prez.13/14 (compulsory elective course)
DOS bak.prez.13/14 (compulsory elective course)
ITS bak.prez.13/14 (compulsory elective course)
LED bak.prez.13/14 (compulsory elective course)
MED bak.prez.13/14 (compulsory elective course)
DOS bak.prez.13/14 (SKOK) (compulsory elective course)
LED bak.prez.13/14 (SKOK) (compulsory elective course)
MED bak.prez.13/14 (SKOK) (compulsory elective course)
DOS bak.prez.14/15 (compulsory elective course)
MED bak.prez.14/15 (compulsory elective course)
AUT bak.prez.14/15 (compulsory elective course)
ITS bak.prez.14/15 (compulsory elective course)
LED bak.prez.14/15 (compulsory elective course)
DOS bak.prez.15/16 (compulsory elective course)
MED bak.prez.15/16 (compulsory elective course)
AUT bak.prez.15/16 (compulsory elective course)
ITS bak.prez.15/16 (compulsory elective course)
LED bak.prez.15/16 (compulsory elective course)
BEZ bak.prez.15/16 (compulsory elective course)
DOS bak.prez.16/17 (compulsory elective course)
LOG bak.prez.16/17 (compulsory elective course)
ITS bak.prez.16/17 (compulsory elective course)
LED bak.prez.16/17 (compulsory elective course)
BEZ bak.prez.16/17 (compulsory elective course)
DOS bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (compulsory elective course)
DOS bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (compulsory elective course)
LOG bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (compulsory elective course)
LOG bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (compulsory elective course)
ITS bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (compulsory elective course)
ITS bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (compulsory elective course)
LED bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (compulsory elective course)
LED bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (compulsory elective course)
BEZ bak.prez.17/18 - v 1.sem. si NEZAPSALI 14DB (compulsory elective course)
BEZ bak.prez.17/18 - v 1.sem. si ZAPSALI 14DB (compulsory elective course)
LOG bak.prez.17/18 - včetně 11FYZ v 3.s. (compulsory elective course)
LED bak.prez.17/18 - včetně 11FYZ v 3.s. (compulsory elective course)
DOS bak.prez.18/19 (compulsory elective course)
LOG bak.prez.18/19 (compulsory elective course)
ITS bak.prez.18/19 (compulsory elective course)
LED bak.prez.18/19 (compulsory elective course)
DOS bak.prez.18/19 (skok do 3.r.) (compulsory elective course)
CŽV pro LED bak.prez. v 18/19 (compulsory elective course)
LOG bak.prez.18/19 (skok do 3.r.) (compulsory elective course)
ITS bak.prez.18/19 (skok do 3.r.) (compulsory elective course)
LED bak.prez.18/19 - skok z 2.r.do 3.r. (compulsory elective course)
LED bak.prez.19/20 angličtina (compulsory elective course)
DOS bak.prez.19/20 (compulsory elective course)
LOG bak.prez.19/20 (compulsory elective course)
ITS bak.prez.19/20 (compulsory elective course)
LED bak.prez.19/20 (compulsory elective course)
ITS bak.prez.19/20 (skok do 3.r.) (compulsory elective course)
DOS bak.prez.19/20 (skok do 3.r.) (compulsory elective course)
LED bak.prez.19/20 (skok do 3.r.) (compulsory elective course)
LED bak.prez.20/21 angličtina (compulsory elective course)
DOS bak.prez.20/21 (compulsory elective course)
LOG bak.prez.20/21 (compulsory elective course)
LOG bak.prez.20/21 (skok do 3.r.) (compulsory elective course)
ITS bak.prez.20/21 (compulsory elective course)
ITS bak.prez.20/21 (skok do 3.r.) (compulsory elective course)
LED bak.prez.20/21 (compulsory elective course)
LED bak.prez.20/21 (skok do 3.r.) (compulsory elective course)
LED bak.prez.21/22 (skok do 3.r.) (compulsory elective course)
DOS bak.prez.21/22 (skok do 3.r.) (compulsory elective course)
LOG (obor) bak.prez.21/22 (skok do 3.r.) (compulsory elective course)
ITS bak.prez.21/22 (skok do 3.r.) (compulsory elective course)
DOS bak.prez.21/22 (compulsory elective course)
ITS bak.prez.21/22 (compulsory elective course)
LED bak.prez.21/22 (compulsory elective course)