FPF:UIMOIBP008 Graph theory - Course Information
UIMOIBP008 Graph theory
Faculty of Philosophy and Science in OpavaWinter 2023
- Extent and Intensity
- 2/2/0. 6 credit(s). Type of Completion: zk (examination).
- Teacher(s)
- doc. RNDr. Luděk Cienciala, Ph.D. (lecturer)
doc. RNDr. Luděk Cienciala, Ph.D. (seminar tutor)
RNDr. Radka Poláková, Ph.D. (seminar tutor) - Guaranteed by
- doc. RNDr. Luděk Cienciala, Ph.D.
Institute of Computer Science – Faculty of Philosophy and Science in Opava - Timetable
- Mon 9:45–11:20 B1
- Timetable of Seminar Groups:
- Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- Information and communication technologies (programme FPF, MOI)
- Course objectives
- In this course students learn the basic concepts of the proving techniques and possible applications of graph theory.
- Learning outcomes
- Students will be able to: - define important concepts of graph theory. - use graph algorithms. - apply the acquired knowledge on concrete examples.
- Syllabus
- 1. Graphs and simple graphs, degree of vertex.
- 2. Subgraphs, matrix representation of graphs, paths, cycles, reachability, connectedness, connected, disconnected graphs, distance v graph, vertex eccentricity, diameter and radius of a graph.
- 3. Trees, classes of graphs.
- 4. Other classes of graphs - complete graphs, bipartite and multipartite graphs, isomorphism, automorphism. Vertex and edge continuity, blocks.
- 5. Pairing, covering, edge coloring of graphs, pairing and covering in bipartite graphs, algorithm finding unsaturated alternate paths.
- 6. Vertex coloring of graphs, planar graphs.
- 7.-8. 4-color problem, Non-planar graphs, Eulerian graphs, Maze type problems - Tarry's algorithm, Trémaux algorithm.
- 9. Hamiltonian graphs, oriented graphs.
- 10. Oriented graphs, tournaments, networks, flows and cuts.
- 11.-12. Minimum skeleton graph finding algorithm, Prim's algorithm, Kruskal's algorithm, General graph search scheme, vertex labeling.
- 13. Graph search in width, in depth, Backtracking.
- Literature
- required literature
- Cienciala, L., Ciencialová, L. Teorie grafů a grafové algoritmy. Slezská univerzita v Opavě, 2014. ISBN 978-80-7510-060-3. info
- recommended literature
- Bondy, A., Murty, U. S. R. Graph Theory. Springer, 2011. info
- Even, S., Even, G. Graph algorithms, 2nd edition. New York Cambridge University Press, 2012. ISBN 978-0-521-51718-8. info
- Merris, R. Graph Theory. New York : John Wiley, 2001. ISBN 0-471-38925-0. info
- HLINĚNÝ, Petr. Základy Teorie grafů [online]. Masarykova univerzita. 2010. Dostupné na: https://is.muni.cz/do/1499/el/estud/fi/js10/grafy/Grafy-text10.pdf [cit. 8. 10. 2017]
- KOVÁŘ, Petr. Úvod do teorie grafů [online]. VŠB TU v Ostravě, 2016. Dostupné na: http://homel.vsb.cz/~kov16/files/uvod_do_teorie_grafu.pdf. [cit. 8. 10. 2017]
- GERA, Ralucca, Craig LARSON and Stephen HEDETNIEMI. Graph theory: Favorite Conjectures and OpenProblems. New York: Springer, 2016. ISBN 978-3-319-31938-4. info
- KOCAY, William L and Donald L KREHER. Graphs, Algorithms and Optimization. 2nd Edition. Boca Raton,USA: CRC Press, 2016. ISBN 978-1-4822-5116-6. info
- MILKOVÁ, Eva. Teorie grafů a grafové algoritmy. Hradec Králové: Gaudeamus, 2013. ISBN 978-80-7435-267-6. info
- not specified
- ŠEDA, Miloš. Teorie grafů [online]. Brno: VUT, 2003. Dostupné na: http://www.uai.fme.vutbr.cz/~mseda/TG03_MS.pdf. [cit. 8. 10. 2017]
- Teaching methods
- Interactive lecture
Tutorials - Assessment methods
- Credit: Compulsory attendance at seminars min. 75%.
A written form of verification of study results.
For the exam, the student can obtain a maximum of 60 points. A minimum of 30 points is required for successful completion. - Language of instruction
- Czech
- Further Comments
- Study Materials
- Enrolment Statistics (Winter 2023, recent)
- Permalink: https://is.slu.cz/course/fpf/winter2023/UIMOIBP008