Toky a cykly v grafech - NDMI058

• Anglický název: Flows and Cycles in Graphs
• Podoba výuky: přednáška
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2009 do 2009
• Počet semestrů výuky: 1
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Maximální kapacita předmětu: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Forma uskutečňování: prezenční
• Další informace: http://kam.mff.cuni.cz/~samal/vyuka/Toky/
• Možnost opakovaného zápisu: 2 / 2 / 2 / 2
• Garant: prof. RNDr. Tomáš Kaiser, DSc.; prof. RNDr. Jaroslav Nešetřil, DrSc.; doc. Mgr. Robert Šámal, Ph.D.
• Vyučující: prof. RNDr. Tomáš Kaiser, DSc.; prof. RNDr. Jaroslav Nešetřil, DrSc.; doc. Mgr. Robert Šámal, Ph.D.
• Třída: DS, diskrétní modely a algoritmy; Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

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)

angličtina

Introduction to nowhere zero flows and cycle covers of graphs and matroids.

Poslední úprava: T_KAM (03.05.2002)

Literatura

čeština

C.Q.Zhang: Integer flows and cycle covers of graphs.

Poslední úprava: Šámal Robert, doc. Mgr., Ph.D. (11.02.2019)

Sylabus

čeština

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)

angličtina

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.

Poslední úprava: T_KAM (06.05.2004)