Geometrické reprezentace grafů 2 - NDMI035

• Anglický název: Geometric Representations of Graphs 2
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2025
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní 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: vyučován
• Jazyk výuky: angličtina
• Způsob výuky: prezenční
• Garant: prof. RNDr. Jan Kratochvíl, CSc.; doc. RNDr. Vít Jelínek, Ph.D.
• Vyučující: doc. RNDr. Vít Jelínek, Ph.D.; prof. RNDr. Jan Kratochvíl, CSc.
• Třída: DS, diskrétní modely a algoritmy; Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Diskrétní matematika
• Je neslučitelnost pro: NDMI019
• Je záměnnost pro: NDMI019

Anotace

čeština

Průnikové grafy především geometricky definované - algoritmy a charakterizační věty. Volně navazuje na Geometrické reprezentace grafů I (DMI037). Vhodné pro 5.ročník a PGS.

Poslední úprava: T_KAM (27.03.2004)

angličtina

Advanced course in Computer Science Intersection and contact representations of graphs, including interval graphs, chordal graphs, circle graphs, circular-arc graphs, segment-intersection graphs, string graphs. Characterization theorems, NP-hardness results for recognition. Sizes of representations. Optimization algorithms for classes of intersection graphs. Representations of planar graphs (kissing lemma, visibility representations, drawing on small size grid).

Poslední úprava: T_KAM (06.05.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)

Literatura

Golumbic: Algorithmic graph theory

Poslední úprava: Zakouřil Pavel, RNDr., Ph.D. (05.08.2002)

Požadavky ke zkoušce

čeština

Zkouška je ústní. Požadavky ke zkoušce odpovídají sylabu 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

NP-úplnost rozpoznávání (průnikové grafy úseček, konvexních množin a křivek).

Velikosti reprezentací (grafy vynucující reprezentace exponenciální velikosti).

Reprezentovatelnost planárních grafů (Koebeho věta o kruzích, bipartitní grafy jako grafy viditelnosti).

Odhady na barevnost jako funkce klikovosti.

Kreslení rovinných grafů na pevnou množinu bodů.

3-dimenzionální kreslení grafů.

Poslední úprava: T_KAM (27.03.2004)

angličtina

NP-hardness of recognition (intersection graphs of segments, convex sets and strings).

Sizes of representation (graphs requiring representations of exponential size).

Representability of planar graphs (Koebe's theorem on touching circles, bipartite graphs as visibility graphs).

Bounds on chromatic number as a function of the clique number.

Drawing planar graphs on a fixed point set.

3-dimensional graph representation.

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