Univerzalita množin bodů pro alternující hamiltonovské cesty

• Název práce v češtině: Univerzalita množin bodů pro alternující hamiltonovské cesty
• Název v anglickém jazyce: Universality of point sets for alternating Hamiltonian paths
• Klíčová slova: geometrický graf|univerzální množina bodů|alternující hamiltonovská cesta
• Klíčová slova anglicky: geometric graph|universal point set|alternating Hamiltonian path
• Akademický rok vypsání: 2023/2024
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: doc. Mgr. Jan Kynčl, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 31.05.2024
• Datum zadání: 03.06.2024
• Datum potvrzení stud. oddělením: 08.01.2025
• Datum a čas obhajoby: 11.02.2025 10:30
• Datum odevzdání elektronické podoby: 10.01.2025
• Datum odevzdání tištěné podoby: 10.01.2025
• Datum proběhlé obhajoby: 11.02.2025
• Oponenti: Mgr. Jan Soukup

Zásady pro vypracování

Úkolem bude pro zadané množiny 2n bodů v rovině zjišťovat, při jakých typech obarvení bodů dvěma barvami existuje alternující hamiltonovská cesta nakreslená pomocí navzájem nekřížících se úseček.

For given sets of 2n points in the plane, the student will investigate for which types of colorings of the points by two colors there is an alternating Hamiltonian path drawn using pairwise noncrossing segments.

Seznam odborné literatury

J. Cibulka, J. Kynčl, V. Mészáros, R. Stolař and P. Valtr, Universal sets for straight-line embeddings of bicolored graphs, in: J. Pach (Ed.), Thirty Essays on Geometric Graph Theory, 101-119, Springer, 2013, ISBN 978-1-4614-0109-4.
A. Kaneko and M. Kano, Discrete Geometry on Red and Blue Points in the Plane - A Survey -, In: Aronov B., Basu S., Pach J., Sharir M. (eds) Discrete and Computational Geometry, Algorithms and Combinatorics, vol 25. Springer, Berlin, Heidelberg, pp 551-570.
M. Kano, J. Urrutia, Discrete geometry on colored point sets in the plane—a survey, Graphs Combin. 37 (2021), no. 1, 1-53.