資源描述：
《圖論中的追捕問(wèn)題——警察抓小偷》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、研究生圖論課程作業(yè)（論文）?重慶郵電大學(xué)圖論論文題目：圖論中的游戲——警察抓小偷學(xué)院名稱：通信與信息工程學(xué)院學(xué)生姓名：周易德專業(yè)：信息與通信工程班級(jí)：通信14班學(xué)號(hào)：S160101195聯(lián)系方式：goliathchoe@foxmail.com指導(dǎo)教師：李紅剛2016年12月-1-研究生圖論課程作業(yè)（論文）?摘要本文簡(jiǎn)要地介紹了一種簡(jiǎn)單的圖論游戲——警察抓小偷（agameofcopsandrobbers）。這是一個(gè)在圖上進(jìn)行的點(diǎn)追捕游戲（vertex-pursuitgame），通常由一個(gè)警察或多個(gè)警察和一個(gè)小偷組成，兩名隊(duì)玩家在一個(gè)有限無(wú)向簡(jiǎn)單圖上進(jìn)行游戲，且交替沿著邊進(jìn)行
2、移動(dòng)。當(dāng)任意警察與小偷重合時(shí)，則代表警察抓住了小偷；反之，如果小偷一直不能被捉住，則小偷贏。關(guān)于這個(gè)游戲，雖然看似簡(jiǎn)單并已經(jīng)被研究了三十多年，但仍然有一些未能解決的問(wèn)題和未能證明的假設(shè)。本文旨在介紹這個(gè)游戲規(guī)則，并從零開始介紹一些由此引發(fā)的簡(jiǎn)單定理，并在力所能及的范圍內(nèi)嘗試證明它們?！娟P(guān)鍵詞】Pursuit-evasiongameongraphs;CopsandRobbers;Vertex-pursuitGame;MeynielsConjectureABSTRACTThisarticlebrieflyintroducesasimplegameongraphswhichca
3、lledthepolicecatchthethief,oragameofcopsandrobbers.ThisisaPursuitGame,usuallyincludingatleastonepolicemanandonlyonethief,whoplayonafiniteundirectedgraphandmovealongtheedgealternately.Whenanyofpolicemenandthethiefcoincidewitheachother,itmeansthatthepolicemanseizedthethief.Ontheotherhand,if
4、thethiefhasbeenunabletobecaught,thethiefisconsideredtowin.Aboutthisgame,althoughseeminglysimpleandhasbeenstudiedforoverthirtyyears,therearestillsomeunsolvedproblemsandunprovenassumptions.Thepurposeofthisarticleistointroducetherulesofthegameandintroducesomeofthesimpletheoremsthatresultfrom
5、them,andtrytoprovethemwithinmylimits.【Keywords】Pursuit-evasiongameongraphs;CopsandRobbers;Vertex-pursuitGame;MeynielsConjecture-2-研究生圖論課程作業(yè)（論文）?1.游戲簡(jiǎn)介警察抓小偷（Agameofcopsandrobbers或vertex-pursuitgame）最早是由R.Nowakowski和P.Winkler于1983年,在[1]中提出的。游戲由兩隊(duì)人組成警察和小偷組成。玩家在一個(gè)有限的無(wú)向簡(jiǎn)單連通圖G中進(jìn)行，每個(gè)小偷和警察能交替地沿著邊
6、在相鄰的點(diǎn)之間移動(dòng)或者選擇停留在原地。警察可能不止一個(gè)，他們的目的抓住小偷，也就是通過(guò)不斷移動(dòng)與小偷所在點(diǎn)重合。而小偷的目的當(dāng)然是永遠(yuǎn)不要被警察抓住。這樣一個(gè)簡(jiǎn)答的游戲卻引出了一串復(fù)雜的理論。游戲開始時(shí)，先由每個(gè)警察選一個(gè)點(diǎn)作為初始位置；之后再由小偷選擇初始位置。之后，每個(gè)回合小偷和警察都只能移動(dòng)“一步”，即只能從自己所在點(diǎn)前往這個(gè)點(diǎn)的相鄰定點(diǎn)。為了化簡(jiǎn)問(wèn)題的難度，我們認(rèn)為小偷和警察的位置都不是秘密的，即所有人都知道其他人的位置。在確定的有限無(wú)向簡(jiǎn)單圖上的游戲流程如下：1.警察選擇初始位置，位置可以重疊。2.小偷選擇初始位置，令t=1。3.第t回合開始，每個(gè)警察可以選擇移
7、動(dòng)至鄰居點(diǎn)或者停留。每個(gè)警察都只能移動(dòng)一步。4.如果警察到達(dá)了小偷所在點(diǎn)則游戲結(jié)束，否則繼續(xù)。5.小偷可以選擇移動(dòng)至鄰居點(diǎn)或者停留。小偷只能移動(dòng)一步。6.t=t+1,返回3注意我們定義的游戲是警察先選擇初始位置，小偷后選擇初始位置。每回合開始也是警察先移動(dòng)。后文中提到“回合開始時(shí)”就是指輪到警察選擇前的時(shí)刻。游戲過(guò)程中，小偷和警察知道關(guān)于游戲的所有信息，包括：(1)圖G的連接情況；（2）所有警察和小偷的。這種所有玩家擁有關(guān)于游戲的所有信息在博弈論中被稱為完全信息（completeinformation）。在[2]中，Isler
