FPFVA044 Graph Theory

Filozoficko-přírodovědecká fakulta v Opavě
zima 2020
Rozsah
0/1/0. 5 kr. Ukončení: z.
Vyučující
doc. RNDr. Luděk Cienciala, Ph.D. (cvičící)
Garance
doc. RNDr. Luděk Cienciala, Ph.D.
Filozoficko-přírodovědecká fakulta v Opavě
Předpoklady
TYP_STUDIA ( N )
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
předmět má 51 mateřských oborů, zobrazit
Cíle předmětu
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.
Výstupy z učení
Students will be able to: - define important concepts of graph theory. - use graph algorithms. - apply the acquired knowledge on concrete examples.
Osnova
  • 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
Výukové metody
Interactive lecture
Tutorials
Metody hodnocení
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.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.slu.cz/predmet/fpf/zima2020/FPFVA044