Geometrické reprezentace grafů 1 - NDMI037

• Anglický název: Geometric Representations of Graphs 1
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• 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í
• 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

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.

Poslední úprava: G_I (17.03.2011)

angličtina

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.

Poslední úprava: G_I (26.10.2001)

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

čeština

Ústní zkouška

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (10.06.2019)

angličtina

Oral exam

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (10.06.2019)

Požadavky ke zkoušce

čeština

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

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (12.10.2017)

angličtina

The exam is oral. The requirements correspond to the syllabus of the course, as covered by the lectures.

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (10.06.2019)

Sylabus

čeština

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

Poslední úprava: T_KAM (27.03.2004)

angličtina

Intersevtion graph classes: interval, chordal, circular arc, circle, permutation, comparability, segment, convex, and string graphs in the plane.

Characterisation results (interval, chordal, comparability and permutation graphs)

Recognition algorithms (chordal and comparability graphs).

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (10.06.2019)