Course: Graphs and Graph Algorithms

« Back
Course title Graphs and Graph Algorithms
Course code UI/DI012
Organizational form of instruction no contact
Level of course Doctoral
Year of study not specified
Semester Winter and summer
Number of ECTS credits 0
Language of instruction Czech
Status of course Compulsory
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Course availability The course is available to visiting students
Lecturer(s)
  • CIENCIALA Luděk, doc. RNDr. Ph.D.
Course content
1. Graphs and simple graphs, vertex degree. 2. Subgraphs, graph representation by matrices, paths, cycles, connected and unconnected graphs. 3. Trees. 4. Special families of graphs - complete graphs, bipartite and multi-partite graphs, isomorphism and automorphism. 5. Matching and covering, edge coloring, matching and covering in bipartite graphs, the algorithm of seeking unsaturated alternating paths. 6. Vertex coloring, planar graphs. 7. The four-colour problem, non/planar graphs, Euler graphs, maze-like tasks - Tarry's algorithm algorithm of Trémaux. 8. Hamilton graphs. 9. Directed graphs, tournaments , networks, flows and cuts. 10.Algorithm to find the minimum spanning tree, Prim's algorithm , Kruskal's algorithm , General scheme of graph search. 11.Bread-First search, Depth-First search, Backtracking.

Learning activities and teaching methods
Interactive lecture, Lecture with a video analysis
Recommended literature
  • Behzad, M., Chartrand, G. Graphs and Digraphs. Weber, Schmidt, 1979.
  • Bollobas, B. Modern Graph Theory. New York, Springer, 1998.
  • Bondy, A., Murty, U. S. R. Graph Theory. Springer, 2011.
  • Bondy, J. A. Graph Theory with Applications. The Macmillan Press, 1976.
  • Bosák, J. Grafy a ich aplikácie. Bratislava, Alfa, 1980.
  • Cienciala, L., Ciencialová, L. Teorie grafů a grafové algoritmy. Slezská univerzita v Opavě, 2014. ISBN 978-80-7510-060-3.
  • Demel, J. Grafy. Praha, SNTL, 1988.
  • Diestel, R. Graph Theory. New York, Springer, 1997.
  • Even, S., Even, G. Graph algorithms, 2nd edition. New York Cambridge University Press, 2012. ISBN 978-0-521-51718-8.
  • Fronček, D. Úvod do teorie grafů. Opava, FPF SU, 2000.
  • Kolář, J. Grafy - cvičení. Praha, ČVUT, 1984.
  • Kolář, J. Grafy. Praha, ČVUT, 1984.
  • Merris, R. Graph Theory. New York : John Wiley, 2001. ISBN 0-471-38925-0.


Study plans that include the course
Faculty Study plan (Version) Branch of study Category Recommended year of study Recommended semester
Faculty of Philosophy and Science in Opava Autonomous Systems (1) Informatics courses - -
Faculty of Philosophy and Science in Opava Autonomous Systems (1) Informatics courses - -
Faculty of Philosophy and Science in Opava Autonomous Systems (1) Informatics courses - -
Faculty of Philosophy and Science in Opava Autonomous Systems (1) Informatics courses - -