PředmětyPředměty(verze: 861)
Předmět, akademický rok 2019/2020
  
Topologické a geometrické grafy - NDMI095
Anglický název: Topological and geometric graphs
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2019
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: nevyučován
Jazyk výuky: angličtina, čeština
Způsob výuky: prezenční
Další informace: https://kam.mff.cuni.cz/~kyncl/tgg/
Garant: Mgr. Jan Kynčl, Ph.D.
doc. RNDr. Pavel Valtr, Dr.
Třída: DS, diskrétní modely a algoritmy
Informatika Mgr. - Diskrétní modely a algoritmy
Kombinatorická geometrie a geom. algorit
Kategorizace předmětu: Informatika > Diskrétní matematika
Anotace -
Poslední úprava: T_KAM (21.04.2016)
Nakreslení typického grafu do roviny se neobejde bez křížení hran. Nakreslením grafů v rovině, v nichž jsou povolena křížení hran, a to i vícenásobná, se říká topologické grafy. Speciálním případem jsou geometrické grafy, jejichž hrany jsou nakresleny jako úsečky. Typickým problémem při studiu nakreslení grafů je hledání nakreslení s minimálním počtem křížení. Zkoumají se i různé extremální otázky, jako např. maximální počet hran v geometrickém grafu bez k disjunktních hran. Předpokládají se základní znalosti z teorie grafů a kombinatorické geometrie (NDMI009).
Podmínky zakončení předmětu -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (29.05.2019)

Ústní zkouška.

Literatura -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (19.02.2019)

převážně odborné články, částečně skripta; podrobnosti viz https://kam.mff.cuni.cz/~kyncl/tgg/

Požadavky ke zkoušce -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (19.02.2019)

Zkouška bude ústní na základě přednesené látky.

Sylabus -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (06.02.2019)

Hananiova--Tutteova věta a algebraický algoritmus na testování rovinnosti

Jordanova věta o kružnici

Thrackles

Topologické a geometrické grafy bez zakázaných konfigurací

Úplné topologické grafy

Případně další témata

 
Univerzita Karlova | Informační systém UK