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 2014 do 2014
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní 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: nevyučován
• Jazyk výuky: češ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: Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

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.

angličtina

Poslední úprava: G_I (26.10.2001)

Overview of intersection defined classes of graphs, mainly of geometric objects in the plane (interval graphs, circle graphs, circular arc graphs, permutation graphs, cocomparability graphs). Characterization theorems and recognition.

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