Předmět Geometrické reprezentace grafů II (NDMI035)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NDMI035 - Geometrické reprezentace grafů II, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Sylabus
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ů.
Literatura
Golumbic: Algorithmic graph theory
Garant
prof. RNDr. Jan Kratochvíl, CSc.RNDr. Vít Jelínek, Ph.D.