PředmětyPředměty(verze: 807)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Geometrické reprezentace grafů I - NDMI037
Anglický název: Geometric Representations of Graphs I
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní 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
Způsob výuky: prezenční
Garant: prof. RNDr. Jan Kratochvíl, CSc.
doc. RNDr. Vít Jelínek, Ph.D.
Třída: Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Diskrétní matematika
Anotace -
Poslední úprava: G_I (17.03.2011)

Průnikové grafy především geometricky definované - algoritmy a charakterizační věty. Vhodné pro 5.ročník a PGS. Předpokládají se vstupní znalosti alespoň na úrovni předmětu NDMI011 Kombinatorika a grafy I.
Požadavky ke zkoušce
Poslední úprava: prof. RNDr. Jan Kratochvíl, CSc. (12.10.2017)

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

Sylabus
Poslední úprava: T_KAM (27.03.2004)

Průnikově definované třídy grafů - intervalové, chordální, obloukové, sečnové, permutační, srovnatelné, průnikové grafy úseček, konvexních množin a křivek v rovině.

Charakterizační věty (intervalové, chordální, srovnatelné, permutační grafy).

Algoritmy na rozpoznávání (chordální, srovnatelné).

 
Univerzita Karlova | Informační systém UK