PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Geometrické reprezentace grafů 2 - NDMI035
Anglický název: Geometric Representations of Graphs 2
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2023
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
Způsob výuky: prezenční
Způsob výuky: prezenční
Garant: prof. RNDr. Jan Kratochvíl, CSc.
doc. RNDr. Vít Jelínek, Ph.D.
Třída: DS, diskrétní modely a algoritmy
Informatika Mgr. - volitelný
Kategorizace předmětu: Informatika > Diskrétní matematika
Je neslučitelnost pro: NDMI019
Je záměnnost pro: NDMI019
Anotace -
Poslední úprava: T_KAM (27.03.2004)
Průnikové grafy především geometricky definované - algoritmy a charakterizační věty. Volně navazuje na Geometrické reprezentace grafů I (DMI037). Vhodné pro 5.ročník a PGS.
Podmínky zakončení předmětu -
Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)

Ústní zkouška

Literatura
Poslední úprava: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)

Golumbic: Algorithmic graph theory

Požadavky ke zkoušce -
Poslední úprava: prof. RNDr. Jan Kratochvíl, CSc. (12.10.2017)

Zkouška je ústní. Požadavky ke zkoušce odpovídají sylabu v rozsahu předneseném na přednášce.

Sylabus -
Poslední úprava: T_KAM (27.03.2004)

NP-úplnost rozpoznávání (průnikové grafy úseček, konvexních množin a křivek).

Velikosti reprezentací (grafy vynucující reprezentace exponenciální velikosti).

Reprezentovatelnost planárních grafů (Koebeho věta o kruzích, bipartitní grafy jako grafy viditelnosti).

Odhady na barevnost jako funkce klikovosti.

Kreslení rovinných grafů na pevnou množinu bodů.

3-dimenzionální kreslení grafů.

 
Univerzita Karlova | Informační systém UK