FPF:UIINK14 Graph theory - Course Information
UIINK14 Graph theory
Faculty of Philosophy and Science in OpavaWinter 2024
- Extent and Intensity
- 12/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 offered to students of any study field.
- 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)
- The course can also be completed outside the examination period.
Information on the extent and intensity of the course: Přednáška 12 HOD/SEM.
- Enrolment Statistics (recent)
- Permalink: https://is.slu.cz/course/fpf/winter2024/UIINK14