Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 368)
Detail práce
   Přihlásit přes CAS
Dotykové grafy kružníc a Möbiove transformácie
Název práce v jazyce práce (slovenština): Dotykové grafy kružníc a Möbiove transformácie
Název práce v češtině: Dotykové grafy kružnic a Möbiovy transformace
Název v anglickém jazyce: Circle packing and Möbius transformations
Klíčová slova: geometrické reprezentácie grafov, circle packing, primal-dual circle packing, zložitosť, Möbiove transformácie
Klíčová slova anglicky: geometric representation of graphs, circle packing, primal-dual circle packing, computational complexity, Möbius transformations
Akademický rok vypsání: 2017/2018
Typ práce: bakalářská práce
Jazyk práce: slovenština
Ústav: Katedra aplikované matematiky (32-KAM)
Vedoucí / školitel: Mgr. Peter Zeman
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 16.03.2018
Datum zadání: 02.04.2018
Datum potvrzení stud. oddělením: 01.06.2018
Datum a čas obhajoby: 14.02.2019 10:00
Datum odevzdání elektronické podoby:03.01.2019
Datum odevzdání tištěné podoby:04.01.2019
Datum proběhlé obhajoby: 14.02.2019
Oponenti: prof. RNDr. Jan Kratochvíl, CSc.
 
 
 
Zásady pro vypracování
Študent/ka spracuje známe poznatky ohľadne dotykových grafov kružníc. Veta o dotykových grafoch kružníc (Circle packing theorem) hovorí, že graf je rovinný práve vtedy, keď je možné ho reprezentovať ako dotykový graf kružníc. Túto vetu dokázali nezávisle Koebe, Andreev a Thurston. Jedným z cieľov práce bude prehľadne spísať dôkaz tejto vety.

Ďalšia časť práce sa bude venovať algoritmom. Študent/ka prehľadne spíše popis algoritmu, ktorý v danej presnosti spočíta v polynomiálnom čase reprezentáciu rovinného grafu pomocou kružníc [1].

Dôležitý problém v oblasti geometrických reprezentácií grafov je testovať, či sa čiastočná reprezentácia dá rozšíriť. V prípade všeobecných dotykových grafov kružníc je tento problém NP-úplný [3]. Na druhú stranu, reprezentácia rovinnej triangulácie pomocou dotykov kružníc je jednoznačná, až na aplikáciu Möbiovej transformácie. Študent/ka sa zamyslí, či je v tomto prípade možné využiť poznatky komplexnej analýzy a poznatky ohľadne Möbiových transformácií k popisu polynomiálneho algoritmu na rozširovanie čiastočných reprezentácií [2].
Seznam odborné literatury
[1] Mohar, Bojan. "A polynomial time circle packing algorithm." Discrete Mathematics 117.1-3 (1993): 257-263.
[2] Needham, Tristan. Visual complex analysis. Oxford University Press, 1998.
[3] Chaplick, Steven, et al. "Contact representations of planar graphs: Extending a partial representation is hard." International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, Cham, 2014.
 
Univerzita Karlova | Informační systém UK