Název: Alternující cesty v obarvených bodových množinách v konvexní poloze
Překlad názvu: Alternating paths in colored point sets in convex position
Autoři: Papáčková, Marie Guadalupe ; Valtr, Pavel (vedoucí práce) ; Soukup, Jan (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2023
Jazyk: cze
Abstrakt: [cze] [eng]
Tato práce se zabývá problémem nejdelších alternujících cest v obarve- ných bodových množinách v konvexní poloze, především v bodových množi- nách s n červenými a n modrými body. Cílem práce je shrnout hlavní výsledky dosažené v této oblasti a dát je do souvislostí. Nejprve uvedeme základní po- jmy a algoritmus pro hledání nejdelší alternující cesty na konkrétní bodové množině. Vyjádříme si l(n), největší číslo takové, že pro každé uspořádání 2n bodů s n červenými a n modrými body existuje alternující cesta o délce alespoň l(n). Ukážeme souvislost l(n) s problémem největšího separovaného párování. Uvedeme nejdůležitější dolní i horní odhady l(n), včetně nejlepších dosud publikovaných. Nakonec zobecníme problém pro více barev a ukážeme související problém o (anti)palindromech binárních cyklických slov. This thesis deals with the problem of the longest alternating paths in colored point sets in a convex position, especially in point sets with n red and n blue points. The aim of the thesis is to summarize the main results in this area and put them in context. First, we present the basic concepts and the algorithm for finding the longest alternating path on a specific point set. We express l(n), the largest number such that for each arrangement of 2n points with n red and n blue points, there is an alternating path of at least l(n). We show the connection of l(n) to the problem of the largest separated matching. We present the most important lower and upper bounds of l(n), including the best ones published so far. Finally, we generalize the problem for multicolored point sets and show the related problem about (anti)palindromic subsequences of binary circular words.
Klíčová slova: rovina|alternující cesta|obarvená bodová množina|konvexní poloha|separované párování; plane|alternating path|colored point set|convex position|separated matching

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/182986

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-531878


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce