FPF:FPFVA044 Graph Theory - Course Information

FPFVA044 Graph Theory

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

• English in combination with another discipline (programme FPF, N7310 Filo) (2)
• Angličtina (jednooborové) (programme FPF, N7310 Filo) (3)
• Archaeology (programme FPF, N7109 Arch) (2)
• Audio-visual works (programme FPF, AVT-np)
• Audio-visual Creation (programme FPF, N8203 DrUm)
• Czech Studies (programme FPF, N7310 Filo) (2)
• Computational Physics (programme FPF, N1701 Fyz)
• Computer Science and Technology (programme FPF, N1801 Inf) (2)
• Historical Science (programme FPF, N7105 HiVe) (2)
• Historie-muzeologie (programme FPF, N7105 HiVe) (2)
• Information and Library Studies (programme FPF, N7201 InSK) (2)
• Information Studies (programme FPF, KNIH-nav)
• Computer Science and Technology (programme FPF, N1801 Inf) (2)
• Library science with the focus on public libraries of the community type (programme FPF, N7201 InSK) (2)
• Cultural Inheritance in Regional Practice (programme FPF, N7106 HiSt) (2)
• Kulturní dějiny (programme FPF, N7105 HiVe) (2)
• Němčina (dvouoborové) (programme FPF, N7310 Filo) (2)
• German (programme FPF, N7310 Filo) (3)
• German (programme FPF, NJ) (2)
• Protection of the Cultural Heritage (programme FPF, N7105 HiVe) (2)
• Computational Physics (programme FPF, N1701 Fyz)
• Theoretical Physics (programme FPF, N1701 Fyz) (2)
• Physics (programme FPF, N1701 Fyz) (2)
• Creative Photography (programme FPF, N8204 ITF)
• Secondary School Teacher Training in English (programme FPF, N7504 UcSS)
• Secondary School Teacher Training in Czech language and literature (programme FPF, N7504 UcSS)
• Secondary School Teacher Training in History (programme FPF, N7504 UcSS)
• Secondary School Teacher Training in German (programme FPF, N7504 UcSS) (2)
• Teacher Training - shared framework (programme FPF, N7504 UcSS)
• Public community type libraries (programme FPF, KNIH-nav)

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