Эксперименты по контролю функции выходов инициального автомата

Контроль функции выходов инициального автомата с использованием простого безусловного эксперимента

Известно, что ДУ с памятью, описываемое математической моделью конечного автомата Мили, всегда может быть реализовано в виде, изображенном на рис.6.1. Здесь блок $$C$$ реализует функцию выходов и является комбинационным устройством, а блок $$B$$ представляет собой запоминающее устройство.

(рис 6.1)

В общем случае причинами неисправности ДУ могут быть как неисправности в блоке $$C$$ (блоке $$B$$ ), так и неисправности, возникшие в обоих блоках.

В этой лекции рассматриваются эксперименты, ориентированные на контроль функционирования блока $$C$$, т. е. функции выхода автомата. Мы займемся исследованием этого частного случая экспериментов потому, что для проверки памяти ДУ, т. е. блока $$B$$, разработаны хорошо зарекомендовавшие себя специальные методы. Конечно, для проверки функционирования блока $$C$$ можно применить контрольные эксперименты общего вида, однако в рассмотренной ситуации методы их построения не учитывают ее специфики и будут порождать тесты, длина которых заведомо больше той, которая минимально необходима.

Естественно, что методы контроля зависят от класса рассматриваемых автоматов и применяемых средств. Ниже исследуются методы контроля для инициальных и неинициальных автоматов, а в качестве средств используются простые и кратные безусловные эксперименты. Характерной особенностью всех рассматриваемых здесь задач контроля является их сводимость к построению различных обходов графов автомата, т. е. путей по графу, проходящих через все его дуги.

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

В связи с этим при исследовании рассматриваемых ниже задач будем придерживаться следующей схемы: после постановки задачи контроля она будет сводиться к задаче построения соответствующего обхода графа. Далее в терминах теории графов будут получены условия существования решения, алгоритмы построения решения и оценки длины получаемых обходов.

При решении задач контроля автоматов обычно принимается предположение, что в процессе проведения эксперимента дополнительных неисправностей в автомате не возникает. В рассматриваемых ниже задачах это предположение также остается в силе.

Рассмотрим следующую задачу. Пусть в распоряжении экспериментатора находится один экземпляр автомата Мили $$A$$, у которого известны входной алфавит $$X=\{x_1, \dots, x_m\}$$, выходной алфавит $$Y=\{y_1, \dots, y_l\}$$, множество состояний $$s=\{s_0, s_1, \dots, s_{n-1}\}$$, где $$s_0$$ - выделенное состояние, называемое начальным, и функция переходов $$\delta : S \times X \to S$$. Требуется построить простой безусловный эксперимент, позволяющий распознать функцию выходов $$\lambda$$ автомата $$A$$ или эквивалентного ему автомата.

Умение решать сформулированную задачу позволит решать и задачу контроля функции выходов инициального автомата. В самом деле, если нам удастся распознать функцию выходов $$\lambda'$$ автомата, с которым производится эксперимент, то сравнение ее с функцией $$\lambda$$ автомата $$A$$, играющего роль исправного, позволит сделать вывод об исправности $$\lambda'$$ в исследуемом автомате. Если же изменения, появившиеся в функционировании блока $$\lambda$$, таковы, что исследуемый автомат эквивалентен $$A$$, то естественно игнорировать эти изменения и считать исследуемый автомат исправным. Именно этим мотивируется требование распознаваемости функции выходов с точностью до эквивалентности.

Очевидно, что функция выходов будет распознана, если в результате проведения эксперимента для любого состояния этого автомата будет определена его реакция на любой входной символ.

В соответствии с определением простого безусловного эксперимента его проведение должно включать построение соответствующего входного слова, наблюдение реакции автомата на это входное слово и, наконец, сравнение на основе полученной реакции функции выходов исследуемого автомата с эталоном и вывод заключения об исправности ее.

Контроль функции выходов исследуемого автомата может быть выполнен с помощью так называемого контролирующего автомата, связанного с исследуемым так, как это изображено на рис.6.2, где $$A$$ - исследуемый автомат, $$K$$ - контролирующий автомат.

(рис 6.2)

Автомат $$K$$ фактически реализует второй и третий этап эксперимента. Вопросы синтеза подобных автоматов рассмотрены в ряде работ, например в [3], [29], поэтому мы не будем здесь на них останавливаться, а основное внимание уделим построению входного слова.

Если автомат задан в виде ориентированного графа, у которого начальной является вершина $$s_0$$, то упомянутому входному слову в графе автомата будет соответствовать путь, начинающийся в $$s_0$$ и проходящий через все его дуги. Этот путь будем называть обходом графа. Под путем в графе понимается последовательность дуг, таких, что конечная вершина предыдущей дуги является начальной вершиной следующей. Таким образом, сформулированная нами задача эквивалентна задаче построения обхода автоматного графа.

Под графом $$G(S,U)$$, где $$S,U$$ - множество вершин и дуг графа соответственно, мы будем понимать конечный ориентированный мультиграф. Пусть $$s_0$$ - начальная вершина этого графа. Дугу $$u$$ графа, ведущую из вершины $$s_1$$ в $$s_2$$, для удобства будем иногда обозначать $$(s_1, s_2, u)$$, чтобы явно указать ее начальную и конечную вершины.

Перейдем к определению условий существования обхода графа. Рассмотрим бинарное отношение $$\tau \subset S \times S$$, задаваемое следующим образом: $$(s_1, s_2) \in \tau$$ тогда и только тогда, когда в графе $$G(S,U)$$ существует путь из вершины $$s_1$$ в вершину $$s_2$$. Отношение $$\tau$$ называется отношением достижимости. Используя отношение $$\tau$$, построим бинарное отношение $$\eta \subset S \times S$$ следующим образом:

$$\eta = \tau \cap \tau^{-1}$$

Известно [62], что $$\eta$$ является отношением эквивалентности, а его классы, называемые слоями, являются максимальными сильно связными подмножествами множества $$S$$. Каждому слою $$\sigma$$ графа $$G(S,U)$$ естественным образом ставится в соответствие подграф $$G'(S,U')$$, где $$U'$$ - множество всех дуг из $$U$$, начало и конец которых есть вершины множества $$\sigma$$. Иногда для простоты мы будем отождествлять слой графа с соответствующим ему подграфом, однако каждый раз из контекста будет ясно, о чем именно идет речь.

Следующее утверждение описывает класс графов, у которых существует обход.

Теорема 6.1. Для того чтобы у графа $$G(S,U)$$ существовал обход, необходимо и достаточно, чтобы выполнялись следующие условия:

для любой вершины $$s \in S$$ существует путь, связывающий вершину $$s_0$$ с вершиной $$s$$ ;

в любом слое $$\sigma$$ графа существует не более одной вершины $$s$$, а в графе $$G(S,U)$$ не более одной дуги $$(s,s', u)$$, таких, что $$s' \notin \sigma$$.

Необходимость. Предположим, что путь $$(s_0, s_{i_1}, u_{i_1}) (s_{i_1}, s_{i_2}, u_{i_2}) \dots (s_{i_{k-1}}, s_{i_k}, u_{i_k})$$ является обходом графа $$G(S,U)$$. Справедливость первого условия непосредственно следует из определения обхода графа. Справедливость второго условия докажем от противного. Допустим, что существует слой $$\sigma$$ и две различные дуги $$(s_{i_{\nu}},s_{i_{\nu +1}}, u_{i_{\nu +1}})$$ и $$(s_{i_{\mu}}, s_{i_{\mu +1}}, u_{i_{\mu +1}})$$, такие, что $$s_{i_{\nu +1}} \notin \sigma$$ и $$s_{i_{\mu +1}} \notin \sigma$$. Предположим, что первая из этих дуг входит в обход ранее второй, т. е. обход имеет следующую структуру:

$$p=p_1(s_{i_{\nu}}, s_{i_{\nu +1}}, u_{i_{\nu +1}})p_2(s_{i_{\mu}}, s_{i_{\mu +1}}, u_{i_{\mu +1}})p_3,$$

где $$p_1(i=1,2,3)$$ - некоторые отрезки пути $$p$$.

Рассмотрим множество вершин $$\sigma Y\{s_{i_{\nu +1}}\}$$. Поскольку $$\sigma$$ - сильно связное подмножество, отрезок $$p_1$$ заканчивается в вершине $$s_{i_{\nu}} \in \sigma$$, а отрезок $$p_1(s_{i_{\nu}}, s_{i_{\nu +1}}, u_{i_{\nu +1}})$$ является начальным отрезком обхода $$p$$, то между любой вершиной $$s \in \sigma$$ и вершиной $$s_{i_{\nu +1}} \notin \sigma$$ путь по графу $$G(S,U)$$ существует. Далее, так как отрезок $$(s_{i_{\nu}}, s_{i_{\nu+1}}, u_{I_{\nu +1}})p_2$$ заканчивается в вершине $$s_{i_{\mu}} \in \sigma$$ и $$\sigma$$ - сильно связное подмножество, то между вершиной $$s_{i_{\nu +1}}$$ и любой вершиной $$s \in \sigma$$ по графу $$G(S,U)$$ путь также существует. Отсюда следует, что $$\sigma Y \{s_{i_{\nu +1}}\}$$ есть сильно связное подмножество. Это противоречит нашему предположению о том, что $$\sigma$$ - максимальное сильно связное подмножество. Полученное противоречие и доказывает наше утверждение.

Достаточность. Поскольку рассматриваемый граф $$G(S,U)$$ конечен, то конечным является и число его слоев. Предположим, что это число есть $$N$$.

Пронумеруем слои $$\sigma$$ графа $$G(S,U)$$ следующим образом:

$$\sigma_1$$ - слой, содержащий начальную вершину $$s_0$$ ;

пусть $$i-1$$ слоев $$(i=2, \dots, N-1)$$ уже пронумеровано; слой $$\sigma$$ получает номер $$i$$, если существует такая вершина $$s \in \sigma_{i-1}$$ ( $$\sigma_{i-1}$$ - слой с номером $$i-1$$ ) и такая дуга $$(s,s',u)$$, что $$s' \in \sigma$$ ;

номер $$N$$ получает тот слой $$\sigma$$, все дуги которого ведут в вершины, принадлежащие $$\sigma$$.

Легко показать, что каждому слою графа $$G(S,U)$$, удовлетворяющему условию доказываемой теоремы, в соответствии со сформулированной процедурой будет присвоен единственный номер из диапазона от 1 до $$N$$.

Обозначим через $$s^{(i)}$$ вершину слоя $$\sigma_i$$, из которой выходит дуга $$(s^{(i)}, \tilde {s^{(i)}}, u^{(i)})$$, такая, что $$\tilde {s}^{(i)} \in \sigma_{i+1}$$. В силу второго условия теоремы эта дуга единственна. Рассмотрим подграф $$G(\sigma_i, u_i)$$ графа $$G(S,U)$$, где $$\sigma_i$$ - множество вершин $$i$$ -го слоя, $$u_1$$ - множество всех дуг, начало и конец которых есть вершины множества $$\sigma_i$$. Поскольку этот подграф сильно связен, то у него всегда существует обход $$p_i$$, начинающийся в вершине $$\tilde {s}^{(i-1)}$$ и заканчивающийся в вершине $$s^{(i)} (i=1,2,\dots, N-1)$$. Через $$p_N$$ обозначим обход подграфа $$G(\sigma_N, U_N)$$, начинающийся в вершине $$\tilde {s}^{(N-1)}$$. Условимся считать, что $$\tilde {s}^{(0)}=s^0$$.

Легко видеть, что путь $$p=p_1(s^{(1)}, \tilde {s}^{(1)}, u^{(1)})p_2 p_1(s^{(2)}, \tilde {s}^{(2)}, u^{(2)}) \dots p_1(s^{(N-1)}, \tilde {s}^{(N-1)}, u^{(N-1)})p_N$$ является обходом графа $$G(S,U)$$. Достаточность условий теоремы доказана.

Хотя приведенное доказательство теоремы 6.1 и не является конструктивным, мы не будем здесь останавливаться на методах построения обходов графа в связи с тем, что в теории графов известно много различных методов построения путей между двумя вершинами (в том числе и минимальной длины), которыми можно воспользоваться при конструировании обходов. Покажем теперь, каким образом задача построения обхода графа может быть сведена к задаче построения пути, соединяющего две его выделенные вершины.

По графу $$G(S,U)$$ с начальной вершиной $$s_0$$ построим новый граф $$O(B(U)\times S,U)$$, где $$B(U)$$ - множество всех подмножеств $$U$$. Начальной вершиной графа $$O(B(U) \times S,U)$$ будем считать вершину $$(U, s_0)$$. Положим, что в этом графе из вершины $$(U_{i_1}, s_{i_1})$$ в вершину $$(U_{i_2}, s_{i_2})$$ ведет дуга $$((U, s_{i_1}),(U_{i_2}, s_{i_2}),u)$$, если:

дуга $$(s_{i_1}, S_{i_2},u)$$ графа $$G(S,U)$$ принадлежит $$U_{i_1}$$ ;

$$U_{i_2}=U_{i_1}\\{(s_{i_1}, s_{i_2},u)\}$$, где знаком "\" обозначена теоретико-множественная разность.

Из самой конструкции графа $$O(B(U) \times S,U)$$ легко следует справедливость следующего утверждения.

Лемма 6.1. Путь $$p=(s_0, s_{i_1}, u_{i_1})(s_{i_1}, s_{i_2}, u_{i_2}) \dots (s_{i_{k-1}}, s_{i_k}, s_{i_k})$$ в графе $$G(S,U)$$ является его обходом тогда и только тогда, когда в графе $$O(B(U)\times S,U)$$ существует путь

$$((u, s_0), (u_{i_1}, s_{i_1}'), u_{i_1}') \times ((u_{i_1},s_{i_1}', (u_{i_2}, s_{i_2}'), y_{i_2') \dots ((U_{i_{k-1}}, s_{i_{k-1}}'), (u_{i_k}, s_{i_k}'), u_{i_k}'),$$

такой, что

$$u_{i_k}= \varnothing$$ ;

для любого $$\nu, 1 \le \nu \le k, s_{i_{\nu}}=s_{i_{\nu}}', u_{i_{\nu}}=u_{i_{\nu}}'$$.

Лемма 6.1 по существу дает алгоритмы для решения следующих задач:

Выяснить, существует ли обход для графа $$G(S,U)$$ с начальной вершиной $$s_0$$.

Найти множество всех обходов графа $$G(S,U)$$.

Найти множество всех минимальных по длине обходов графа $$G(S,U)$$.

Эти алгоритмы сводятся к построению по графу $$G(S,U)$$ графа $$O(B(U) \times S,U)$$ и последующему его анализу. Так, первая задача равносильна выяснению существования пути между вершиной $$(u, s_0)$$ и любой вершиной вида $$( \varnothing, s)$$ этого графа, вторая - нахождению всех путей графа $$O(B(U) \times S,U)$$ между упомянутыми вершинами и, наконец, третья - определению всех путей минимальной длины между теми же вершинами.

Перейдем к интерпретации полученных результатов для задачи, сформулированной в начале этой лекции. Сделаем это достаточно подробно, чтобы далее на этом детально не останавливаться.

Легко видеть, что при построении простого безусловного эксперимента для распознавания функции выходов инициального автомата нам достаточно ограничиться рассмотрением автомата без выходов $$A=(S,X, \delta, s_0)$$, а не исходного автомата Мили $$A=(S,X,Y, \delta, \lambda, s_0)$$, ему соответствующего.

Определение 6.1. Слово $$p \in X_e*$$ будем называть характеристическим для автомата $$A=(S,X, \delta, s_0)$$, если для любого состояния $$s \in S$$ и любого входного символа $$x \in X$$ существует начальный отрезок $$q$$ этого слова, такой, что $$p=qxq'$$ и $$\delta (s_0, q)=s$$.

Из этого определения следует, что характеристическое слово автомата в точности соответствует пути по графу этого автомата, начинающемуся в вершине $$s_0$$ и проходящему через все его дуги, т. е. обходу автоматного графа. Таким образом, исходная задача сведена нами к задаче построения характеристического слова для автомата $$A=(S,X, \delta, s_0)$$. Простая переформулировка теоремы 6.1 дает возможность описать класс автоматов, для которых характеристическое слово существует.

Теорема 6.1. Для того чтобы конечный инициальный автомат $$A=(S,X, \delta, s_0)$$ обладал характеристическим словом, необходимо и достаточно, чтобы выполнялись следующие условия:

для любого состояния $$s \in S$$ существует слово $$p \in X_e*$$, такое, что $$\delta (s_0, p)=s$$ ;

для любого слоя $$\sigma$$ существует не более одного состояния $$s \in \sigma$$ и не более одного входного символа $$x \in X$$, таких, что $$\delta (s,x) \notin \sigma$$.

Оценки длины кратчайших обходов и характеристических слов

Граф $$G(S,U)$$ с начальной вершиной $$s_0$$, удовлетворяющий условиям теоремы 6.1, будем называть $$s_0$$ - правильным или просто правильным. Через $$p_{\min}^G$$ обозначим кратчайший обход графа $$G(S,U)$$, а через $$d(p_\min}^G$$ - его длину, т. е. число дуг, входящих в обход.

По определению обход графа $$G(S,U)$$ представляет собой путь, содержащий все дуги из $$U$$. Отсюда следует нижняя оценка длины кратчайшего обхода:

$$d(p_{\min}^g) \ge |U|$$

Возникает вопрос, существуют ли графы, для которых эта оценка достижима, и если да, то как описать такой класс графов. Ответы на эти вопросы даются следующей теоремой.

Теорема 6.2. Для правильного графа $$G(S,U)$$ обход длины $$|U|$$ существует тогда и только тогда, когда выполняется одно из следующих условий:

в каждой вершине графа число исходящих дуг равно числу заходящих;

в начальной вершине $$s_0$$ графа число исходящих дуг на единицу больше числа заходящих, и существует такая вершина $$s$$, в которой число исходящих дуг на единицу меньше числа заходящих; в остальных вершинах графа число исходящих дуг равно числу заходящих.

Справедливость этой теоремы следует из известных результатов теории графов [25]. Очевидно, что путь (контур) в графе длины $$|U|$$, проходящий через все его дуги и только по одному разу, есть не что иное, как эйлеров путь (контур). Условия сформулированной теоремы являются соответственно условиями существования эйлерова контура и пути.

Далее обход графа $$G(S,U)$$, начинающийся в вершине $$a$$ и заканчивающийся в одной из вершин множества $$B$$, будем именовать $$(a,B)$$ -обходом.

$$(s_o, S)$$ -обход, т. е. обход в определенном ранее смысле, будем называть $$s_0$$ -обходом, чтобы отметить его начальную вершину. Если $$B=\{b\}$$, то $$(a, B)$$ -обход будем называть $$(a,b)$$ -обходом.

Для установления верхней оценки длины кратчайших обходов введем несколько определений и докажем ряд вспомогательных утверждений.

Через $$\Delta (s)$$ обозначим разность между числом заходящих и исходящих дуг вершины $$s$$ графа $$G(S,U)$$.

Определение 6.2. Вершину $$s$$ графа $$G(S,U)$$, у которой $$\Delta (s) >0 (\Delta (s)<0)$$ ), назовем положительной (отрицательной).

Через $$S^+ (S^-)$$ обозначим множество всех положительных (отрицательных) вершин графа $$G(S,U)$$.

Определение 6.3. Семейство $$M$$ элементарных путей назовем компенсирующей системой путей графа $$G$$ для $$(a,b)$$ -обхода, если:

каждая положительная (отрицательная) вершина $$s$$, отличная от $$a$$ и $$b$$, является началом $$\Delta (s)$$ (концом $$|\Delta (s)|$$ ) путей из $$M$$, где $$|K|$$ - модуль $$K$$ ;

при $$\Delta (a) \ge 0 (\Delta (a) <0)$$ вершина $$a$$ является началом $$\Delta (a)+ \omega$$ (концом $$|\Delta (a)+ \omega|$$ ) путей из $$M$$, где $$\omega =0$$, если $$a=b$$, и $$\omega = 1$$, если $$a \ne b$$ ;

если $$\Delta (b)>0 (\Delta (b) \le 0)$$ ), то вершина $$b$$ является началом $$\Delta (b) - \omega$$ (концом $$|\Delta (b) - \omega|$$ ) путей из $$M$$, где $$\omega$$ определяется так же, как в пункте 2.

Сумму длины всех путей из $$M$$ назовем длиной компенсирующей системы $$M$$ и обозначим ее через $$D(M)$$.

Через $$(D(a,b)$$ обозначим длину кратчайшего $$(a,b)$$ -обхода графа $$G$$. Легко убедиться, что для правильных графов компенсирующая система всегда существует.

Теорема 6.3. $$D(a,b)=|U|+D(M)$$, где $$M$$ - компенсирующая система минимальной длины для $$(a,b)$$ -обхода графа $$G(S,U)$$.

Доказательство. Каждому пути из $$M$$, ведущему из вершины $$s$$ в вершину $$s'$$, поставим во взаимно однозначное соответствие дугу, соединяющую те же вершины. Пусть множество этих дуг есть $$V=\{\nu_1, \dots, \nu_{|M|}\}$$. Рассмотрим граф $$G(S,UYV)$$, полученный из $$G(S,U)$$ добавлением всех дуг множества $$V$$. Легко видеть, что в графе $$G(S,UYV)$$ существует эйлеров путь $$p$$, ведущий из вершины $$a$$ в вершину $$b$$ (см. теорему параграфа 28 из [25]). Заменив в $$p$$ каждую дугу $$\nu_i$$ соответствующим ему путем из $$M$$, получим новый путь $$p'$$, проходящий только по дугам графа $$G(S,U)$$ и являющийся его $$(a,b)$$ -обходом. Из сказанного следует, что $$D(a,b) \le |U| + D(M)$$. Неравенство $$D(a,b) \ge |U|+D(M)$$ вытекает из того, что $$M$$ - компенсирующая система минимальной длины. Из приведенных неравенств следует справедливость утверждения теоремы.

Будем говорить, что граф $$G(S,U)$$ имеет степень $$m$$, если из каждой его вершины исходит ровно $$m$$ дуг.

Теорема 6.4. Для сильно связного графа $$G(S,U), |S|=n$$ степени $$m$$ и диаметра $$d$$ имеет место неравенство

$$D(a,b) \le mn+ \frac 12 (m-1)(2n-d-1)d+d$$

Доказательство. Поскольку при $$m=1$$ теорема очевидна, то рассмотрим случай $$m>1$$. Число дуг графа $$G$$, т. е. $$|U|$$, равно $$mn$$, но тогда в силу теоремы 6.3 достаточно доказать, что существует компенсирующая система путей $$M$$ графа $$G$$ для $$(a,b)$$ -обхода, длина которой не превосходит величины $$\frac 12 (m-1)(2n-d-1)d+d$$.

Пусть $$s_{i_1}, s_{i_2}, \dots, s_{i_t} (s_{i_1}', s_{i_2}', \dots, s_{i_t}')$$ - неупорядоченная последовательность вершин графа $$G(S,U)$$, таких, которые в соответствии с определением 6.3 являются начальными (конечными) вершинами путей компенсирующей системы $$M$$ графа $$G$$. Факт существования системы $$M$$ для сильно связного графа очевиден.

Если некоторая вершина является началом (концом) $$l$$ путей системы $$M$$, где $$l>1$$, то в последовательности $$s_{i_1}, s_{i_2}, \dots, s_{i_t} (s_{i_1}', s_{i_2}', \dots, s_{i_t}')$$ она встречается $$l$$ раз.

Построение компенсирующей системы путей $$M$$ будем выполнять в виде пошагового процесса.

1-й шаг. Находим кратчайший путь $$\mu_1$$ среди путей, ведущих из вершины $$s_{i_j}$$ в вершину $$s_{i_k}', 1 \le j, k \le t$$. Путь $$\mu_1$$ является первым путем компенсирующей системы $$M$$. Предположим, что $$\mu_1$$ начинается в вершине $$s$$ и заканчивается в вершине $$s'$$. Вычеркиваем $$s$$ и $$s'$$ из соответствующих последовательностей вершин, выписанных выше.

$$(\alpha +1)$$ -й шаг. Пусть уже построены пути $$\mu_1, \mu_2, \dots, \mu_{\alpha}$$ компенсирующей системы $$M$$, где $$\alpha \ge 1$$. Тогда последовательность начальных (конечных) вершин путей системы $$M$$ содержит на данном шаге $$t- \alpha$$ членов. Не теряя общности, можно считать, что такая последовательность начальных (конечных) вершин суть $$s_{i_1}, s_{i_2}, \dots, s_{i_{t-\alpha}} (s_{i_1}', s_{i_2}', \dots, s_{i_{t-\alpha}}')$$. Находим кратчайший путь $$\mu_{\alpha +1}$$ среди путей, ведущих из вершины $$s_{i_j}$$ в вершину $$s_{i_k}', 1 \le j, k \le t-\alpha$$. Пусть $$\mu_{\alpha +1}$$ является $$(\alpha +1)$$ -м путем компенсирующей системы $$M$$.

Построение компенсирующей системы путей $$M$$ заканчивается, когда из последовательности ее начальных (конечных) вершин будут вычеркнуты все элементы. Предположим, что по описанному алгоритму построена компенсирующая система путей $$M$$. Покажем, что при любом $$k, 1 \le k \le d$$, система эта содержит $$r$$ путей длины, не меньшей $$r$$, где $$r \le (n-k)(m-1)+1$$.

Допустим противное. Пусть $$\mu_{l_1}, \dots, \mu_{l_r}$$ - пути системы $$M$$ длины, не меньшей $$k$$, где $$r>(n-k)(m-1)+1$$. Поскольку $$G$$ сильно связен, то каждая вершина из множества $$S^-\\{b\}$$ является концом не более чем для $$m-1$$ путей из $$M$$. Очевидно, что вершина $$b$$ может являться концом не более чем для $$m$$ путей системы $$M$$. Из этого следует, что среди вершин, являющихся конечными для путей $$\mu_{l_1}, \dots, \mu_{l_r}$$ из $$M$$ длины, не меньшей $$k$$, найдется по крайней мере $$n-k+1$$ различных. Тогда, если $$s$$ является начальной вершиной некоторого пути $$\mu_{i_j}, 1 \le j \le r$$, среди конечных вершин путей $$\mu_{j_1}, \dots, \mu_{l_r}$$ найдется вершина $$s'$$, такая, что длина кратчайшего пути из $$s$$ в $$s'$$ не превышает $$k-1$$. Это противоречит нашему предположению.

Обозначим через $$\beta_j$$ число путей длины $$j$$ в компенсирующей системе путей $$M$$ графа $$G(S,U)$$ для $$(a,b)$$ -обхода. Очевидно, что общая длина всех путей из $$M$$ определяется следующим образом:

$$D(M)=\sum_{j=1}^{d}j*\beta_j \le \sum_{k=1}^{d}[(n-k)(m-1)+1]=\frac 12 (m-1)(2n-d-1)d+d$$

Покажем, что оценка (6.2) является достижимой. Рассмотрим граф на рис.6.3.

(рис 6.3)

Из каждой вершины графа выходит $$m$$ дуг с отметками $$1,2, \dots, m$$. Для простоты на этом рисунке кратные дуги заменены одной дугой с кратной отметкой. Легко видеть, что для всех $$n,d (1 \le d \le n-1), m (m \ge n-d+1)$$ и для всех $$b \in \{d, \dots, n-1\}$$ длина кратчайшего $$(0,b)$$ -обхода графа $$G$$ точно равна оценке (6.2).

Теорема 6.5. Пусть $$G(S,U), |S|=n$$, есть сильно связный граф степени $$m >1$$, у которого удалена одна дуга, исходящая из вершины $$b$$. Если после удаления этой дуги граф $$G$$ остался сильно связным и диаметр его равен $$d$$, то для любой вершины $$a$$ этого графа справедливо неравенство

$$D(a,b) \le mn+\frac 12 (m-1)(2n-d-1)d-1$$

Доказательство. При $$m=1$$ сильно связный граф $$G$$ представляет собой следующую конструкцию: из $$i$$ -й вершины дуга ведет в $$(i+1)$$ -ю для $$i=1,2, \dots, n-1$$, а из $$n$$ -й вершины в первую. Очевидно, что удаление любой дуги из $$G$$ превращает его в граф, не являющийся сильно связным. Поэтому мы покажем справедливость оценки (6.3) при $$m>1$$.

Пусть $$G'$$ - сильно связный граф, полученный из $$G$$ удалением одной дуги, исходящей из вершины $$b$$. Добавим к этому графу петлю в ту же вершину. Полученный в результате новый граф обозначим через $$G*$$. Построим компенсирующую систему путей $$M$$ для $$(a,b)$$ -обхода графа $$G*$$ по алгоритму, изложенному при доказательстве теоремы 6.4. Рассуждения, аналогичные приведенным при доказательстве предыдущей теоремы, показывают, что компенсирующая система путей $$M$$ для $$(a,b)$$ -обхода графа $$G*$$ при любом $$k(1 \le k \le d)$$ содержит $$r$$ путей длины, не меньшей $$k$$, причем $$r \le (n-k)(m-1)$$. Отсюда следует, что общая длина $$D(M)$$ путей компенсирующей системы $$M$$ графа $$G*>$$ удовлетворяет неравенству

$$D(M) \le \sum_{k=1}^{d}[(n-k)(m-1)]\frac 12 (m-1)(2n-d-1)d=$$

Тогда длина $$(a,b)$$ -обхода графа $$G*$$ не превосходит величины $$mn+\frac 12 (m-1)(2n-d-1)d$$. Нетрудно убедиться, что среди $$(a,b)$$ -обходов графа $$G*$$, удовлетворяющих оценке (6.3), есть такой, у которого добавленная фиктивная петля является последней в этом обходе, т. е. обход имеет следующую структуру: $$\mu = \mu' u$$, где $$u$$ - дуга фиктивной петли в вершине $$b$$. Отсюда следует, что путь $$\mu'$$ является $$(a,b)$$ -обходом графа $$G'$$, а длина его не превосходит величины $$mn+\frac 12 (m-1)(2n-d-1)d-1$$.

Покажем, что оценка (6.3) является достижимой. С этой целью вновь обратимся к графу, изображенному на рис.6.3. Непосредственным подсчетом легко убедиться, что для всех $$n, d (1 \le d \le +1), m (m \ge n-d+1)$$ и $$b \in \{d, \dots, n-1\}$$, если удалить одну дугу (произвольным образом) рассматриваемого графа, длина $$(0, b)$$ -обхода в точности равна оценке (6.3).

Рассмотрим теперь обход графов, не являющихся сильно связными.

Пусть $$G(S,U)$$ - $$s_0$$ правильный граф, число слоев которого есть $$N$$. Обозначим через $$G_i(S_i, U_i)$$ подграф графа $$G$$, соответствующий его $$i$$ -му слою. Легко видеть, что $$(a,B)$$ -обход графа $$G$$ существует тогда и только тогда, когда $$BI S_N \ne \varnothing$$ и $$G$$ есть $$a$$ -правильный граф.

Пусть $$G(S,U), |S|=n$$, есть граф степени $$m$$, являющийся $$a_1$$ -правильным. Предположим, что $$G_i(S_i, U_i)$$ - слои графа $$G, i=1, \dots, N$$, которые занумерованы в соответствии с процедурой нумерации, описанной в разделе 6.1. Условимся считать, что $$|S_i|=n_i$$, а диаметр $$G_i$$ есть $$d_i$$. Пусть $$u_i$$ - дуга, ведущая из вершины $$b_i \in S_i$$ в вершину $$a_{i+1} \in S_{i+1}$$. Через $$O_G(a,b)$$ обозначим $$(a,b)$$ -обход графа $$G$$. Очевидно, что $$O_G(a_1, b_N)=O_{G_1}(a_1, b_1)u_iO_{G_2}(a_2, b_2) \dots u_{k-1}O_{G_N}(a_n, b_N))$$. Из этого, а также теорем 6.3 и 6.5 вытекает справедливость следующего утверждения.

Теорема 6.6.

$$D(a_1, b_N)=|U|+\sum_{i=1}^{N}D(M_i)$$

где $$M_i$$ - компенсирующая система путей минимальной длины графа $$G_i$$ для $$(a_i, b_i)$$ -обхода.

Следствие 1. Длина кратчайшего $$(a_1, a_N)$$ -обхода (следовательно, и $$a_1$$ -обхода) графа $$G$$ не превосходит величины

$$mn+\frac 12 (m-1) \sum_{i=1}^{N} (2n_i-d_i-1)d_i$$

Доказательство. В силу теоремы 6.4 достаточно доказать, что для каждого из графов $$G_i$$, у которого удалена дуга, ведущая из вершины $$b_i$$ в вершину $$a_{i+1}$$ графа $$G_{i+1} (i=1,2, \dots, N-1)$$, существует компенсирующая система путей $$M_i$$ для $$(a_1, b_i)$$ -обхода, а для графа $$G_N$$ - система $$M_N$$ для $$(a_N, a_N)$$ -обхода, для которых справедливо неравенство

$$\sum_{i=1}^N D(M_i) \le \frac 12 (m-1) \sum_{i=1}^N(2n_i-d_i-1)d_i$$

Методом, аналогичным использованному в доказательстве теоремы 6.5, можно показать, что длина компенсирующей системы путей графа $$G_N$$ для $$(a_N, a_N)$$ -обхода не превышает величины

$$\frac 12 (m-1)(2n_N-d_N-1)d_N$$

Длина компенсирующей системы путей $$M_i$$ для $$(a_i, b_i)$$ -обхода графа $$G_I (i=1,2,\dots, N-1)$$ с одной удаленной дугой, ведущей из $$b_i$$ в $$a_{i+1} \in S_{i+1}$$, в силу оценки (3.3) удовлетворяет неравенству

$$D(M_i) \le \frac 12 (m-1)(2n_i-d_i-1)d_i-1$$

Отсюда следует, что

$$D(a_1, a_N) \le mn+ \frac 12 \sum_{i=1}^{N_1}[(m-1)(2n_i-d_i-1)d_i-1]+\\ +\frac 12 (m-1)(2n_N-d_N-1)d_N+(N-1)=mn+\frac 12 (m-1) \sum_{i=1}^{N}(2n_i-d_i-1)d_i$$

Замечание. На основании (6.5) получаем, что длина $$(a,a)$$ -обхода $$n$$ -вершинного сильно связного графа степени $$m$$ удовлетворяет неравенству

$$D(a,a) \le mn+ \frac 12 (m-1)(2n-d-1)d$$

Известно, что диаметр $$n$$ -вершинного графа не превосходит величины $$n-1$$. Заменяя в (3.6) $$d$$ на $$n-1$$, получаем

$$D(a,a) \le \frac 12 (m-1)(n-1)n$$

Таким образом, оценка (6.7), установленная в работе [36] , следует из оценки (6.6).

Следствие 2. Если в графе $$G(S,U), |S|=n$$, степени $$m$$ $$(a,b)$$ -обход существует, то длина кратчайшего $$(a,b)$$ -обхода не превосходит величины

$$mn+ \frac 12 (m-1) \sum_{i=1}^N(2n_i-d_i-1) d_i+d_N$$

Это следствие непосредственно вытекает из теорем 6.5 и 6.6.

Легко показать, что оценки (6.4) и (6.8) достижимы. Для этого достаточно построить граф $$H$$, слой $$H_i$$ которого есть подграф, изображенный на рис.6.3. В каждом из этих подграфов произведем следующие изменения: дугу $$i$$ -го подграфа $$(1 \le I \le N-1)$$, исходящую из вершины с номером $$n_i-1$$ с отметкой $$m$$, заменим дугой с той же отметкой и исходящей из той же вершины, но заходящей в вершину с номером 0 $$(i+1)$$ -го подграфа. Непосредственным подсчетом можно убедиться, что оценки (6.4) и (6.8) для графа $$H$$ достижимы.

Из полученных результатов следует, что точная нижняя оценка длины кратчайших характеристических слов автомата есть оценка (6.1), а точные верхние оценки следующие: для сильно связного автомата - (6,2) и (6.7), для остальных - (6.8).

Вопросы и упражнения

Приведите постановку задачи контроля функции выходов инициального автомата.

Приведите критерий существования обхода графа и его доказательство.

Дайте определение характеристического слова автомата.

Каков критерий существования характеристического слова автомата?

Каковы условия существования обхода графа минимально возможной длины?

Что представляет собой компенсирующая система путей графа ?

Приведите верхние оценки различных типов обходов. Какие из этих оценок являются достижимыми?