SubjectsSubjects(version: 837)
Course, academic year 2018/2019
   Login via CAS
Geometric Representations of Graphs I - NDMI037
Title in English: Geometrické reprezentace grafů I
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: not taught
Language: Czech
Teaching methods: full-time
Guarantor: prof. RNDr. Jan Kratochvíl, CSc.
doc. RNDr. Vít Jelínek, Ph.D.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: 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.
Requirements to the exam - Czech
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 - Czech
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ě.

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

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

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html