Hry na grafech

• Název práce v češtině: Hry na grafech
• Název v anglickém jazyce: Games on graphs
• Akademický rok vypsání: 2006/2007
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: prof. RNDr. Jan Kratochvíl, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 04.01.2007
• Datum zadání: 04.01.2007
• Datum a čas obhajoby: 25.06.2007 00:00
• Datum odevzdání elektronické podoby: 31.05.2007
• Datum odevzdání tištěné podoby: 31.05.2007
• Datum proběhlé obhajoby: 25.06.2007
• Oponenti: RNDr. Martin Pergel, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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

Předběžná náplň práce

Studium her typu "cop and robber" na grafech.

Předběžná náplň práce v anglickém jazyce

Cop and robber games on graphs.