FPF:UIDI012 Graphs and Graph Algorithms - Course Information
UIDI012 Graphs and Graph Algorithms
Faculty of Philosophy and Science in OpavaWinter 2013
- Extent and Intensity
- 0/0. 0 credit(s). Type of Completion: dzk.
- Guaranteed by
- doc. RNDr. Luděk Cienciala, Ph.D.
Institute of Computer Science – Faculty of Philosophy and Science in Opava - 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
- Autonomous Systems (programme FPF, P1801 Inf)
- Course objectives
- In this course students learn the basic concepts of the proving techniques and possible applications of graph theory.
- Syllabus (in Czech)
- 1. Grafy a jednoduché grafy, stupeň vrcholu.
2. Podgrafy, reprezentace grafů pomocí matic, cesty, cykly, dosažitelnost, souvislost, souvislé, nesouvislé grafy, vzdálenost v grafu, excentricita vrcholu, průměr a poloměr grafu.
3. Stromy, třídy grafů.
4. Další třídy grafů - kompletní grafy, bipartitní a multi-partitní grafy, izomorfismus, automorfismus. Vrcholová a hranová souvislost, bloky.
5. Párování, pokrytí, hranové barvení grafů, párování a pokrytí v bipartitních grafech, algoritmus hledající nesaturované alternující cesty.
6. Vrcholové barvení grafů, planární grafy.
7. Problém 4 barev, Neplanární grafy, Eulerovské grafy, Úlohy typu bludiště ? Tarryho algoritmus, Trémauxův algoritmus.
8. Hamiltonovské grafy, orientované grafy.
9. Orientované grafy, turnaje, sítě, toky a řezy.
10. Algoritmus nalezení minimální kostry grafu, Primův algoritmus, Kruskalův, Obecné schéma prohledávání grafu ? značkování vrcholů.
11. Prohledávání grafů do šířky, do hloubky, Backtracking.
- 1. Grafy a jednoduché grafy, stupeň vrcholu.
- Literature
- recommended literature
- Fronček, D. Úvod do teorie grafů. Opava, FPF SU, 2000. info
- Bollobas, B. Modern Graph Theory. New York, Springer, 1998. info
- Diestel, R. Graph Theory. New York, Springer, 1997. info
- Demel, J. Grafy. Praha, SNTL, 1988. info
- Kolář, J. Grafy. Praha, ČVUT, 1984. info
- Kolář, J. Grafy - cvičení. Praha, ČVUT, 1984. info
- Bosák, J. Grafy a ich aplikácie. Bratislava, Alfa, 1980. info
- Behzad, M., Chartrand, G. Graphs and Digraphs. Weber, Schmidt, 1979. info
- Bondy, J. A. Graph Theory with Applications. The Macmillan Press, 1976. info
- Language of instruction
- Czech
- Further Comments
- The course can also be completed outside the examination period.
- Teacher's information
- Total of examination exam can earn 60 points. For the successful completion students need to get 30 points.
- Enrolment Statistics (Winter 2013, recent)
- Permalink: https://is.slu.cz/course/fpf/winter2013/UIDI012