1. Введение и постановка задачи

В работе изучается следующая задача гарантированного поиска. Команда преследователей пытается поймать ``невидимого" для них убегающего на связном топологическом графе. Игроки обладают ``простыми движениями" с ограниченными максимальными скоростями, а топологический граф является фазовым ограничением для их траекторий. Задача заключается в нахождении наименьшего числа преследователей, необходимого для поимки убегающего при тех или иных условиях поиска.

Авторами первых статей, давших толчок к появлению многочисленных публикаций, посвященных задачам поиска на графах, являются Парсонс [18] и Петров [3]. С момента опубликования этих работ задачи поиска на графах привлекают внимание многих исследователей из разных областей математики по нескольким причинам. Первая причина - это связь некоторых задач поиска с играми в камни (pebble games) [13], которые имеют отношение к задачам рационального использования памяти ЭВМ. Во-вторых, выяснилось, что некоторые инварианты графов, первоначально возникшие в теории сверхбольших интегральных схем (СБИС), такие как ширина разреза [16], топологическая ширина ленты [15], величина вершинного разделения графа [9], во многих случаях имеют теоретико-игровую интерпретацию. Третьей причиной является связь задач поиска с путевой и древесной шириной графа - важнейшими параметрами в теории миноров графов, разработанной Робертсоном и Сеймуром [6,8]. Проблемы поиска на графах возникают также в задачах о координации движений роботов [19], в некоторых моделях борьбы с компьютерными вирусами [6] и в задачах сохранения секретности информации, передаваемой по электронным сетям с мобильными подслушивающими устройствами (``жучками") [12]. Подробную информацию о задачах поиска и их ``родственниках" можно найти в обзорах [6,10,17]. Некоторые результаты настоящей статьи опубликованы в [11].

Многие из полученных авторами результатов, нетрадиционных для ``российской" теории управления, встретили понимание и поддержку со стороны выдающегося представителя екатеринбургской математической школы Андрея Измаиловича Субботина, о чем мы, его петербургские коллеги, всегда будем помнить.

В дальнейшем под словом граф мы будем подразумевать конечный связный топологический граф, вершины которого $V(\Gamma )$ суть точки в ${\bf R}^3$, а ребра $E(\Gamma )$ - непересекающиеся конечнозвенные ломаные с концами в соответствующих вершинах. Граф предполагается не имеющим петель и кратных ребер.

На графе $\Gamma$ находятся $n$ преследователей $P_1,\dots,P_{n}$ и убегающий $E$. Предполагается, что преследователи и убегающий обладают в ${\bf R}^3$ (граф вложен в ${\bf R}^3$) простыми движениями:

$$\begin{eqnarray*} (P_i) :& \qquad \dot x_i = u_i, & \Vert u_i \Vert \le 1, \qqu... ... {n}\},\\ (E): & \qquad \dot y= u_0, & \Vert u_0 \Vert \le \mu, \end{eqnarray*}$$

причем $\Gamma$ является для игроков фазовым ограничением. Для простоты считается, что допустимыми управлениями игроков являются кусочно-постоянные функции, заданные на произвольных промежутках $[0,T]$. Таким образом, допустимыми траекториями будут кусочно-аффинные
вектор-функции со значениями в $\Gamma$.

Обозначим через $\rho$ внутреннюю метрику графа $\Gamma$, т.е. $\rho(x,y)$ есть длина (в евклидовой метрике) кратчайшего пути в $\Gamma$ с концами в $x$ и $y$, а через $\varepsilon$ - неотрицательное число, характеризующее ``радиус поимки".

Убегающий $E$ считается пойманным преследователем $P_{i}$ в момент $t \in [0,T]$, если $\rho(x_{i}(t), y(t))\le \varepsilon$. Совокупность траекторий преследователей $x_i \colon [0,T]\to \Gamma$, ${i}\in\{{1},\dots, {n}\}$ называется программой преследователей, заданной на промежутке $[0,T]$. Программа $n$ преследователей $\{x_{1},\dots,x_{n}\}$, заданная на $[0,T]$, называется выигрывающей, если для любой траектории убегающего $y$, заданной на $[0,T]$, существуют $t \in [0,T]$ и ${i}\in\{{1},\dots, {n}\}$ такие, что $\rho(x_{i}(t), y(t))\le \varepsilon$, т.е. независимо от выбора траектории убегающий ловится одним из преследователей. Ставится вопрос о нахождении наименьшего натурального числа $n$ такого, что у $n$ преследователей существует выигрывающая программа, заданная на некотором промежутке $[0,T]$. Понятно, что эта величина зависит только от графа $\Gamma$, а также от чисел $\mu$ и $\varepsilon$. Будем обозначать ее че-
рез $S_{\mu }^{\varepsilon}(\Gamma )$.

Задачу поиска бывает удобно интерпретировать как задачу очистки графа от ``распыленного" убегающего. Будем говорить, что для программы $\Pi=$ $\{x_1(t)$, $\dots ,x_n(t)\}$, $t \in [0,T]$, точка $x\in \Gamma$ является загрязненной в момент времени $t^* \in [0,T]$, если найдется траектория убегающего $y(t)$, $t\in [0,t^*]$, такая, что $y(t^*)=x$, и для всякого ${i}\in\{{1},\dots, {n}\}$ и $t\in [0,t^*]$ имеет место неравенство $\rho(y(t), x_i (t)) > \varepsilon$. Множество загрязненных в момент $t^*$ точек графа $\Gamma$ обозначим через ${\cal{C}}(\Pi,\Gamma ,t^*)$. Множество точек $\Gamma \setminus {\cal{C}}(\Pi,\Gamma ,t^*)$ называется очищенным в момент $t^*$ множеством. Очевидно, что программа $\Pi= \{x_1(t),\dots ,x_n(t)\}$, $t \in [0,T]$ является выигрывающей тогда и только тогда, когда для некоторого $t^* \in [0,T]$ весь граф $\Gamma$ очищен.

Случай $\mu = +\infty$ (убегающий может двигаться сколь угодно быстро) и $\varepsilon =0$ первоначально рассматривался Парсонсом [18]. Отметим, что в этом случае наименьшее число преследователей, необходимое для существования выигрывающей программы, не зависит от длин ребер и является инвариантом, зависящим только от комбинаторной схемы графа. Случай, когда $\mu = +\infty$ и $\varepsilon \ge 0$ изучался Головачем [1], а случай $\mu \ge 0$ и $\varepsilon =0$ - Петровым [3]. Задачи поиска Головача и Петрова являются естественным обобщением задачи Парсонса. Зависимость от длин ребер значительно усложняет решение задачи и определить величину $S_{\mu }^{\varepsilon}(\Gamma )$ можно лишь в исключительных случаях.

Одним из основополагающих фактов в изучении задачи поиска является теорема ЛаПо [14], гласящая, что в случае $\mu = +\infty$ и $\varepsilon =0$ the ``recontamination`` does not help to search a graph.¹ К сожалению, для более общих задач поиска данный факт не верен и ``стандартная" техника неприменима.

Ранее в работах [1,2,4,5] авторами был получен ряд фундаментальных результатов о поиске. Основной целью данной работы является демонстрация того, как можно применять эти результаты при решении модельных задач.

В настоящей работе мы обозначаем через $T$, $C$, $O$ графы, состоящие из всех ребер и вершин тетраэдра, куба и октаэдра, соответственно. Полный граф с $n$ вершинами (т.е. граф, любые две вершины которого смежны) обозначается через $K_n$. Заметим, что графы $K_4$ и $T$ изоморфны. Мы полагаем, что в графах $T$, $C$, $O$ и $K_n$ все ребра имеют единичную длину.

Дальнейшая часть работы имеет следующую структуру. В §2 вычисляются числа $S_{\infty }^{\varepsilon}(T )$, $S_{\infty }^{\varepsilon}(C )$, $S_{\infty }^{\varepsilon}(O )$ и $S_{\infty }^{\varepsilon}(K_n )$ для всех $\varepsilon \ge 0$. В §3 доказывается, что для всякого $n\ge 4$ $S_{\mu }^{0}(K_n )=n$ при $\mu \ge 1$. Далее находятся числа $S_{\mu }^{0}(T )$, $S_{\mu }^{0}(C )$ и $S_{\mu }^{0}(O )$ при $\mu \ge 1$ и доказывается, что $S_{\mu }^{0}(T )\le 2$ при $\mu \le 1/3$, $S_{\mu }^{0}(C )\le 3$ при $\mu < 0.5$ и $S_{\mu }^{0}(C )\le 2$ при $\mu \le 0.2$. В заключение (§4) мы формулируем некоторые гипотезы о поисковых числах графов правильных многогранников.