UIINFNP011 Combinatorial Algorithms

Faculty of Philosophy and Science in Opava
Winter 2025
Extent and Intensity
2/0/0. 4 credit(s). Type of Completion: zk (examination).
Teacher(s)
RNDr. Radka Poláková, Ph.D. (lecturer)
Guaranteed by
RNDr. Radka Poláková, Ph.D.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Timetable
Mon 18:05–19:40 PED1
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
Course objectives
A student obtains knowledge about combinatorial algorithms (algorithms from graph theory). So, student returns to terms from graph theory and meets several graph algorithms in this subject.
Learning outcomes
The student will have an understanding of basic graph algorithms and he will be able to apply them when solving different discrete problems.
Syllabus
1. Graph. 2. Representation of graph. 3. Going through graph. 4. Connectivity, components of graph. 5. Length of path in graph. 6. Tree subgraph. 7. Eulerian graphs, Hamiltonian cycle. 8. Matching in graph. 9. Clique, independent set. 10. Colouring of graph. 11. Cycle in graph. 12. Network flows.
Literature
    required literature
  • 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. 2019]
  • 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. 2019]
    recommended literature
  • BONDY, J and MURTY. Graph theory. New York: Springer, 2010. ISBN 978-1-84996-690-0. info
  • GERA, Ralucca; Craig LARSON and Stephen HEDETNIEMI. Graph theory: Favorite Conjectures and OpenProblems. New York: Springer, 2016. ISBN 978-3-319-31938-4. info
  • Even, S., Even, G. Graph algorithms, 2nd edition. New York Cambridge University Press, 2012. ISBN 978-0-521-51718-8. 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
  • ŠEDA, Miloš. Teorie grafů [online]. Brno: VUT, 2003. Dostupné na: http://www.uai.fme.vutbr.cz/~mseda/TG03_MS.pdf. [cit. 8. 10. 2019]
Teaching methods
Lectures, discussions, exercises, case studies.
Assessment methods
Attendance – a full time study: To attend the lectures is recomended. Attendance – a part time study: Lectures are obligatory. Exam test is written. A student have to reach fifty percent assesment minimally.
Language of instruction
Czech
The course is also listed under the following terms Winter 2021, Winter 2022, Winter 2023, Winter 2024.
  • Enrolment Statistics (recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2025/UIINFNP011