SubjectsSubjects(version: 873)
Course, academic year 2020/2021
Flows and Cycles in Graphs - NDMI058
Title: Toky a cykly v grafech
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2019
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: not taught
Language: Czech, English
Teaching methods: full-time
Additional information:
Guarantor: doc. Mgr. Robert Šámal, Ph.D.
Class: DS, diskrétní modely a algoritmy
Informatika Mgr. - volitelný
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: T_KAM (03.05.2002)
Introduction to nowhere zero flows and cycle covers of graphs and matroids.
Course completion requirements -
Last update: doc. Mgr. Robert Šámal, Ph.D. (01.03.2019)

The exam will be oral based on the presented material.

For the credit from practicals you need to get at least 50% score from the homework assignments.

Literature -
Last update: doc. Mgr. Robert Šámal, Ph.D. (11.02.2019)

C.Q.Zhang: Integer flows and cycle covers of graphs. Monographs and Textbooks in Pure and Applied Mathematics, 205. Marcel Dekker, Inc., New York, 1997.

C.Q.Zhang: Circuit double cover of graphs. London Mathematical Society Lecture Note Series, 399. Cambridge University Press, Cambridge, 2012.

Syllabus -
Last update: T_KAM (06.05.2004)

Integer flows in graphs. Group and modular flows, basic properties. Tutte's conjectures on nowhere-zero flows, known partial results. The classical characterization of graphs with k disjoint spanning trees. The cycle double cover conjecture, relations to flows. Compatible decompositions of Eulerian graphs. Tensions, the tension-flow duality. Flow-continuous and cycle-continuous maps, the Petersen coloring conjecture.

Charles University | Information system of Charles University |