UINA170 Combinatorial algorithms

Faculty of Philosophy and Science in Opava
Winter 2020
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
Prerequisites (in Czech)
TYP_STUDIA(N)
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
The course follows and extends knowledge obtain in the Graph theory course. It focuses on the practical applications of the theoretical knowledge and on the programming techniques and on the working with graphs.
Syllabus
  • 1. Recall of the basic terms of the graph theory
    2. Representation of the graphs in the computer, suitability of the representations
    3. Basic methods of the searching the graphs, depth-first search, breadth-first search
    4. Accessibility in the graph, vertices and edges connectedness of the graph, components of the graph
    5. The length of the path of the graph
    6. The graph skeletons
    7. Finding the Eulers paths and cycles in the graphs, Eulers graphs, finding the Hammiltones paths and cycles
    8. The flows in the nets
    9. Paring in the bipartite and common graphs
    10. Clique in the graph, finding the independent set of vertices, colouring of graphs
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
Teaching methods
Interactive lecture
Lecture with a video analysis
Assessment methods
Exam
Language of instruction
English
Further comments (probably available only in Czech)
The course can also be completed outside the examination period.
Teacher's information
Build up an application solving chosen graph algorithms
The course is also listed under the following terms Winter 2017, Winter 2018, Winter 2019.
  • Enrolment Statistics (recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2020/UINA170