UIN1070 Combinatorial Algorithms

Faculty of Philosophy and Science in Opava
Winter 2012
Extent and Intensity
2/2/0. 4 credit(s). Type of Completion: zk (examination).
Guaranteed by
RNDr. Miroslav Langer, 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
Course objectives (in Czech)
Předmět navazuje a rozšiřuje znalosti získané v předmětu Teorie grafů. Ukazuje praktickou aplikaci teoretických poznatků a techniky programování a práce s grafy.
Syllabus (in Czech)
  • 1. Připomenutí základních pojmů z teorie grafů.
    2. Reprezentace grafů v počítači, vhodnost reprezentací.
    3. Základní metody průchodů grafů, prohledávání grafů do hloubky a do šířky.
    4. Dostupnost v grafu, hranová a vrcholová souvislosta komponenty grafu.
    5. Délka cesty v grafu
    6. Kostry grafu
    7. Hledání eulerovských cest a cyklů, eulerovské grafy, hledání hamiltonovské cesty a cyklu.
    8. Toky v sítích
    9. Párování v bipartitních a obecných grafech
    10. Klikovost grafu, hledání nezávislé množiny vrcholů, barvení grafů
Literature
    recommended literature
  • Večerka. Grafy a grafové algoritmy. PřF UP Olmouc, 2007. info
  • Fronček. Úvod do teorie grafů. SLU Opava, 1999. info
  • Kučera. Kombinatorické algoritmy. SNTL Praha, 1991. info
  • Demel. Grafy. Praha, 1989. info
Language of instruction
Czech
Further Comments
The course can also be completed outside the examination period.
The course is also listed under the following terms Winter 2010, Winter 2011, Winter 2013, Winter 2014, Winter 2015, Winter 2016, Winter 2017, Winter 2018, Winter 2019, Winter 2020, Winter 2021, Winter 2022, Winter 2023.
  • Enrolment Statistics (Winter 2012, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2012/UIN1070