Dissertation/ Thesis
Alternující cesty v obarvených bodových množinách v konvexní poloze ; Alternating paths in colored point sets in convex position
| العنوان: | Alternující cesty v obarvených bodových množinách v konvexní poloze ; Alternating paths in colored point sets in convex position |
|---|---|
| المؤلفون: | Papáčková, Marie Guadalupe |
| المساهمون: | Valtr, Pavel, Soukup, Jan |
| بيانات النشر: | Univerzita Karlova, Matematicko-fyzikální fakulta |
| سنة النشر: | 2023 |
| المجموعة: | Charles University: CU Digital repository / Univerzita Karlova: Digitální repozitář UK |
| مصطلحات موضوعية: | plane|alternating path|colored point set|convex position|separated matching, rovina|alternující cesta|obarvená bodová množina|konvexní poloha|separované párování |
| الوصف: | 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. ; 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. ; Katedra aplikované matematiky ; Department of Applied Mathematics ; Faculty of Mathematics and Physics ; Matematicko-fyzikální fakulta |
| نوع الوثيقة: | bachelor thesis |
| وصف الملف: | application/pdf |
| اللغة: | unknown Czech |
| Relation: | http://hdl.handle.net/20.500.11956/182986; 256041 |
| الاتاحة: | https://hdl.handle.net/20.500.11956/182986 |
| رقم الانضمام: | edsbas.D18CFA8E |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |