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.
Last update: 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.
Course completion requirements -
Last update: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
Oral exam
Last update: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
Ústní zkouška
Requirements to the exam -
Last update: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
The exam is oral. The requirements correspond to the syllabus of the course, as covered by the lectures.
Last update: 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.
Syllabus -
Last update: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
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).
Last update: 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ě.