Course: Graph Theory

« Back
Course title Graph Theory
Course code UI/N1004
Organizational form of instruction Lecture + Lesson
Level of course Bachelor
Year of study 2
Semester Winter
Number of ECTS credits 6
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.
  • KOŽANÝ Adam, Mgr.
  • MENŠÍK Marek, Mgr. Ph.D.
  • PERDEK Michal, RNDr.
  • FOLDYNOVÁ Martina, Mgr.
  • DRASTIK Jan, Mgr.
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
Mathematical Institute in Opava Mathematical Analysis (1-IVT) Mathematics courses 1 Winter
Faculty of Philosophy and Science in Opava Applied Computer Science (1) Informatics courses 2 Winter
Mathematical Institute in Opava Mathematical Methods in Economics (2) Economy 2 Winter
Faculty of Philosophy and Science in Opava Computer Science and Technology (1) Electrical engineering, telecommunication and IT 2 Winter
Mathematical Institute in Opava Applied Mathematics (2014-IVT) Mathematics courses 1 Winter
Mathematical Institute in Opava Mathematical Methods in Economics (3) Economy 2 Winter
Mathematical Institute in Opava Mathematics (2014-IVT) Mathematics courses 1 Winter
Mathematical Institute in Opava Mathematics (1-IVT) Mathematics courses 1 Winter
Mathematical Institute in Opava Applied Mathematics in Risk Management (3) Mathematics courses 2 Winter