PředmětyPředměty(verze: 873)
Předmět, akademický rok 2020/2021
  
Průsečíková čísla grafů - NDMI099
Anglický název: Crossing numbers of 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/crossings/
Garant: Mgr. Jan Kynčl, Ph.D.
RNDr. Martin Balko, 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
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (25.04.2018)
Průsečíkové číslo grafu je základní grafový parametr, důležitý hlavně pro vizualizaci grafů. Jeho určení je algoritmicky těžké, dokonce i pro úplné grafy přesná hodnota průsečíkového čísla stále není známá. Kromě klasického pojmu minimálního počtu křížení v nakreslení v rovině bylo studováno mnoho dalších variant průsečíkových čísel; v přednášce se zaměříme na několik hlavních z nich. Předpokládají se základní znalosti z teorie grafů, kombinatorické geometrie (NDMI009) a výpočetní složitosti (pojem NP-úplnosti).
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. (25.04.2018)
Marcus Schaefer, The Graph Crossing Number and its Variants: A Survey, The Electronic Journal of Combinatorics, Dynamic Survey DS21 (2017), http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS21

Marcus Schaefer, Crossing numbers of graphs, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2018, ISBN: 978-1-4987-5049-3

Odborné články (bude upřesněno)

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

Varianty průsečíkových čísel (rektilineární, monotónní, párové, liché, nezávislé) a vztahy mezi nimi

Dolní odhady na průsečíková čísla - varianty průsečíkového lemma

Existence podgrafu s vysokým průsečíkovým číslem

Algoritmická složitost určení průsečíkového čísla

Průsečíková čísla úplných grafů

Průsečíková čísla dalších grafů, např. grafů vnořitelných na určitou plochu

 
Univerzita Karlova | Informační systém UK