Geometrické reprezentace grafů 1 - NDMI037

• Anglický název: Geometric Representations of Graphs 1
• Podoba výuky: přednáška
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2025 do 2025
• Počet semestrů výuky: 1
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Maximální kapacita předmětu: 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: čeština
• Forma uskutečňování: prezenční
• Možnost opakovaného zápisu: 2 / 2 / 2 / 2
• Garant: prof. RNDr. Jan Kratochvíl, CSc.; doc. RNDr. Vít Jelínek, Ph.D.
• Vyučující: prof. RNDr. Jan Kratochvíl, CSc.
• 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)

Kontroly studia předmětu a podmínky pro jejich úspěšné vykonání, způsob hodnocení

č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)