Přednáška poskytne základy současné teorie nikde nenulových toků a cyklických rozkladů a pokrytí grafů a matroidů.
Vhodné pro doktorandy a studenty od 3. ročníku.
Poslední úprava: T_KAM (03.05.2002)
Introduction to nowhere zero flows and cycle covers of graphs and matroids.
Podmínky zakončení předmětu -
Poslední úprava: doc. Mgr. Robert Šámal, Ph.D. (01.03.2019)
Zkouška bude ústní na základě přednesené látky.
Pro zisk zápočtu je třeba získat alespoň 50% bodů ze zadaných domácích úkolů.
Poslední úprava: 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.
Literatura -
Poslední úprava: 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.
Poslední úprava: 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.
Sylabus -
Poslední úprava: T_KAM (06.05.2004)
Celočíselné toky v grafech. Grupové a modulárni toky, základní vlastnosti. Tutteovy hypotézy o existenci nenulového toku, známé dílčí výsledky. Charakterizace grafu s k disjunktními kostrami. Hypotéza o dvojpokrytí cykly, souvislosti s toky. Kompatibilní rozklady eulerovských grafů. Tenze, dualita mezi toky a tenzemi. Tokově a cyklově spojitá zobrazení, hypotéza o petersenovském barvení.
Poslední úprava: 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.