3. Случай $\mathbf \mu \ge 0$, $\mathbf \varepsilon = 0$

Пусть $\Gamma$ - граф, все ребра которого имеют единичную длину. Заданная на $[0,T]$ программа преследователей $\Pi$ называется дискретной, если $T$ - натуральное число и для всякого $k \in \{1,\dots, T\}$ на протяжении $[k-1,k]$ каждый из преследователей либо стоит в вершине графа, либо переходит из вершины в смежную вершину с максимальной скоростью.

Следующее утверждение доказывается в работе [5].

Теорема 9.   Пусть $\Gamma$ - граф, все ребра которого имеют единичную длину. Тогда следующие утверждения эквивалентны:

1. При $\mu=1$, $\varepsilon =0$ на $\Gamma$ существует выигрывающая программа $n$ преследователей.
2. При $\mu=1$, $\varepsilon =0$ на $\Gamma$ существует дискретная выигрывающая программа $n$ преследователей.

Введем обозначения, необходимые для дальнейших доказательств.
Пусть $\Gamma$ - один из графов $\{C,T,O, K_n\}$, $n\ge 4$. Рассмотрим некоторую дискретную программу $\Pi$ на $\Gamma$ при $\mu=1$. Легко убедиться, что во всякий целочисленный момент времени $k$ внутренность всякого ребра (в топологии ${{\bf R}}^3$) графа $\Gamma$ либо целиком очищена, либо целиком загрязнена.

Обозначим через $p_i (v)$ число преследователей, находящихся в момент $i$ в вершине $v$. Назовем вершину $v$ особой в момент $i$, если $p_i (v)$ не меньше числа загрязненных ребер, инцидентных этой вершине. Будем обозначать через $A_i$ множество всех особых вершин в момент $i$, а через $a_i$ - его мощность. Будем говорить, что вершина $v$ является $k$-особой в момент $i$, если $v\in A_i$ и $p_i (v) =k$. Назовем вершину $v$ голой в момент $i$, если все инцидентные ей ребра в этот момент загрязнены. Будем обозначать через $B_i$ множество всех голых вершин в момент $i$, а через $b_i$ - его мощность. Пусть $v$ - вершина степени $\ge 3$ графа $\Gamma$. Тогда для всякой дискретной программы $\Pi$ на $\Gamma$ легко доказываются следующие утверждения:

Лемма 1.   Если $v\not\in A_i$ и $p_{i+1} (v) =0$, то $v\in B_{i+1}$.

Лемма 2.   Если $v\not\in A_i$ и $v\in A_{i+1}$, то $p_{i+1} (v)\ge 2$.

Докажем теперь основную теорему, касающуюся полных графов.

Теорема 10.   Пусть $K_{n+1}$ - полный топологический граф с $n+1$ вершиной, все ребра которого имеют единичную длину. Тогда $S_{1}(K_{n+1} ) = n+1$ для всех $n\ge 3$.

Д о к а з а т е л ь с т в о. Заметим прежде всего, что $n+1$ преследователей достаточно для поимки убегающего на $K_{n+1}$ при любом $\mu$. Для доказательства неравенства $S_1(K_{n+1} ) \ge n+1$ покажем, что ни одна программа для $n$ преследователей не может быть выигрывающей. Предположим противное, и пусть $\Pi$ - выигрывающая программа для $n$ преследователей. Сославшись на теорему 9, мы можем предполагать, что $\Pi$ является дискретной программой.

Покажем, что при реализации $\Pi$ все величины $a_j \le 2$ и, следовательно, эта программа не может быть выигрывающей.

Рассмотрим три случая.

Случай 1. $a_j =0$, $a_{j+1}=k \ge 1$, т.е. в момент $j$ особых вершин не было, а в момент $j+1$ их стало $k\colon v_1,\dots , v_k$.

Тогда в момент $j+1$ в неособых вершинах находятся

$$n - \sum_{i=1}^{k} p_{j+1} (v_i)$$

преследователей и существует не менее

$$l\stackrel{\bigtriangleup}{=}(n+1) - k - \left( n - \sum_{i=1}^{k} p_{j+1} (v_i)\right)= \sum_{i=1}^{k} p_{j+1} (v_i) - k +1$$

вершин, свободных от преследователей. По лемме 1 все эти вершины должны быть голыми в момент $j+1$. Так как все они смежны с каждой особой вершиной, то $p_{j+1} (v_i)\ge l$ для $i = 1, \dots, k$ и, следовательно,

$$kl +n - \sum_{i=1}^{k} p_{j+1} (v_i)\le n.$$

Это неравенство может быть переписано в виде

$$(1-k)\left(\sum_{i=1}^{k} p_{j+1} (v_i) -k \right)\ge 0.$$

Так как по лемме 2 $p_{j+1} (v_i) \ge 2$ для всех $i = 1, \dots, k$, то отсюда следует, что $a_{j+1} = k = 1$. Таким образом, в случае 1 может возникнуть только одна особая вершина.

Случай 2. В момент $j$ была одна особая вершина $v_0$, а в момент $j+1$ особых вершин стало $k+1 \colon v_0, v_1,\dots , v_k$, $k\ge 1$, (т.е. добавилось $k$ новых особых вершин).

Тогда в неособых вершинах в момент $j+1$ находятся

$$n - \sum_{i=0}^{k} p_{j+1} (v_i)$$

преследователей и

$$b_{j+1}\ge l\stackrel{\bigtriangleup}{=}(n+1) - (k+1) - \lef... ...1}^{k} p_{j+1} (v_i)\right)= \sum_{i=0}^{k} p_{j+1} (v_i) - k.$$

Заметим, что в силу леммы 2 $l>0$. Отсюда, рассуждая так же, как и в случае 1, заключаем, что во всех особых вершинах в момент $j+1$ должно находиться не менее $(k+1)l$ преследователей. Следовательно,

$$(k+1)l +n - \sum_{i=0}^{k} p_{j+1} (v_i ) \le n.$$

Это неравенство равносильно следующему

$$\sum_{i=0}^{k} p_{j+1} (v_i ) \le k+1.$$

Замечая, что в силу леммы 2 левая часть этого неравенства не меньше $p_{j+1} (v_0 ) + 2k$, получаем, $p_{j+1} (v_0 )=0$, что невозможно, так как $p_{j+1} (v_0 )\ge l >0$. Таким образом, случай 2 реализоваться не может.

Случай 3. В момент $j$ была одна особая вершина $u_0$, а в момент $j+1$ их стало $k\colon v_1,\dots , v_k$, $k\ge 2$, (т.е. вершина $u_0$ стала неособой и добавилось $k$ новых особых вершин). Тогда в неособых вершинах в момент $j+1$ находятся

$$n - \sum_{i=1}^{k} p_{j+1} (v_i)$$

преследователей, а незанятых вершин оказывается не менее

$$l\stackrel{\bigtriangleup}{=} (n+1) -k - \left(n - \sum_{i=1}^{k} p_{j+1} (v_i)\right)= \sum_{i=1}^{k} p_{j+1} (v_i) - k +1.$$

В силу леммы 2 $l\ge 3$. В момент $j+1$ голых вершин не менее $l-1$ (вершина $u_0$ может оказаться незанятой, но не голой) и, следовательно, в каждой особой вершине в момент $j+1$ не менее $l-1$ преследователей. Как и выше, получаем

$$k(l-1) +n - \sum_{i=1}^{k}p_{j+1}(v_i) \le n,$$

или

$$(k-1)\sum_{i=1}^{k}p_{j+1}(v_i) \le k^2,$$

откуда в силу леммы 2 имеем $k=2$. Из предыдущего неравенства следует также, что

$$p_{j+1} (v_1) + p_{j+1} (v_2) \le 4,$$

$$p_{j+1} (v_1) = p_{j+1} (v_2) = 2, \quad \mbox{ и } \quad l=3.$$

Ранее было отмечено, что в момент $j+1$ голых вершин не менее $l-1=2$. С другой стороны, их не может быть более двух, так как в этом случае в особой вершине было бы более двух преследователей. Отсюда следует, что в момент $j+1$ существуют ровно две голые вершины (обозначим их через $u_1, u_2$). Пусть $A$ - множество всех вершин, отличных от $u_0, v_1$ и $v_2$. В силу леммы 1 каждая из вершин этого множества в момент $j+1$ либо занята, либо является голой. Отсюда следует, что вершины $u_1, u_2 \in A$, в них нет преследователей, а каждая из остальных вершин множества $A$ (которые мы будем обозначать через $w_1, \dots, w_{n-4})$ занята одним преследователем. Вершине $v_1$ инцидентны два загрязненных ребра $(v_1, u_1)$ и $(v_1, u_2)$, остальные же инцидентные ей ребра должны быть очищены. Заметим, что ребро $(v_1 , u_0)$, являющееся очищенным в момент $j+1$, в момент $j+2$ окажется загрязненным, если к этому моменту в вершину $u_0$ не придет преследователь из $v_1$. Все сказанное выше относительно $v_1$ справедливо и для вершины $v_2$. Заметим, что рассматриваемая ситуация может возникнуть лишь для $n\ge 4$.

Покажем теперь, что $a_{j+2}<2$. Предположим сначала, что в этот момент стала особой вершина $u_i$ ($i=0,1,2$) с $m$ очищенными инцидентными ребрами. Если $m=0$, то в $u_i$ должны собраться все преследователи и, следовательно, никакая другая вершина в момент $j+2$ не может стать особой. Если $m=1$, то очищенным ребром, инцидентным $u_i$, может быть лишь $(u_i , v_1)$ или $(u_i , v_2)$ (при переходе преследователя из вершины $w_k$ в $u_i$ ребро $(u_i , w_k)$ оказывается в момент $j+2$ загрязненным). Пусть для определенности очищенным ребром является $(u_i , v_1)$. Оно оказалось очищенным в момент $j+2$ в результате перехода одного преследователя из $v_1$ в $u_i$ (при этом другой преследователь должен остаться в $v_1$). Чтобы вершина $u_i$ могла стать особой в момент $j+2$, все преследователи из вершин $v_2, w_1, \dots, w_{n-4}$ должны к этому моменту перейти в $u_i$. В этом случае $u_i$ также является единственной особой вершиной в момент $j+2$. Осталось рассмотреть случай $m=2$ (из предыдущего ясно, что $m\le 2$). В этом случае вершине $u_0$ в момент $j+2$ инцидентны два очищенных ребра $(u_i , v_1)$ и $(u_i , v_2)$. Чтобы вершина $u_0$ могла стать особой в момент $j+2$, в ней должны собраться $n-2$ преследователей (все, кроме двух, находящихся в вершинах $v_1$ и $v_2$). Нетрудно убедиться, что и в этой ситуации $u_i$ - единственная особая вершина в момент $j+2$.

Предположим теперь, что в момент $j+2$ стала особой одна из вершин $w_1, \dots, w_{n-4}$, скажем, $w_1$. Покажем, что и в этом случае других особых вершин в момент $j+2$ быть не может. Это утверждение очевидно, если преследователь, находящийся в момент $j+1$ в вершине $w_1$, покидает ее. В противном случае будем рассуждать следующим образом. Чтобы вершина $w_1$ стала особой в момент $j+2$, в нее необходимо перевести по крайней мере двух преследователей (``нейтрализовать" загрязненные к моменту $j+2$ ребра $(w_1 , u_0 )$, $(w_1 , u_1 )$ и $(w_1 , u_2 )$). При этом ясно, что преследователи, находящиеся в момент $j+1$ в вершинах $w_2, \dots , w_{n-4}$, для этой цели использованы быть не могут. Поведение же преследователей, находящихся в момент $j+1$ в вершинах $v_1$ и $v_2$, должно быть следующим: для каждого $i=1,2$ по крайней мере один из преследователей, находящихся в $v_i$, должен перейти в $w_1$, причем если переходит ровно один преследователь, то другой должен оставаться в $v_i$. Теперь становится ясным, что вершины $v_1$ и $v_2$ не могут быть особыми в момент $j+2$. То же можно сказать и о вершинах $u_0, u_1,u_2,w_2, \dots, w_{n-4}$.

Итак, если в момент $j+2$ становится особой одна из вершин $u_0, u_1$, $u_2$, $w_2, \dots , w_{n-4}$, то эта особая вершина - единственная. Таким образом, осталось рассмотреть случай, когда в момент $j+2$ могут стать особыми лишь вершины $v_1$ и $v_2$. Покажем, что на самом деле лишь одна из них может стать особой. Предположим противное, и пусть $\alpha_1,\dots, \alpha_m$, $m\ge 1$, - все незанятые вершины в момент $j+2$. Покажем, что каждая из этих вершин - голая (в момент $j+2$). Если $\alpha_i = u_0$, то это утверждение очевидно, поскольку в момент $j+1$ вершина $u_0$ инцидентна загрязненным ребрам $(u_0 , u_1)$ и $(u_0 , u_2)$. В противном случае вершина $\alpha_i$ оказывается голой в момент $j+2$ в силу леммы 1.

Таким образом, в момент $j+2$ в особых вершинах $v_1, v_2$ находится не менее $2m$ преследователей. Для преследователей, стоящих в этот момент в неособых вершинах, остается $(n+1)-2 +m$ вершин, каждая из которых должна быть занята (иначе, незанятых вершин оказывается больше $m$). Отсюда следует, что

$$(n+1) -2 -m \le n -2m$$

и $m=1$.

Итак, если предположить, что особыми (в момент $j+2$) являются обе вершины $v_1$ и $v_2$, то в этот момент в каждой занятой вершине находится ровно один преследователь. Осталось выяснить, каким образом вершина $v_1$, особая в момент $j+1$, осталась особой в момент $j+2$. Это могло произойти лишь следующим образом: два преследователя, находящиеся в момент $j+1$ в вершине $v_1$, перешли в $u_1$ и $u_2$, а в вершину $v_1$ перешел ровно один преследователь из $v_2$ (чтобы в момент $j+2$ ``нейтрализовать" единственное инцидентное $v_1$ загрязненное ребро $(u_0 , v_1 )$). Однако в этом случае нетрудно убедиться, что вершина $v_2$ не может быть особой в момент $j+2$. Получили противоречие.

Таким образом, доказано, что в процессе реализации программы $\Pi$ не может возникнуть более двух особых вершин и, следовательно, эта программа не может быть выигрывающей. $\Box$

Теорема 11.   $\$

(T1)

$S_{\mu}^{0}(T ) = 4$ $\Leftrightarrow$ $\mu \ge 1$.

(T2)

$S_{\mu }^{0}(T )\le 2$ при $\mu \le 1/3$.

Д о к а з а т е л ь с т в о.

(T1). Импликация $\Leftarrow$ является следствием теорем 10 и 3.

$\Rightarrow$: Опишем выигрывающую программу трех преследователей при $\mu <1$. Обозначим через $A,B,C,D$ вершины графа $T$ и через $L$ - цикл
$(A,B,D,C,A)$. Преследователь $P_1$ движется в выбранном направлении по циклу $L$ с постоянной максимальной (единичной) скоростью. Преследователь $P_2$ ($P_3$) движется по ребру $[A,D]$ ($[B,C]$). Действия преследователей синхронизированы следующим образом: $P_1$ встречается с $P_2$ в $A$ и $D$; $P_1$ встречает $P_3$ в $B$ и $C$.

Если убегающий не покидает $L$, то за время $4(1-\mu)^{-1}$ он будет пойман преследователем $P_1$. С другой стороны, учитывая действия игроков $P_2$ и $P_3$, можно убедиться, что покинув цикл $L$, убегающий, уклоняющийся от встречи с этими игроками, должен на $L$ возвратиться. При этом расстояние между ним и преследователем $P_1$ уменьшается.

(T2). Пусть $A,B,C,D$ - вершины $T$. Определим программу, в которой преследователи $P_1$ и $P_2$ движутся с максимальной скоростью по следующим маршрутам:

$$\begin{eqnarray*} P_{1}:& A \mathop{\to}\limits C \mathop{\to}\limits D\mathop{\... ...its _{9} C\mathop{\to}\limits _{10} A\mathop{\to}\limits _{11}B, \end{eqnarray*}$$

где $\xi\mathop{\to}\limits _{i}\eta$ обозначает, что на протяжении $[i-1, i]$ преследователь переходит из $\xi$ в $\eta$ (или стоит, если $\xi = \eta$).

Проверка того, что указанная программа является выигрывающей при $\mu = 1/3$ проста и нами опускается. $\Box$

Теорема 12.   $S_{\mu}^{0}(O) =5$ $\Leftrightarrow$ $\mu \ge 1$.

Д о к а з а т е л ь с т в о.

$\Leftarrow$: Рассмотрим произвольную дискретную программу $\Pi$ четырех преследователей на графе октаэдра $O$. Мы докажем, что при $\mu=1$ эта программа не является выигрывающей.

Поскольку всякая вершина октаэдра смежна всем остальным вершинам, за исключением одной, справедлива следующая лемма.

Лемма 3.   Если $b_i \ge l$, то для всякой вершины $v\in A_{i}$ имеет место $p_{i} (v)\ge l-1$.

Мы покажем, что в программе $\Pi$ все числа $a_i \le 2$, а потому эта программа не может быть выигрывающей.

Очевидно, что $a_0\le 1$. Докажем, что $a_{i-1} \le 2$ влечет $a_i \le 2$. Заметим, что по лемме 2 в момент $i$ имеется не более двух особых вершин. Следовательно, если $a_{i-1}=0$, то $a_i \le 2$.

Предположим, что $a_{i-1} = 1$ и $a_{i} = 3$, т.е. одна особая вершина $u_1$ - старая, а две особые вершины $u_2$, $u_3$ - новые. По лемме 2 в момент $i$ вершины $u_2$, $u_3$ являются 2-особыми, поэтому $u_1$ - 0-особая. Таким образом, $b_i \le 1$. С другой стороны, согласно лемме 1 $b_i =3$ и мы доказали, что $a_{i-1} = 1$ влечет $a_{i} \le 2$.

Рассмотрим последний возможный случай $a_{i-1} =2$. Сначала мы докажем вспомогательное утверждение.

Лемма 4.   Если для некоторого $k$ выполняются условия $a_{k-1} < 2$ и $a_k =2$, то $a_{k+1} <2$.

Д о к а з а т е л ь с т в о   л е м м ы $\ref{lemma4}.$ Если $a_{k-1} =0$, то в момент $k$ имеются две новые 2-особые вершины. В то же время, согласно лемме 1 все остальные вершины голые. Нетрудно убедиться, что такая ситуация не может возникнуть, и для доказательства леммы достаточно рассмотреть случай $a_{k-1} =1$. Для этого случая возможны варианты:

(I)Из двух особых в момент $k$ вершин одна является новой, а вторая старой.

(II)Обе две особые в момент $k$ вершины являются новыми.

Покажем, что первый вариант не может реализоваться. Предположим противное: в момент $k$ имеется одна старая особая вершина $u_1$ и одна новая - $u_2$. Поскольку $p_k (u_2) \ge 2$ (лемма 2), то $b_k\ge 2$ (лемма 1). Из леммы 3 следует, что $p_k (u_1 ) \ge 1$ и, снова используя лемму 1, получаем $b_k \ge 3$. Лемма 3 влечет $p_k (u_1 ) \ge 2$; таким образом, $p_k (u_1) = p_k (u_2 ) = 2$. Но как следует из леммы 1, в возникшей ситуации все остальные вершины обязаны быть голыми, т.е. $b_k = 4$, что противоречит лемме 3.

Нами доказано, что если $a_{k-1} =1$ и $a_k =2$, то должны быть $u_1 \in A_{k-1}\setminus A_k$ и имеются две новые особые вершины $u_2$, $u_3$. По лемме 2 эти вершины являются 2-особыми и $b_k = 3$ (отметим, что $u_1$ не может быть голой). Подобная ситуация может возникнуть, только если вершины $u_2$ и $u_3$ смежны и каждая из них смежна двум голым вершинам. Поскольку $u_2$ и $u_3$ являются 2-особыми и $b_k = 3$, мы заключаем, что ребро $(u_2, u_3)$ очищено. Более того, легко проверяется, что ребра $(u_2 , u_1)$ и $(u_3 , u_1)$ тоже очищены. Таким образом, цикл, порождаемый вершинами $u_1, u_2, u_3$, в момент $k$ очищен и $p_k (u_1) =0$, $p_k (u_2)= p_k (u_3)=2$. Заметим, что такая ситуация осуществима. Но теперь ясно, что любые действия преследователей из данной позиции приводят к случаю $a_{k+1} <2$ и лемма 4 доказана. $\Box$

Из леммы 4 следует, что если $a_{i-1} =2$, то $a_{i-2} <2$ и $a_i <2$. Поэтому мы заключаем, что в программе $\Pi$ все числа $a_i \le 2$ и эта программа не может быть выигрывающей.

Итак, $S_{\mu}^{0}(O) >4$ при $\mu \ge 1$ и по теореме 7 $S_{\mu}^{0}(O) =5$ при $\mu \ge 1$.

$\Rightarrow$: Опишем выигрывающую при $\mu <1$ программу четырех преследователей. Преследователь $P_i$, ${i}\in\{{1},\dots, {4}\}$, движется по циклу $L_i$ длины 3 следующим образом (см. рисунок):

$$\begin{eqnarray*} P_{1}:& u_{2} \to v_{2} \to u_{1} \to u_{2} \to \dots & \\ P_... ...s& \\ P_{4}: & u_{4} \to v_{1} \to u_{1} \to u_{4} \to \dots& . \end{eqnarray*}$$

Если убегающий не покидает цикл $L_i$, то на протяжении $3\lceil(1-\mu)^{-1}\rceil$ он будет пойман преследователем $P_i$ ($\mu <1$). С другой стороны, смена циклов не помогает убегающему уклониться от поимки. В самом деле, если убегающий переходит с цикла $L_i$ на цикл $L_j$ в некоторый момент времени $t$ (такой переход может произойти только в вершине октаэдра), то в момент $t$ он ``равноудален" от преследователей $P_i$ и $P_j$. $\Box$

Теорема 13.   $\$

(C1)

$S_{\mu}^{0}(C) =5$ $\Leftrightarrow$ $\mu \ge 1$.

(C2)

$S_{\mu }^{0}(C )\le 3$ при $\mu < 0.5$.

(C3)

$S_{\mu }^{0}(C )\le 2$ при $\mu \le 0.2$.

Д о к а з а т е л ь с т в о.

(C1) $\Leftarrow$: Покажем, что $S_{1}^{0}(C) =5$. Рассмотрим произвольную дискретную программу поиска четырех преследователей $\Pi$ и докажем, что программа $\Pi$ не может быть выигрывающей при $\mu=1$.

Нетрудно убедиться в справедливости следующей леммы.

Лемма 5.  

a) Если в момент $i$ имеется одна 0-особая вершина,
то $b_i \le 4$.

b) Если в момент $i$ имеется две 0-особые вершины, то $b_i \le 2$.

Для доказательства того, что программа не является выигрывающей, мы покажем, что все числа $a_i \le 3$.

Предположим, что в начальный момент времени все преследователи находятся в одной вершине - единственной особой вершине в данный момент. Докажем, что $a_{i-1} \le 3$ влечет $a_i \le 3$. Отметим, что из леммы 2 следует, что в момент $i$ не более двух особых вершин являются новыми. Поэтому если $a_{i-1}\le 1$, то $a_i \le 3$.

Предположим, что $a_{i-1} =2$, но $a_{i} > 3$. Тогда $a_i =4$. Более того, в момент $i$ две особые вершины $u_1$, $u_2$ - старые и две особые вершины $u_3$, $u_4$ - новые. Поскольку $u_3$, $u_4$ являются 2-особыми в момент $i$, то вершины $u_1$, $u_2$ в этот же момент должны быть 0-особыми. Лемма 1 влечет $b_i \ge 4$; с другой стороны, $b_i \le 2$ (лемма 5). Таким образом, если $a_{i-1} =2$, то $a_{i} \le 3$.

Для изучения случая $a_{i-1} =3$ докажем еще одну лемму.

Лемма 6.   Если для некоторого $k\ge 1$ справедливо $a_{k-1} < 3$ и $a_k =3$, то $a_{k+1} <3$.

Д о к а з а т е л ь с т в о. Если $a_{k-1} =1$, то в момент $k$ множество особых вершин состоит их одной старой вершины $u_1$ и двух новых $u_2$, $u_3$. Из леммы 2 следует, что вершины $u_2$ и $u_3$ являются 2-особыми в момент $k$; следовательно, в этот момент $u_1$ является 0-особой. В силу леммы 1 $b_i \ge 5$, в то же время лемма 5 влечет $b_i \le 4$. Поэтому $a_{k-1} = 2$.

В этом случае возможен один из вариантов:

(I) Из трех особых в момент $k$ вершин две старые и одна новая.

(II) Из трех особых в момент $k$ вершин одна старая и две новые.

Покажем, что вариант (I) невозможен. Предположим, что в момент $k$ особые вершины $u_1$, $u_2$ являются старыми, а вершина $u_3$ новая. По лемме 2 $p_k (u_1)+ p_k (u_2) \le 2$. В этой ситуации возникает четыре случая.

a) $p_k (u_1)= p_k (u_2)=0$. По лемме 5 $b_k \le 2$ и лемма 1 влечет $b_k \ge 3$.

b) $p_k (u_1) =0$, $p_k (u_2)=2$. По лемме 1 $b_k \ge 5$, тогда по лемме 5 $b_k \le 4$.

c) $p_k (u_1) =0$, $p_k (u_2)=1$. В силу лемм 1 и 5 имеем $b_k = 4$. Три вершины куба смежны вершине $u_1$, и $u_1$ не может быть голой. Следовательно, $u_2$ смежна $u_1$. Тогда вершина $u_2$ инцидентна двум загрязненным (в момент $k$) ребрам и не может быть особой.

d) $p_k (u_1)=p_k (u_2)=1$, $p_k (u_3)=2$. В этом случае $b_k =5$. В момент $k$ вершина $u_1$ смежна как минимум двум очищенным ребрам, концы которых не принадлежат $B_k$. А потому $u_1$ смежна $u_2$ и $u_3$. По той же причине $u_2$ смежна $u_1$ и $u_3$. Тогда вершины $u_1$, $u_2$, $u_3$ порождают цикл длины три в $C$, что невозможно.

Мы доказали, что если $a_{k-1} = 2$ и $a_k =3$, то возможен только вариант (II), т.е. существуют вершины $u_0 \in A_{k-1} \setminus A_k$, $u_1 \in A_{k-1} \cap A_k$ и две новых вершины $u_2$, $u_3 \in A_k\setminus A_{k-1}$. По лемме 1 все вершины, за исключением $u_0$,$u_1$,$u_2$ и $u_3$ являются голыми в момент $k$, а потому $b_k = 4$. Также вершины $u_0$,$u_2$,$u_3$ смежны $u_1$. Отметим, что такая ситуация возможна.

Теперь ясно, что всякие действия преследователей в данной позиции приводят к случаю $a_{k+1} <3$ и лемма 6 доказана. $\Box$

Из леммы 6 следует, что если $a_{i-1} =3$, то $a_{i-2} < 3$ и $a_{i} < 3$. Таким образом, для программы $\Pi$ все числа $a_i \le 3$ и $\Pi$ не может быть выигрывающей.

Итак, $S_{\mu}^{0}(C) >4$ при $\mu \ge 1$ и по теореме 6 $S_{\mu}^{0}(C) =5$ при $\mu \ge 1$.

$\Rightarrow$: Предъявим выигрывающую при $\mu <1$ программу четырех преследователей. Каждый из преследователей $P_i$, ${i}\in\{{1},\dots, {4}\}$, движется по циклу $L_i$ длины четыре согласно следующей схеме (см. рисунок):

$$\begin{eqnarray*} P_{1}:& u_{1} \to u_{5} \to u_{6} \to u_{2} \to u_{1}\to \dots... ..._{4}: & u_{3} \to u_{7} \to u_{8} \to u_{4}\to u_{3} \to \dots & \end{eqnarray*}$$

Как и в теореме 12, нетрудно убедиться в том, что за время $4\lceil(1-\mu)^{-1}\rceil$ убегающий будет пойман.

(C2) Обозначим через $u_i$, ${i}\in\{{1},\dots, {8}\}$, вершины графа $C$ (см. рисунок). Определим маршруты преследователей:

$$\begin{eqnarray*} P_{1}:& u_1 \to u_2 \to u_2\to u_3\to u_3\to u_4\to u_4\to u_1... ... u_1 \to u_2\to u_6\to u_7\to u_3\to u_4\to u_8\to u_5 \to u_1 . \end{eqnarray*}$$

Каждый из преследователей проходит по указанному маршруту $\Big\lceil (1-2\mu)^{-1}\Big\rceil$ раз. Легко доказывается, что при $\mu < 0.5$ данная программа будет выигрывающей. В самом деле, преследователи $P_1$ и $P_2$ вынуждают убегающего покинуть ребра циклов $u_1,u_2,u_3,u_4,u_1$ и $u_5,u_6,u_7,u_7,u_5$. Но тогда убегающий ловится игроком $P_3$.

(C3) Обозначим через $u_i$, ${i}\in\{{1},\dots, {8}\}$, вершины графа $C$ (см. рисунок). Определим траектории игроков:

$$\begin{eqnarray*} P_{1}:& u_6 \mathop{\to}\limits u_7 \mathop{\to}\limits u_8 \m... ...2} u_3\mathop{\to}\limits _{23}u_2 \mathop{\to}\limits _{24}u_6. \end{eqnarray*}$$

Доказательство того, что при $\mu=0.2$ программа является выигрывающей, просто и оставляется читателю. $\Box$