FPF:UIINP14 Graph theory - Course Information
UIINP14 Graph theory
Faculty of Philosophy and Science in OpavaWinter 2024
- Extent and Intensity
- 2/2/0. 6 credit(s). Type of Completion: zk (examination).
- Teacher(s)
- doc. RNDr. Luděk Cienciala, Ph.D. (lecturer)
RNDr. Radka Poláková, Ph.D. (seminar tutor) - Guaranteed by
- doc. RNDr. Luděk Cienciala, Ph.D.
Institute of Computer Science – Faculty of Philosophy and Science in Opava - Timetable
- Mon 9:45–11:20 B1
- Timetable of Seminar Groups:
- 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
- Informatics B/P (programme FPF, INFOR-bpk)
- Mathematical Methods and Modelling (programme MU, Bc-M)
- Mathematical Methods in Economics (programme MU, Bc-M)
- Mathematical Methods in Risk Management (programme MU, Bc-M)
- General Mathematics (programme MU, Bc-M)
- 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
- The course can also be completed outside the examination period.
- Enrolment Statistics (Winter 2024, recent)
- Permalink: https://is.slu.cz/course/fpf/winter2024/UIINP14