FPFVA044 Graph Theory

Faculty of Philosophy and Science in Opava
Winter 2020
Extent and Intensity
0/1/0. 5 credit(s). Type of Completion: z (credit).
Teacher(s)
doc. RNDr. Luděk Cienciala, Ph.D. (seminar tutor)
Guaranteed by
doc. RNDr. Luděk Cienciala, Ph.D.
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
there are 51 fields of study the course is directly associated with, display
Course objectives
A graph is a collection of points with edges drawn between them. Graph theory was first introduced by Leonhard Euler in his solution to the Königsberg bridge problem in 1736. Since then, graph theory has become an active area of study in mathematics due both to its wide array of real-life applications in biology, chemistry, social sciences and computer networking, and to its interactions with other branches of mathematics. The course will start with an overview of the fundamental concepts and general results in graph theory, followed by explorations of a variety of topics in graph theory and their applications, including connectivity, planar graphs, directed graphs, greedy algorithms, matchings, vertex and edge colourings. The course will end with the introduction of a more advanced topic.
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. Introduction to Graph Theory, Definitions and examples
  • 2. Paths and cycles
  • 3. Trees
  • 4. Planarity
  • 5. Colouring vertices
  • 6. Colouring maps
  • 7. Digraphs
  • 8. Matching
  • 9. Tree-Search Algorithms
  • 10. Flows in Networks
  • 11. Matroids
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
  • Enrolment Statistics (recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2020/FPFVA044