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 2025
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: 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: angličtina, čeština
• Způsob výuky: prezenční
• Další informace: https://kam.mff.cuni.cz/~kvgweb/tgg
• Garant: doc. Mgr. Jan Kynčl, Ph.D.; doc. RNDr. Pavel Valtr, Dr.
• Vyučující: doc. Mgr. Jan Kynčl, Ph.D.
• 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

čeština

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

Poslední úprava: T_KAM (21.04.2016)

angličtina

A drawing of a typical graph in the plane usually contains many crossings. A topological graph is a drawing of a graph in the plane where crossings of edges are allowed, including multiple crossings of the same pair of edges. A geometric graph is a special case where the edges are drawn as straight-line segments. Finding a drawing of a graph minimizing the number of crossings is a typical problem in this area. Various extremal problems are also studied, for example the maximum number of edges of a geometric graph with no k disjoint edges. Basic knowledge of graph theory and discrete geometry (

Poslední úprava: T_KAM (21.04.2016)

Podmínky zakončení předmětu

čeština

Ústní zkouška.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (29.05.2019)

angličtina

Oral exam.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (29.05.2019)

Literatura

čeština

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

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

angličtina

mostly research papers, a part covered by lecture notes; see https://kam.mff.cuni.cz/~kyncl/tgg/ for details

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

Požadavky ke zkoušce

čeština

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

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

angličtina

The exam will be oral based on the material that was presented.

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

Sylabus

čeština

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

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

angličtina

The Hanani--Tutte theorem and an algebraic algorithm for planarity testing

The Jordan curve theorem

Thrackles

Topological and geometric graphs without forbidden substructures

Complete topological graphs

Possibly other topics

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