PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Toky a cykly v grafech - NDMI058
Anglický název: Flows and Cycles in Graphs
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018 do 2018
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Další informace: http://kam.mff.cuni.cz/~samal/vyuka/Toky/
Garant: 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 -
Poslední úprava: T_KAM (03.05.2002)
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.
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ů.

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.

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í.

 
Univerzita Karlova | Informační systém UK