Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 336)
Detail práce
   Přihlásit přes CAS
Cops and robber game on directed complete graphs
Název práce v češtině: Hra Cops and robber na orientovaných úplných grafech
Název v anglickém jazyce: Cops and robber game on directed complete graphs
Klíčová slova: hra Cops and robber, teorie her, teorie grafů, turnaje
Klíčová slova anglicky: Cops and robber game, game theory, graph theory, tournaments
Akademický rok vypsání: 2014/2015
Typ práce: bakalářská práce
Jazyk práce: angličtina
Ústav: Katedra aplikované matematiky (32-KAM)
Vedoucí / školitel: Mgr. Tomáš Gavenčiak, Ph.D.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 21.01.2015
Datum zadání: 21.01.2015
Datum potvrzení stud. oddělením: 19.03.2015
Datum a čas obhajoby: 15.06.2015 00:00
Datum odevzdání elektronické podoby:21.05.2015
Datum odevzdání tištěné podoby:21.05.2015
Datum proběhlé obhajoby: 15.06.2015
Oponenti: doc. RNDr. Vít Jelínek, Ph.D.
 
 
 
Zásady pro vypracování
Cílem práce je prozkoumat hru Cops and robber (četníci a zloděj) na orientovaných úplných grafech (turnajích) jak obecně, tak na speciálních typech turnajů jako například cirkulární a Cayleho grafy či vyvážené turnaje. Je třeba prozkoumat vztahy nutného počtu četníků k velikosti grafu, délce hry, stupňům vrcholů a případně dalším vlastnostem. Speciálně je možné zaměřit se na otázku prof. Geni Hahna, zda ve všech turnajích vzniklých orientací Steinerovského systému trojic stačí k polapení zloděje 2 četníci a 2 tahy.

Během práce předpokládáme jak teoretickou práci a výsledky, tak možnost použití vlastních programů pro prozkoumání některých případů. Samotné programy ale nejsou hlavním výstupem této práce.
Seznam odborné literatury
Anthony Bonato, Richard J. Nowakowski: The Game of Cops and Robbers on Graphs, AMS (2011)
Richard J. Nowakowski, Peter Winkler: Vertex to vertex pursuit in a graph, Discrete Math. 43 (1983)
Brian Alspach: Searching and Sweeping Graphs: A Brief Survey, Le Matematiche 59 (2004)
Michel Boyer et al.: Cops-and-robbers: remarks and problems, JCMCC vol. 85 (2013)

Další literatura dle doporučení vedoucího.
Předběžná náplň práce
Hra Cops and robber je motivována pronásledováním či hledáním zločince či pohřešovaného skupinou koordinovaných četníků či zachránců ve známém prostředí. Jedná se sice o velké zjednodušení na to, aby měla hra přímé bezpečnostní uplatnění, ale od svého vzniku v roce 1983 je velmi populární v teorii her i grafů a časem se ukázaly zajímavé souvislosti s několika jinými grafovými parametry.

Práce se zaměří na tuto hru na orientovaných úplných grafech (turnajích), kde ještě nebyla úplně prozkoumána a pokusí se odpovědět na některé otázky v této oblasti. Bližší detaily viz Zásady pro vypracování.
Předběžná náplň práce v anglickém jazyce
The game of Cops and robber is motivated by pursuit of criminals or missing persons by a coordinated group of policemen or rescuers in a known environment. Although this combinatorial game is too simplified to have direct security applications, it is very popular in game theory and graph theory since its introduction in 1983, and it was shown to have interesting connections with several other graph properties.

The work will focus on the game played on directed complete graphs (tournaments) where it has not been fully explored yet, and will try to answer some of the questions in this area. For more details, see Zásady pro vypracování.
 
Univerzita Karlova | Informační systém UK