FPF:UIMOIBK008 Graph theory - Course Information
UIMOIBK008 Graph theory
Faculty of Philosophy and Science in OpavaWinter 2024
- Extent and Intensity
- 0/0/0. 6 credit(s). Type of Completion: zk (examination).
- Teacher(s)
- doc. RNDr. Luděk Cienciala, Ph.D. (lecturer)
- 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
- Information and communication technologies (programme FPF, MOI)
- Course objectives
- In this course students learn the basic concepts of the proving techniques and possible applications of graph theory.
- Learning outcomes
- Students will be able to: - define important concepts of graph theory. - use graph algorithms. - apply the acquired knowledge on concrete examples.
- Syllabus
- 1. Graphs and simple graphs, degree of vertex.
- 2. Subgraphs, matrix representation of graphs, paths, cycles, reachability, connectedness, connected, disconnected graphs, distance v graph, vertex eccentricity, diameter and radius of a graph.
- 3. Trees, classes of graphs.
- 4. Other classes of graphs - complete graphs, bipartite and multipartite graphs, isomorphism, automorphism. Vertex and edge continuity, blocks.
- 5. Pairing, covering, edge coloring of graphs, pairing and covering in bipartite graphs, algorithm finding unsaturated alternate paths.
- 6. Vertex coloring of graphs, planar graphs.
- 7.-8. 4-color problem, Non-planar graphs, Eulerian graphs, Maze type problems - Tarry's algorithm, Trémaux algorithm.
- 9. Hamiltonian graphs, oriented graphs.
- 10. Oriented graphs, tournaments, networks, flows and cuts.
- 11.-12. Minimum skeleton graph finding algorithm, Prim's algorithm, Kruskal's algorithm, General graph search scheme, vertex labeling.
- 13. Graph search in width, in depth, Backtracking.
- Teaching methods
- Interactive lecture
Tutorials - Assessment methods
- Credit: Compulsory attendance at seminars min. 75%.
A written form of verification of study results.
For the exam, the student can obtain a maximum of 60 points. A minimum of 30 points is required for successful completion. - Language of instruction
- Czech
- Further comments (probably available only in Czech)
- Information on the extent and intensity of the course: 12 hod/sem.
- Enrolment Statistics (recent)
- Permalink: https://is.slu.cz/course/fpf/winter2024/UIMOIBK008