Geometrické reprezentace grafů II - NDMI035

• Anglický název: Geometric Representations of Graphs II
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2014 do 2014
• 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: nevyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: prof. RNDr. Jan Kratochvíl, CSc.; doc. RNDr. Vít Jelínek, Ph.D.
• 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

Poslední úprava: T_KAM (27.03.2004)

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.

angličtina

Poslední úprava: T_KAM (06.05.2001)

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

Literatura

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

Golumbic: Algorithmic graph theory

Sylabus

Poslední úprava: T_KAM (27.03.2004)

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ů.