Study programmes / C-SE System engineering and informatics / Graph Theory
Course code:TGR
Course title in language of instruction:Teorie grafů
Course title in Czech:Teorie grafů
Course title in English:Graph Theory
Mode of completion and number of credits:Exam (5 credits)
(1 ECTS credit = 28 hours of workload)
Mode of delivery/Timetabled classes:full-time, 2/1
(full-time, hours of lectures per week / hours of seminars per week)
Language of instruction:Czech
Level of course:master continuing
Semester:SS 2018/2019 - FBE
Name of lecturer:prof. RNDr. Ing. Jiří Šťastný, CSc. (supervisor)
Prerequisites:Final Bachelor Exam
 
Aims of the course:The goal of the subject is to provide sufficient theoretical background for problem solving with the help of the graph theory and graph algorithms. The subject focus not only on theoretical parts of graph theory, it also emphasizes comprehension of curriculum and ability to apply gained knowledge practically.
Course contents:
1.Motivation, history and basic terminology (allowance 6/2)
 
a.Chosen parts of graph theory. Origin of graph theory.
b.Graph definition, graph properties. Complete graph, bipartite graph, planar graph
c.Repetition from TBI

2.Graph implementation (allowance 2/2)
 
a.Static implementation - adjacency matrix, incidence matrix
b.Dynamic implementation - list of neighbours, dynamin representation of a graph

3.Trees and spanning trees (allowance 4/2)
 
a.Characterisation, properties and usage of trees
b.Root trees, ordered root trees. Applications of trees
c.Spanning tree. Spanning tree applications, finding of minimal spanning tree.

4.Searching in graph and its applications (allowance 2/2)
 
a.Breadth-first-search. Distant decomposition of vertices
b.Depth-first-search. Pre-order, in-order, post-order.

5.Finding optimal walks (allowance 4/2)
 
a.Moore's algorithm, Dijkstra's algorithm, Ford algorithm
b.Critical path method, widest paths.
c.Practical applications of optimal walks

6.Network flows and appcations (allowance 2/2)
 
a.Network definition, flow definition. Max-flow min-cut theorem.
b.Ford-Fulkerson algorithm. Applications of networks and flows in technological practice.

7.Problems solved with the help of graph theory (allowance 4/0)
 
a.Program control graph, transition diagram and their usage
b.Planar graph, coloring of graph, pairing in bipartite graph

Learning outcomes and competences:
Generic competences:
 
-ability to analyse and synthesize
-ability to apply knowledge
-ability to communicate with professionals in different field of study
-ability to solve problems
-ability to work independently
-basic computing skills
-capacity to learn
-general knowledge
-professional knowledge
-skilled at utilizing and processing information

Specific competences:
 
-Ability to implement and critically evaluate graph algorithms
-ability to solve the real issues with the use of graph theory
-ability to use the graph algorithms to develop to program modules
-Knowledge of algorithms for solving graph problems
-Knowledge of graph theory terminology

Type of course unit:required
Year of study:Not applicable - the subject could be chosen at anytime during the course of the programme.
Work placement:There is no compulsory work placement in the course unit.
Recommended study modules:none
Assessment methods:Points from homeworks: 5 x 10b. = 50b.
Points from final test: 50 b.
Assessment: A85, B77, C70, D62, E55
 
Learning activities and study load (hours of study load)
Type of teaching methodDaily attendance
Direct teaching
     lecture28 h
     practice14 h
Self-study
     preparation for exam42 h
     elaboration and execution of projects56 h
Total140 h

Basic reading list
  • FOLTÝNEK, T. -- DANNHOFEROVÁ, J. Teorie grafů. Brno: Mendelova univerzita v Brně, 2011. 91 p. ISBN 978-80-7375-500-3.
  • ŽAMBOCHOVÁ, M. Teorie grafů v příkladech. 1st ed. Ústí nad Labem: Fakulta sociálně ekonomická UJEP, 2007. 97 p. ISBN 978-80-7044-962-2.
  • GROSS, J L. -- YELLEN, J. Handbook of graph theory. Boca Raton: CRC Press, 2004. 1167 p. Discrete mathematics and its applications. ISBN 1-58488-090-2.
Recommended reading list
  • DEMEL, J. Grafy a jejich aplikace. 1st ed. 257 p. ISBN 80-200-0990-6.
  • FUCHS, E. Kombinatorika a teorie grafů. Praha: SPN, 1986.
  • GROSS, J L. -- YELLEN, J. Graph theory and its applications. 2nd ed. Boca Raton: Chapman & Hall/CRC, 2006. 779 p. Discrete mathematics and its applications. ISBN 1-58488-505-X.
  • PLESNÍK, J. Grafové algoritmy. Bratislava: VEDA, 1993.