Hry na grafech
| Thesis title in Czech: | Hry na grafech |
|---|---|
| Thesis title in English: | Games on graphs |
| Academic year of topic announcement: | 2006/2007 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | prof. RNDr. Jan Kratochvíl, CSc. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 04.01.2007 |
| Date of assignment: | 04.01.2007 |
| Date and time of defence: | 25.06.2007 00:00 |
| Date of electronic submission: | 31.05.2007 |
| Date of submission of printed version: | 31.05.2007 |
| Date of proceeded defence: | 25.06.2007 |
| Opponents: | RNDr. Martin Pergel, Ph.D. |
| Guidelines |
| Budou studovány hry na grafech, tzv. cop and robber games. Mezi zajímavé otázky patří minimální počet "policistů" nutných k chycění "zloděje" v daném grafu (tzv. cop number) a nejdelší počet kroků, po který se zloděj může v grafu schovávat (tzv. cop time). Zpřesnění některých známých odhadů bude pravděpodobně vyžadovat využití počítače. |
| References |
| A. Bonato, P. Golovach, G. Hahn, J. Kratochvíl, The search-time of a graph, to appear in Discr. Math.
B. Alspach, Sweeping and searching in graphs: a brief survey, to appear in Discr. Math. A. Berarducci, B. Intrigila, On the cop number of a graph, Advances in Applied Math. 14 (1993) 389--403 A. S. Goldstein, E. M. Reingold, The complexity of pursuit on a graph, Theoret. Comput. Sci. 143 (1995) 93--112 G. Hahn, F. Laviolette, N. Sauer, R.E. Woodrow, On cop-win graphs, Discr. Math. 258 (2002) 27--41 R. Nowakowski, P. Winkler, Vertex-to-vertex pursuit in a graph, Discr. Math. 43 (1983) 235--239 a další časopisecká literatura dle zadání vedoucího |
| Preliminary scope of work |
| Studium her typu "cop and robber" na grafech. |
| Preliminary scope of work in English |
| Cop and robber games on graphs. |