图搜索亦被称为追逃问题,是指一组搜索者在图上尽力抓捕入侵者,可以分为两类:搜索博弈、警察和小偷博弈。最初的警察和小偷博弈是一个完美信息的双人博弈。在现实生活中,警察不可能随时都掌握小偷的下落。因此,研究者提出了一些更贴近现实生活的模型。零可视度警察和小偷博弈作为一个变体,其与最初的警察和小偷博弈有一个明显的区别:小偷是不可见的。当且仅当有警察和小偷占据同一个顶点时,警察才能看见小偷。人们感兴趣的问题是求解小偷被警察抓获需要的最小警察数,而三角多面体和完全分割图的单调零可视度最小警察数及其相关搜索算法尚未被解决。本文针对这些问题展开研究,主要研究内容如下:(一)三角多面体上的零可视度警察和小偷博弈问题。首先提出连通图的一个单调零可视度最小警察数下界;其次提出构造三角多面体和基图的定义;接着应用归纳法证得构造三角多面体与其基图的单调零可视度最小警察数相等;然后提出一个计算凸三角多面体的单调零可视度最优警察策略的线性时间算法。(二)完全分割图上的零可视度警察和小偷博弈问题。首先提出triangle-free图的一个单调零可视度最小警察数下界;其次研究了圈、完全图和完全二部图的单调零可视度最小警察数;在此基础上,根据系数m、n分情形研究完全分割图Sm,n,得出其单调零可视度最小警察数mc0(Sm,n)=[m+1/2];然后提出一个计算完全分割图的单调零可视度最优警察策略的线性时间算法。