FPF:UIN1070 Combinatorial algorithms - Course Information

UIN1070 Combinatorial algorithms

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

• Computer Science and Technology (programme FPF, N1801 Inf)

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

Language of instruction

Czech

Further Comments

The course can also be completed outside the examination period.

Teacher's information

Build up an application solving chosen graph algorithms

• Enrolment Statistics (Winter 2013, recent)
  
• Permalink: https://is.slu.cz/course/fpf/winter2013/UIN1070