PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   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 2017
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 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.
Literatura -
Poslední úprava: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)

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

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