Теория экспериментов с конечными автоматами

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

Разбить на страницы
Показывать лекцию целиком

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

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

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

Определение 8.1. Множество $$P$$ путей в графе $$G(S,U)$$, исходящих из начальной вершины $$s_0$$ этого графа, назовем покрытием, если каждая дуга $$G(S,U)$$ принадлежит некоторому пути из $$P$$.

Определение 8.2. Число путей покрытия назовем его кратностью, а сумму длин всех путей покрытия - его длиной.

Перейдем к рассмотрению задачи построения покрытия графа $$G(S,U)$$ с начальной вершиной $$s_0$$.

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

Условимся считать, что из каждой вершины $$s$$ графа $$G$$ исходит "пустой" путь нулевой длины, заканчивающийся в той же вершине. Будем говорить, что вершина $$s$$ графа $$G$$ достижима из вершины $$t$$, если в $$G$$ существует путь из вершины $$t$$ в вершину $$s$$. Из этого определения следует, что каждая вершина графа достижима из самой себя. Полагаем, что каждой вершине графа $$G$$ инцидентна хотя бы одна дуга. Обозначим через $$T$$ множество всех тех вершин графа $$G$$, из которых исходит хотя бы одна дуга.

Теорема 8.1. Покрытие графа $$G$$ существует тогда и только тогда, когда любая вершина множества $$T$$ достижима из начальной.

Доказательство. Пусть $$P$$ - некоторое покрытие графа $$G$$ и $$s$$ - некоторая вершина из $$T$$. Поскольку из вершины $$s$$ исходит некоторая дуга и эта дуга принадлежит одному из путей покрытия, то вершина $$s$$ достижима из $$s_0$$. Вершина $$s_0$$ достижима из самой себя по крайней мере по "пустому" пути. Отсюда следует, что любая вершина множества $$T$$ достижима из $$s_0$$. Предположим теперь, что в графе $$G$$ любая вершина $$s \in T$$ достижима из $$s_0$$. Зафиксируем произвольно некоторую вершину $$t \in T$$. Пусть $$u_1, u_2, \dots, u_{k_t}$$ - путь, ведущий из $$s_o$$ в $$t$$, а $$\{\nu_1, \dots, \nu_{r_t)}\}$$ - множество всех дуг, исходящих из $$t$$. Построим множество путей $$P_t=\{u_{1u2} \dots u_{k_t} \nu_1, \dots, u_{1u2} \dots u_{k_t} \nu_r\}$$. Легко видеть, что объединение множеств $$P_t$$ по всем $$t \in T$$ является покрытием графа $$G$$. Этим и заканчивается доказательство теоремы.

Граф, для которого существует покрытие, назовем правильным. Граф $$H(S,V)$$ назовем сверхграфом графа $$G(S,U)$$, если $$V \supseteq U$$. Сверхграф $$H$$ графа $$G$$ назовем регулярным, если любая дуга из множества $$V\U$$ оканчивается в вершине $$s_0$$. Дуги этого множества будем называть замыкающими.

Лемма 8.1. Каждому контуру $$C$$ регулярного сверхграфа $$H$$ графа $$G$$, проходящему через все дуги графа $$H$$, соответствует покрытие графа $$G$$.

Доказательство. Пусть $$C$$ - контур, проходящий через все дуги регулярного сверхграфа $$H$$. По этому контуру строим множество $$P$$ всех максимальных по длине путей, входящих в $$C$$, но не содержащих замыкающих дуг. Поскольку каждая замыкающая дуга оканчивается в $$s_0$$, то путь из $$P$$ начинается в $$s_0$$. Множество $$P$$ получено из контура $$C$$ исключением только всех замыкающих дуг. Отсюда следует, что любая дуга графа $$G$$ входит хотя бы в один путь из $$P$$, т. е. есть покрытие.

Лемма 8.2. Каждому покрытию графа $$G$$ соответствует регулярный сильно связный сверхграф $$H$$ графа $$G$$ и контур $$C$$, проходящий через все дуги $$H$$.

Доказательство. Пусть $$P=\{p_1 \dots, p_k\}$$ - покрытие графа $$G$$. По этому покрытию и графу $$G$$ построим граф $$H$$ следующим образом: если путь $$p_i \in P$$ оканчивается в вершине $$s$$, то проведем из $$s$$ в $$s_0$$ замыкающую дугу $$r_t$$. Поскольку $$G$$ - правильный граф, то полученный граф $$H(S,V)$$, где $$V+UY\{r_i, \dots, r_k\}$$, является сильно связным регулярным сверхграфом графа $$G$$, а путь $$p_{1r_1p_2r2} \dots p_kr_k$$ - контуром, проходящим через все дуги графа $$H$$.

Определение 8.3. Покрытие $$P=\p_1, \dots, p_k\}$$ графа $$G$$ назовем приведенным, если выполняются следующие условия:

  • для всех $$i \ne j, 1 \le i, j \le k$$, путь $$p_i$$ не является начальным отрезком пути $$p_j$$ ;
  • для всякого $$q$$, являющегося начальным отрезком пути $$p_i, q \ne p_i, i=1, \dots, k$$, множество $$P'=\{p_1, \dots, p_{i-1}, q, p_{i+1}, \dots, p_k\}$$ не является покрытием.
    •

    Пусть $$P$$ - приведенное покрытие графа $$G$$. Из пункта 2 определения 8.3 следует, что если $$p \in P$$ и $$p$$ оканчивается дугой $$u$$, то эта дуга не принадлежит никакому другому пути из $$P$$. Из последнего факта непосредственно вытекает, что для правильного графа $$G$$ всегда существует приведенное покрытие, кратность которого не превосходит числа дуг графа. Легко видеть, что эта оценка достижима для графов с любым числом дуг и вершин. Из определения 8.3 также следует, что покрытие минимальной длины является приведенным.

    Если граф сильно связен, то всегда существует контур, проходящий через все его дуги, т. е. всегда существует приведенное покрытие этого графа кратности 1.

    Рассмотрим теперь не сильно связный граф. Докажем ряд вспомогательных утверждений. Используемые обозначения те же, что и в лекции 6 ч. I.

    Лемма 8.3. Для правильного не сильно связного графа множество положительных вершин не пусто.

    Доказательство. Пусть $$G$$ - некоторый правильный не сильно связный граф, у которого $$S^+$$ пусто. Тогда множество $$S^-$$ также пусто и, следовательно, $$\Delta (s)=0$$ для всех $$s \in S$$. Поскольку правильный граф связен, то из последнего факта следует, что граф $$G$$ обладает эйлеровым контуром и, стало быть, он сильно связен. Полученное противоречие доказывает лемму.

    Лемма 8.4. Из любой вершины связного графа, у которого $$S^+$$ не пусто, достижима хотя бы одна положительная вершина.

    Доказательство. Пусть $$F(S,U)$$ - связный граф, у которого $$S^+$$ не пусто. Из каждой вершины $$s \in S^+$$ проведем ровно $$\Delta (s)$$ дуг, оканчивающихся в отрицательных вершинах, таким образом, чтобы каждая отрицательная вершина $$t$$ служила концом ровно $$\Delta (t)$$ таких дуг.

    В результате получим новый граф $$F'(S,U)$$, у которого $$V \supseteq U$$ и для всех вершин $$s \Delta (s)=0$$. В силу теоремы 2 из [25, c.182], граф $$F'$$ обладает эйлеровым контуром $$C$$.

    Рассмотрим отрезок этого контура, лежащий между двумя дугами из множества $$V\U$$. Этот отрезок является, очевидно, путем, ведущим из некоторой отрицательной вершины графа $$F$$ в некоторую положительную вершину. По построению графа $$F'$$ в каждую отрицательную вершину графа $$F$$ входит хотя бы одна дуга из $$V\U$$. Следовательно, из каждой отрицательной вершины графа $$F$$ достижима некоторая положительная.

    Любая положительная вершина достижима из самой себя по "пустому" пути. Рассмотрим, наконец, произвольную вершину $$s$$, у которой $$\Delta (s)=0$$. Из нее достижима положительная вершина, поскольку из $$s$$ выходит по крайней мере одна дуга и эта дуга содержится в пути, порожденном контуром $$C$$, из отрицательной в положительную вершину. Лемма доказана.

    Рассмотрим граф $$G$$, множество $$S^+$$ которого не пусто. Из каждой вершины $$s \in S'$$, где $$S' \subseteq S^+$$, проведем в вершину $$s_0$$ ровно $$\Delta (s)$$ дуг. Эти дополнительные дуги обозначим через $$r_i, \dots , r_k$$, где $$k=\sum_{s \in S} \Delta (s)$$. Полученный граф обозначим через $$H(G,S')$$.

    Теорема 8.2. Для правильного не сильно связного графа $$G$$ всегда существует покрытие, кратность которого не превосходит величины

    $$\sum_{s \in S^+} \Delta (s)$$

    Доказательство. В силу леммы 8.3 множество $$S^+$$ для правильного не сильно связного графа $$G$$ не пусто. Из теоремы 8.1 следует, что граф $$G$$ связен. Построим граф $$H(G,S^+$$. В силу леммы 8.4 и правильности графа $$G$$ граф $$H(G,S^+)$$ является сильно связным регулярным сверхграфом. Зафиксируем некоторый контур $$C$$ графа $$H(G,S^+)$$, проходящий через все его дуги. По лемме 8.1 этому контуру соответствует покрытие $$P$$, содержащее пути, полученные из $$C$$ исключением всех замыкающих дуг $$r_1, \dots , r_k$$ графа $$H(G,S^+)$$. Из правила построения этого графа следует, что между любыми двумя вхождениями замыкающих дуг в контуре $$C$$ имеется хотя бы одна дуга графа $$G$$. Для завершения доказательства теоремы достаточно показать, что в графе $$H(G,S^+)$$ существует такой контур $$C'$$, проходящий через все дуги этого графа, что каждая дуга $$r_t$$ входит в этот контур только один раз. По построению в графе $$H(G,S^+)$$ для каждой вершины $$s \in S^+ \Delta (s)=0$$ и положительной может быть только вершина $$s_0$$. Поскольку из $$s_0$$ достижима любая вершина графа, то всегда можно построить компенсирующую систему графа $$H(G,S^+)$$, используя только дуги из $$U$$. Следовательно, искомый контур $$C'$$ существует. По лемме 8.1 ему соответствует покрытие кратности (8.1), что и требовалось доказать.

    Легко видеть, что оценка (8.1) достижима для всех ее значений.

    Оценим снизу кратность покрытия правильного графа $$G$$. Напомним, что множество $$S\T$$ состоит из вершин графа $$G$$, из которых не выходят дуги. По ранее сделанному предположению любая вершина графа $$G$$ инцидентна хотя бы одной дуге, но тогда $$S\T \subseteq S^+$$. Пусть мощность множества $$S\T$$ равна $$r$$. По лемме 8.2 всякому покрытию графа $$G$$ соответствует некоторый регулярный сильно связный сверхграф $$H$$ графа $$G$$, число замыкающих дуг которого не меньше $$r$$. Отсюда следует, что кратность любого покрытия графа $$G$$ не может быть меньше величины $$r$$. Легко видеть, что эта оценка достижима для всех значений $$r$$.

    Перейдем к уточнению нижней оценки кратности. Множество $$R^+$$ вершин графа $$G$$ определим следующим образом: $$s \in R^+$$, если $$s \in S^+$$ и из вершины $$s$$ не достижима ни одна отрицательная вершина графа $$G$$. Очевидно, что $$S\T \subseteq S^+$$ и для правильного графа $$s_0 \ne R^+$$. Кроме того, для правильного не сильно связного графа $$G$$ множество $$R^+$$ не пусто. Доказательство этого утверждения может быть проведено по аналогии с доказательством леммы 8.3.

    Покажем справедливость следующего утверждения.

    Теорема 8.3. Кратность покрытия правильного графа не может быть меньше величины

    $$\sum _{s \in R^+} \Delta (s)$$

    Доказательство. Пусть $$P=\{p_1, \dots, p_k\}$$ - некоторое покрытие графа $$G$$. По этому покрытию, используя доказательство леммы 8.3, построим сильно связный регулярный сверхграф $$H$$ графа $$G$$. Пусть $$C$$ - контур графа $$H$$, соответствующий покрытию $$P$$. Каждую дугу графа $$H$$ заменим дугами $$l$$ с тем же началом и концом, где $$l$$ - число вхождений дуги в контур. Полученный в результате граф $$H'$$ обладает эйлеровым контуром. Поскольку для любой вершины $$s$$ графа $$H'* \Delta (s)=0$$, то в вершину $$s_0$$ заходит не менее $$\sum_{s \in R^+} \Delta (s)$$ замыкающих дуг. Таким образом, кратность покрытия графа $$G$$ не может быть меньше величины (8.2).

    Рассмотрим граф, изображенный на рис.8.1. Для этого графа $$S^+=\{s_3, s_7, s_8\}, S\T=\{s_8\}, R^+=\{s_7, s_8\}, \sum_{s \in S^+} \Delta (s)=3, \sum_{s \in S^+} \Delta (s)=2$$.

    (рис 8.1)

    Множество $$P=\{u_1u_3u_5u_6u_8u_{10}, u_2u_4u_5u_7u_9\}$$ является, очевидно, приведенным покрытием кратности 2, т. е. оценка (8.2) в данном примере достижима. Нетрудно показать, что (8.2) является достижимой для любого своего значения.

    Следствие 1. Если для правильного не сильно связного графа $$G$$ множества $$R^+$$ и $$S^+$$ совпадают, то минимальная кратность покрытия графа $$G$$ равна величине (8.1).

    Справедливость этого утверждения вытекает непосредственно из теорем 8.2, 8.3 и того факта, что при совпадении множеств $$S^+$$ и $$R^+$$ оценки (8.1) и (8.2) равны.

    Определение 8.4. Приведенное покрытие графа, являющееся минимальным по кратности и по длине, назовем минимальным.

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

    (рис 8.2)

    Покрытия $$P_1=\{u_1u_2u_3u_4u_5u_6u_8, u_1u_2u_7u_6u_8u_9\}$$ и $$P_2=\{u_1u_2u_3u_4u_5u_6u_8u_9, u_1u_2u_7\}$$, как легко видеть, являются приведенными покрытиями этого графа. Покрытие $$P_1$$ является минимальным по кратности (кратность его равна 1), но не минимальным по длине (длина его равна 13). Покрытие $$P_2$$ (длины 11 и кратности 2) является минимальным по длине, но не минимальным по кратности. Легко установить, что для данного графа минимального покрытия не существует.

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

    Лемма 8.5. Если $$P$$ есть покрытие графа $$G$$ минимальной длины, то любой путь из $$P$$, не оканчивающийся в начальной вершине графа, оканчивается в некоторой положительной его вершине.

    Доказательство. Пусть $$P$$ - покрытие графа $$G(S,U)$$ минимальной длины $$l$$. Предположим, что существует путь $$p \in P$$, оканчивающийся в некоторой не положительной вершине $$w$$, где $$w \ne s_0$$. Покрытию $$P$$ соответствует регулярный сильно связный сверхграф $$H$$, способ построения которого описан при доказательстве леммы 8.3.

    Преобразуем граф $$H$$ следующим образом: каждую дугу $$u \in U$$ заменим $$f$$ дугами $$u(1), \dots, u(f)$$ с тем же началом и концом, где $$f$$ - число путей из $$P$$, содержащих дугу $$u$$. Легко видеть, что полученный в результате граф $$H'$$ обладает эйлеровым контуром. Поскольку $$w$$ не обладает положительной вершиной графа $$G$$ и $$w \ne s_0$$, то в графе $$H$$ эта вершина отрицательна, а в графе $$H'$$, очевидно, $$\Delta (w)=0$$. Отсюда следует, что найдется такая дуга $$u_1 \in U$$, оканчивающаяся в вершине $$w$$, что в графе $$H'$$ существуют дуги $$u_1(1), \dots, u_1(f)$$, где $$f \ge 2$$. Выполним следующее преобразование графа $$H'$$: исключим из него дугу $$u_1(f)$$ и одну замыкающую дугу, исходящую из $$w$$. Далее, из начальной вершины дуги $$u_1(f)$$, если она отлична от $$s_0$$, проводим одну замыкающую дугу в $$s_0$$. Полученный в результате такого преобразования новый граф $$H*$$, как это следует из его построения, обладает эйлеровым контуром.

    Число дуг графа $$H*$$ по крайней мере на единицу меньше числа дуг графа $$H'$$. Любому эйлерову контуру графа $$H'$$ соответствует покрытие $$P*$$ графа $$G$$ длины, не большей $$l-1$$. Отсюда следует, что $$P$$ не является покрытием минимальной длины. Полученное противоречие доказывает лемму.

    Сформулируем достаточное условие существования у графа минимального покрытия.

    Теорема 8.4. Если у правильного графа множества $$S^+$$ и $$R^+$$ совпадают, то у него существует мимнимальное покрытие.

    Доказательство. Если у правильного графа $$G$$ множество $$S^+$$ пусто, то он обладает эйлеровым контуром. Очевидно, что эйлеров контур является минимальным покрытием графа.

    Предположим теперь, что множество $$S^+$$ не пусто, следовательно, $$S^-$$ также не пусто. Поскольку $$S^+=R^+$$, а множество $$R^+$$ состоит из вершин, из которых не достижима ни одна отрицательная вершина, то граф $$G$$ заведомо не является сильно связным. В силу следствия 1 теоремы 8.3 минимальная кратность покрытия графа $$G$$ в таком случае равна (8.2).

    Пусть $$P$$ есть покрытие графа $$G$$ минимальной длины $$d$$ и каждый путь из $$P$$ оканчивается в вершине, не равной $$s_0$$. Тогда по лемме 8.5 каждый путь из $$P$$ оканчивается в вершине множества $$R^+$$. Предположим, что $$P$$ не минимально по кратности, т. е. его кратность $$k$$ больше (8.1). Пусть покрытию $$P$$ соответствует сильно связный регулярный граф $$H$$ (см. доказательство леммы 8.2). По графу $$H$$ построим эйлеров граф $$H'$$, заменяя каждую дугу $$u \in U$$ столькими дугами (с тем же началом и концом), скольким путям из $$P$$ принадлежит дуга $$u$$. Поскольку $$k$$ больше (8.1), то найдется вершина $$t \in S_+$$, из которой в графе $$H$$ выходит $$l$$ замыкающих дуг, где $$l>\Delta (t)$$. Следовательно, в графе $$H$$ найдется дуга $$\nu \in U$$, входящая в вершину $$t$$ и принадлежащая по крайней мере двум путям из $$P$$. Тогда в графе $$H'$$ удалим одну дугу $$\nu'$$, соответствующую дуге $$\nu$$, и удалим одну замыкающую дугу, исходящую из $$t$$. Затем из начала дуги $$\nu'$$ в вершину $$s_0$$ проведем одну дугу. Легко видеть, что полученный граф $$H*$$ является эйлеровым и его эйлерову контуру соответствует покрытие графа $$G$$ длины $$d-1$$. Следовательно, $$P$$ не является покрытием минимальной длины. Противоречие доказывает, что $$P$$ - минимально еопкрытие.

    Рассмотрим, наконец, минимальное по длине покрытие $$P=\{p_1, \dots, p_k\}$$ графа $$G$$, у которого некоторые пути оканчиваются в $$s_0$$. Пусть кратность покрытия $$P$$ больше (8.1) и пути $$p_1, \dots, p_l$$ оканчиваются в $$s_0$$. Легко видеть, что покрытие $$P'=\{p_{1p2} \dots p_{l+1}p_{l+2}, \dots, p_k\}$$ также является покрытием минимальной длины и все пути из $$P'$$ оканчиваются только в положительных вершинах. Выше было показано, что кратность покрытия $$P'$$ минимальна. Теорема доказана.

    Перейдем к описанию алгоритма построения покрытия правильного графа $$G$$. Пути искомого покрытия обозначим через $$p_i$$. Каждой вершине $$s \in T$$ поставим в соответствие множество $$U_s^0$$ всех дуг, выходящих из $$s$$. Дуги в $$U_s^0$$ занумеруем числами $$1,2, \dots$$ причем если $$u_i, u_j \in U_s^0$$ и $$u_i$$ - петля, то $$i<j$$.

    В алгоритме будут использованы функции $$\varphi$$ и $$\delta$$, определяемые такими соотношениями: $$\varphi (u)$$ - номер дуги $$u$$ во множестве $$U_s^0, \delta(s,p)$$ - конечная вершина пути $$p$$, исходящего из вершины $$s$$.

    В описанном алгоритме кроме построения покрытия производится вычисление параметра $$j$$, необходимого для оценки длины полученного покрытия.

    Для краткости при описании алгоритма используем операцию присваивания ":=", употребляемую в том же смысле, что и в алгоритмических языках.

    Алгоритм А.

  • $$P:= \varnothing, i:=1, p_i:=e, s:=s_0, j=0$$ ; для всех $$s \in T:U_s:=U_s^0$$.
  • Если $$U_s \ne \varnothing$$, то перейти к пункту 3, иначе к пункту 4.
  • $$p_i=p_iu$$, где $$u$$ - дуга из множества $$U_s$$, имеющая наименьший номер; $$U_s:=U_s\ \{u\}, s:=\delta (s,u)$$ ; если $$\varphi (u) \ne 1$$, то $$j:=j+1$$ ; перейти к пункту 2.
  • Если $$Y_{s \in S} U_s \ne \varnothing$$ то перейти к пункту 5, иначе работа алгоритма завершается.
  • Если из вершины $$s$$ достижима хотя бы одна вершина $$t$$, для которой $$U_t \ne \varnothing$$, то перейти к пункту 6, иначе к пункту 7.
  • Построить кратчайший путь $$q_j$$, ведущий из вершины $$s$$ в вершину из множества $$\{t|U_t \ne \varnothing \}, p_i:=p_iQ_j$$, и перейти к пункту 3.
  • $$s:=s_0; P:=PY\{p_i\}; i:=i+1; p_i:=e$$ и перейти к пункту 3.
    •

    Заметим, что в случае сильно связного графа полученное по этому алгоритму покрытие имеет кратность 1.

    Оценим сверху длину покрытия, построенного с помощью алгоритма $$A$$. Пусть $$m_s$$ - мощность множества $$U_s, s \in T$$. Множество $$\{m_s\}_{s \in T}$$ упорядочим отношением " $$\le$$ " и обозначим через $$(m_1, \dots , m_s)$$, где $$m_i \le m_j$$, если $$i <j$$.

    Алгоритм $$A$$ можно считать пошаговым процессом, где $$j$$ -м шагом будут являться построения, выполняемые алгоритмом при фиксированном значении параметра $$j$$. Путь $$q_j$$, описанный в пункте 6 алгоритма $$A$$, будем называть транслирующим. Очевидно, что длина покрытия, построенного по алгоритму, равна сумме числа дуг графа и длин всех транслирующих путей.

    Оценим суммарную длину всех транслирующих путей покрытия, построенного по алгоритму $$A$$.

    Из описанного алгоритма следует, что длина транслирующего пути $$q_j$$ не превосходит числа таких вершин $$s$$ из $$T$$, для которых на $$j$$ -м шаге $$U_s= \varnothing$$. Поэтому для значений $$j$$ от 0 до $$m_1-1$$ включительно $$q_j=e$$, где $$e$$ - "пустой" путь. Далее, для значений $$j$$ от $$m_1$$ до $$m_2-1$$ включительно длина $$q_j$$ не превосходит единицы. Из описания алгоритма следует, что на последнем шаге работы алгоритма значение $$j$$ равно $$\sum_{i=1}^f(m_i-1)$$. Отсюда, учитывая предыдущие рассуждения, легко показать, что суммарная длина транслирующих путей, построенных по алгоритму, не превосходит величины

    $$Q=\sum_{i=1}^{f}(i-1)(m_i-1)$$

    Следовательно, справедливо следующее утверждение.

    Теорема 8.5. Для правильного графа $$G$$ всегда существует покрытие, длина которого не превышает величины

    $$W+Q$$

    где $$W$$ - число дуг графа.

    Следствие 1. Для правильного $$n$$ -вершинного автоматного графа степени $$m$$ всегда существует покрытие длины, не превышающей величины

    $$mn+\frac 12 (m-1)n(n-1)$$

    Следствие непосредственно вытекает из теоремы 8.5, так как для автоматного графа $$W=mn$$ и $$Q=\frac 12 (m-1)n(n-1)$$.

    В [16] доказано, что для всех $$n$$ и $$m$$ существует $$n$$ -вершинный сильно связный автоматный граф степени $$m$$, у которого имеется контур, проходящий через все дуги графа, минимальной длины, равной (8.5). Из этого факта следует, что оценка (8.5) достижима при всех $$n$$ и $$m$$. Следовательно, оценки (8.4) и (8.3) также достижимы.

    Перейдем теперь к автоматной интерпретации полученных результатов. Если автомат Мили задан в виде конечного ориентированного автоматного графа, то каждому пути покрытия графа ставится в соответствие некоторое входное слово, а множество слов, соответствующих всем путям покрытия, составит кратный безусловный эксперимент. Таким образом, для распознавания функции выходов заданного инициального автомата или ему эквивалентного с $$n$$ состояниями и $$m$$ входными сигналами может быть использован кратный эксперимент , длина которого не превышает величины (8.5), а кратность - величины (8.2). Необходимое и достаточное условие существования кратного эксперимента, а также алгоритм его построения получаются простой переформулировкой теоремы 8.1 и алгоритма А.

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

  • Приведите постановку задачи контроля функции выходов автомата с помощью кратного эксперимента.
  • Приведите определение покрытия графа и его кратности.
  • Каков критерий существований покрытия графа?
  • Дайте определение приведенного покрытия графа.
  • Приведите верхнюю и нижнюю оценки кратности для правильного не сильно связного графа.
  • Дайте определение минимального покрытия графа.
  • Каково условие существования минимального покрытия?
  • Опишите процедуру построения покрытия правильного графа.
    •
    Страницы:

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

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

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

    Определение 8.1. Множество $$P$$ путей в графе $$G(S,U)$$, исходящих из начальной вершины $$s_0$$ этого графа, назовем покрытием, если каждая дуга $$G(S,U)$$ принадлежит некоторому пути из $$P$$.

    Определение 8.2. Число путей покрытия назовем его кратностью, а сумму длин всех путей покрытия - его длиной.

    Перейдем к рассмотрению задачи построения покрытия графа $$G(S,U)$$ с начальной вершиной $$s_0$$.

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

    Условимся считать, что из каждой вершины $$s$$ графа $$G$$ исходит "пустой" путь нулевой длины, заканчивающийся в той же вершине. Будем говорить, что вершина $$s$$ графа $$G$$ достижима из вершины $$t$$, если в $$G$$ существует путь из вершины $$t$$ в вершину $$s$$. Из этого определения следует, что каждая вершина графа достижима из самой себя. Полагаем, что каждой вершине графа $$G$$ инцидентна хотя бы одна дуга. Обозначим через $$T$$ множество всех тех вершин графа $$G$$, из которых исходит хотя бы одна дуга.

    Теорема 8.1. Покрытие графа $$G$$ существует тогда и только тогда, когда любая вершина множества $$T$$ достижима из начальной.

    Доказательство. Пусть $$P$$ - некоторое покрытие графа $$G$$ и $$s$$ - некоторая вершина из $$T$$. Поскольку из вершины $$s$$ исходит некоторая дуга и эта дуга принадлежит одному из путей покрытия, то вершина $$s$$ достижима из $$s_0$$. Вершина $$s_0$$ достижима из самой себя по крайней мере по "пустому" пути. Отсюда следует, что любая вершина множества $$T$$ достижима из $$s_0$$. Предположим теперь, что в графе $$G$$ любая вершина $$s \in T$$ достижима из $$s_0$$. Зафиксируем произвольно некоторую вершину $$t \in T$$. Пусть $$u_1, u_2, \dots, u_{k_t}$$ - путь, ведущий из $$s_o$$ в $$t$$, а $$\{\nu_1, \dots, \nu_{r_t)}\}$$ - множество всех дуг, исходящих из $$t$$. Построим множество путей $$P_t=\{u_{1u2} \dots u_{k_t} \nu_1, \dots, u_{1u2} \dots u_{k_t} \nu_r\}$$. Легко видеть, что объединение множеств $$P_t$$ по всем $$t \in T$$ является покрытием графа $$G$$. Этим и заканчивается доказательство теоремы.

    Граф, для которого существует покрытие, назовем правильным. Граф $$H(S,V)$$ назовем сверхграфом графа $$G(S,U)$$, если $$V \supseteq U$$. Сверхграф $$H$$ графа $$G$$ назовем регулярным, если любая дуга из множества $$V\U$$ оканчивается в вершине $$s_0$$. Дуги этого множества будем называть замыкающими.

    Лемма 8.1. Каждому контуру $$C$$ регулярного сверхграфа $$H$$ графа $$G$$, проходящему через все дуги графа $$H$$, соответствует покрытие графа $$G$$.

    Доказательство. Пусть $$C$$ - контур, проходящий через все дуги регулярного сверхграфа $$H$$. По этому контуру строим множество $$P$$ всех максимальных по длине путей, входящих в $$C$$, но не содержащих замыкающих дуг. Поскольку каждая замыкающая дуга оканчивается в $$s_0$$, то путь из $$P$$ начинается в $$s_0$$. Множество $$P$$ получено из контура $$C$$ исключением только всех замыкающих дуг. Отсюда следует, что любая дуга графа $$G$$ входит хотя бы в один путь из $$P$$, т. е. есть покрытие.

    Лемма 8.2. Каждому покрытию графа $$G$$ соответствует регулярный сильно связный сверхграф $$H$$ графа $$G$$ и контур $$C$$, проходящий через все дуги $$H$$.

    Доказательство. Пусть $$P=\{p_1 \dots, p_k\}$$ - покрытие графа $$G$$. По этому покрытию и графу $$G$$ построим граф $$H$$ следующим образом: если путь $$p_i \in P$$ оканчивается в вершине $$s$$, то проведем из $$s$$ в $$s_0$$ замыкающую дугу $$r_t$$. Поскольку $$G$$ - правильный граф, то полученный граф $$H(S,V)$$, где $$V+UY\{r_i, \dots, r_k\}$$, является сильно связным регулярным сверхграфом графа $$G$$, а путь $$p_{1r_1p_2r2} \dots p_kr_k$$ - контуром, проходящим через все дуги графа $$H$$.

    Определение 8.3. Покрытие $$P=\p_1, \dots, p_k\}$$ графа $$G$$ назовем приведенным, если выполняются следующие условия:

  • для всех $$i \ne j, 1 \le i, j \le k$$, путь $$p_i$$ не является начальным отрезком пути $$p_j$$ ;
  • для всякого $$q$$, являющегося начальным отрезком пути $$p_i, q \ne p_i, i=1, \dots, k$$, множество $$P'=\{p_1, \dots, p_{i-1}, q, p_{i+1}, \dots, p_k\}$$ не является покрытием.
    •

    Пусть $$P$$ - приведенное покрытие графа $$G$$. Из пункта 2 определения 8.3 следует, что если $$p \in P$$ и $$p$$ оканчивается дугой $$u$$, то эта дуга не принадлежит никакому другому пути из $$P$$. Из последнего факта непосредственно вытекает, что для правильного графа $$G$$ всегда существует приведенное покрытие, кратность которого не превосходит числа дуг графа. Легко видеть, что эта оценка достижима для графов с любым числом дуг и вершин. Из определения 8.3 также следует, что покрытие минимальной длины является приведенным.

    Если граф сильно связен, то всегда существует контур, проходящий через все его дуги, т. е. всегда существует приведенное покрытие этого графа кратности 1.

    Рассмотрим теперь не сильно связный граф. Докажем ряд вспомогательных утверждений. Используемые обозначения те же, что и в лекции 6 ч. I.

    Лемма 8.3. Для правильного не сильно связного графа множество положительных вершин не пусто.

    Доказательство. Пусть $$G$$ - некоторый правильный не сильно связный граф, у которого $$S^+$$ пусто. Тогда множество $$S^-$$ также пусто и, следовательно, $$\Delta (s)=0$$ для всех $$s \in S$$. Поскольку правильный граф связен, то из последнего факта следует, что граф $$G$$ обладает эйлеровым контуром и, стало быть, он сильно связен. Полученное противоречие доказывает лемму.

    Лемма 8.4. Из любой вершины связного графа, у которого $$S^+$$ не пусто, достижима хотя бы одна положительная вершина.

    Доказательство. Пусть $$F(S,U)$$ - связный граф, у которого $$S^+$$ не пусто. Из каждой вершины $$s \in S^+$$ проведем ровно $$\Delta (s)$$ дуг, оканчивающихся в отрицательных вершинах, таким образом, чтобы каждая отрицательная вершина $$t$$ служила концом ровно $$\Delta (t)$$ таких дуг.

    В результате получим новый граф $$F'(S,U)$$, у которого $$V \supseteq U$$ и для всех вершин $$s \Delta (s)=0$$. В силу теоремы 2 из [25, c.182], граф $$F'$$ обладает эйлеровым контуром $$C$$.

    Рассмотрим отрезок этого контура, лежащий между двумя дугами из множества $$V\U$$. Этот отрезок является, очевидно, путем, ведущим из некоторой отрицательной вершины графа $$F$$ в некоторую положительную вершину. По построению графа $$F'$$ в каждую отрицательную вершину графа $$F$$ входит хотя бы одна дуга из $$V\U$$. Следовательно, из каждой отрицательной вершины графа $$F$$ достижима некоторая положительная.

    Любая положительная вершина достижима из самой себя по "пустому" пути. Рассмотрим, наконец, произвольную вершину $$s$$, у которой $$\Delta (s)=0$$. Из нее достижима положительная вершина, поскольку из $$s$$ выходит по крайней мере одна дуга и эта дуга содержится в пути, порожденном контуром $$C$$, из отрицательной в положительную вершину. Лемма доказана.

    Рассмотрим граф $$G$$, множество $$S^+$$ которого не пусто. Из каждой вершины $$s \in S'$$, где $$S' \subseteq S^+$$, проведем в вершину $$s_0$$ ровно $$\Delta (s)$$ дуг. Эти дополнительные дуги обозначим через $$r_i, \dots , r_k$$, где $$k=\sum_{s \in S} \Delta (s)$$. Полученный граф обозначим через $$H(G,S')$$.

    Теорема 8.2. Для правильного не сильно связного графа $$G$$ всегда существует покрытие, кратность которого не превосходит величины

    $$\sum_{s \in S^+} \Delta (s)$$

    Доказательство. В силу леммы 8.3 множество $$S^+$$ для правильного не сильно связного графа $$G$$ не пусто. Из теоремы 8.1 следует, что граф $$G$$ связен. Построим граф $$H(G,S^+$$. В силу леммы 8.4 и правильности графа $$G$$ граф $$H(G,S^+)$$ является сильно связным регулярным сверхграфом. Зафиксируем некоторый контур $$C$$ графа $$H(G,S^+)$$, проходящий через все его дуги. По лемме 8.1 этому контуру соответствует покрытие $$P$$, содержащее пути, полученные из $$C$$ исключением всех замыкающих дуг $$r_1, \dots , r_k$$ графа $$H(G,S^+)$$. Из правила построения этого графа следует, что между любыми двумя вхождениями замыкающих дуг в контуре $$C$$ имеется хотя бы одна дуга графа $$G$$. Для завершения доказательства теоремы достаточно показать, что в графе $$H(G,S^+)$$ существует такой контур $$C'$$, проходящий через все дуги этого графа, что каждая дуга $$r_t$$ входит в этот контур только один раз. По построению в графе $$H(G,S^+)$$ для каждой вершины $$s \in S^+ \Delta (s)=0$$ и положительной может быть только вершина $$s_0$$. Поскольку из $$s_0$$ достижима любая вершина графа, то всегда можно построить компенсирующую систему графа $$H(G,S^+)$$, используя только дуги из $$U$$. Следовательно, искомый контур $$C'$$ существует. По лемме 8.1 ему соответствует покрытие кратности (8.1), что и требовалось доказать.

    Легко видеть, что оценка (8.1) достижима для всех ее значений.

    Оценим снизу кратность покрытия правильного графа $$G$$. Напомним, что множество $$S\T$$ состоит из вершин графа $$G$$, из которых не выходят дуги. По ранее сделанному предположению любая вершина графа $$G$$ инцидентна хотя бы одной дуге, но тогда $$S\T \subseteq S^+$$. Пусть мощность множества $$S\T$$ равна $$r$$. По лемме 8.2 всякому покрытию графа $$G$$ соответствует некоторый регулярный сильно связный сверхграф $$H$$ графа $$G$$, число замыкающих дуг которого не меньше $$r$$. Отсюда следует, что кратность любого покрытия графа $$G$$ не может быть меньше величины $$r$$. Легко видеть, что эта оценка достижима для всех значений $$r$$.

    Перейдем к уточнению нижней оценки кратности. Множество $$R^+$$ вершин графа $$G$$ определим следующим образом: $$s \in R^+$$, если $$s \in S^+$$ и из вершины $$s$$ не достижима ни одна отрицательная вершина графа $$G$$. Очевидно, что $$S\T \subseteq S^+$$ и для правильного графа $$s_0 \ne R^+$$. Кроме того, для правильного не сильно связного графа $$G$$ множество $$R^+$$ не пусто. Доказательство этого утверждения может быть проведено по аналогии с доказательством леммы 8.3.

    Покажем справедливость следующего утверждения.

    Теорема 8.3. Кратность покрытия правильного графа не может быть меньше величины

    $$\sum _{s \in R^+} \Delta (s)$$

    Доказательство. Пусть $$P=\{p_1, \dots, p_k\}$$ - некоторое покрытие графа $$G$$. По этому покрытию, используя доказательство леммы 8.3, построим сильно связный регулярный сверхграф $$H$$ графа $$G$$. Пусть $$C$$ - контур графа $$H$$, соответствующий покрытию $$P$$. Каждую дугу графа $$H$$ заменим дугами $$l$$ с тем же началом и концом, где $$l$$ - число вхождений дуги в контур. Полученный в результате граф $$H'$$ обладает эйлеровым контуром. Поскольку для любой вершины $$s$$ графа $$H'* \Delta (s)=0$$, то в вершину $$s_0$$ заходит не менее $$\sum_{s \in R^+} \Delta (s)$$ замыкающих дуг. Таким образом, кратность покрытия графа $$G$$ не может быть меньше величины (8.2).

    Рассмотрим граф, изображенный на рис.8.1. Для этого графа $$S^+=\{s_3, s_7, s_8\}, S\T=\{s_8\}, R^+=\{s_7, s_8\}, \sum_{s \in S^+} \Delta (s)=3, \sum_{s \in S^+} \Delta (s)=2$$.

    (рис 8.1)

    Множество $$P=\{u_1u_3u_5u_6u_8u_{10}, u_2u_4u_5u_7u_9\}$$ является, очевидно, приведенным покрытием кратности 2, т. е. оценка (8.2) в данном примере достижима. Нетрудно показать, что (8.2) является достижимой для любого своего значения.

    Следствие 1. Если для правильного не сильно связного графа $$G$$ множества $$R^+$$ и $$S^+$$ совпадают, то минимальная кратность покрытия графа $$G$$ равна величине (8.1).

    Справедливость этого утверждения вытекает непосредственно из теорем 8.2, 8.3 и того факта, что при совпадении множеств $$S^+$$ и $$R^+$$ оценки (8.1) и (8.2) равны.

    Определение 8.4. Приведенное покрытие графа, являющееся минимальным по кратности и по длине, назовем минимальным.

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

    (рис 8.2)

    Покрытия $$P_1=\{u_1u_2u_3u_4u_5u_6u_8, u_1u_2u_7u_6u_8u_9\}$$ и $$P_2=\{u_1u_2u_3u_4u_5u_6u_8u_9, u_1u_2u_7\}$$, как легко видеть, являются приведенными покрытиями этого графа. Покрытие $$P_1$$ является минимальным по кратности (кратность его равна 1), но не минимальным по длине (длина его равна 13). Покрытие $$P_2$$ (длины 11 и кратности 2) является минимальным по длине, но не минимальным по кратности. Легко установить, что для данного графа минимального покрытия не существует.

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

    Лемма 8.5. Если $$P$$ есть покрытие графа $$G$$ минимальной длины, то любой путь из $$P$$, не оканчивающийся в начальной вершине графа, оканчивается в некоторой положительной его вершине.

    Доказательство. Пусть $$P$$ - покрытие графа $$G(S,U)$$ минимальной длины $$l$$. Предположим, что существует путь $$p \in P$$, оканчивающийся в некоторой не положительной вершине $$w$$, где $$w \ne s_0$$. Покрытию $$P$$ соответствует регулярный сильно связный сверхграф $$H$$, способ построения которого описан при доказательстве леммы 8.3.

    Преобразуем граф $$H$$ следующим образом: каждую дугу $$u \in U$$ заменим $$f$$ дугами $$u(1), \dots, u(f)$$ с тем же началом и концом, где $$f$$ - число путей из $$P$$, содержащих дугу $$u$$. Легко видеть, что полученный в результате граф $$H'$$ обладает эйлеровым контуром. Поскольку $$w$$ не обладает положительной вершиной графа $$G$$ и $$w \ne s_0$$, то в графе $$H$$ эта вершина отрицательна, а в графе $$H'$$, очевидно, $$\Delta (w)=0$$. Отсюда следует, что найдется такая дуга $$u_1 \in U$$, оканчивающаяся в вершине $$w$$, что в графе $$H'$$ существуют дуги $$u_1(1), \dots, u_1(f)$$, где $$f \ge 2$$. Выполним следующее преобразование графа $$H'$$: исключим из него дугу $$u_1(f)$$ и одну замыкающую дугу, исходящую из $$w$$. Далее, из начальной вершины дуги $$u_1(f)$$, если она отлична от $$s_0$$, проводим одну замыкающую дугу в $$s_0$$. Полученный в результате такого преобразования новый граф $$H*$$, как это следует из его построения, обладает эйлеровым контуром.

    Число дуг графа $$H*$$ по крайней мере на единицу меньше числа дуг графа $$H'$$. Любому эйлерову контуру графа $$H'$$ соответствует покрытие $$P*$$ графа $$G$$ длины, не большей $$l-1$$. Отсюда следует, что $$P$$ не является покрытием минимальной длины. Полученное противоречие доказывает лемму.

    Сформулируем достаточное условие существования у графа минимального покрытия.

    Теорема 8.4. Если у правильного графа множества $$S^+$$ и $$R^+$$ совпадают, то у него существует мимнимальное покрытие.

    Доказательство. Если у правильного графа $$G$$ множество $$S^+$$ пусто, то он обладает эйлеровым контуром. Очевидно, что эйлеров контур является минимальным покрытием графа.

    Предположим теперь, что множество $$S^+$$ не пусто, следовательно, $$S^-$$ также не пусто. Поскольку $$S^+=R^+$$, а множество $$R^+$$ состоит из вершин, из которых не достижима ни одна отрицательная вершина, то граф $$G$$ заведомо не является сильно связным. В силу следствия 1 теоремы 8.3 минимальная кратность покрытия графа $$G$$ в таком случае равна (8.2).

    Пусть $$P$$ есть покрытие графа $$G$$ минимальной длины $$d$$ и каждый путь из $$P$$ оканчивается в вершине, не равной $$s_0$$. Тогда по лемме 8.5 каждый путь из $$P$$ оканчивается в вершине множества $$R^+$$. Предположим, что $$P$$ не минимально по кратности, т. е. его кратность $$k$$ больше (8.1). Пусть покрытию $$P$$ соответствует сильно связный регулярный граф $$H$$ (см. доказательство леммы 8.2). По графу $$H$$ построим эйлеров граф $$H'$$, заменяя каждую дугу $$u \in U$$ столькими дугами (с тем же началом и концом), скольким путям из $$P$$ принадлежит дуга $$u$$. Поскольку $$k$$ больше (8.1), то найдется вершина $$t \in S_+$$, из которой в графе $$H$$ выходит $$l$$ замыкающих дуг, где $$l>\Delta (t)$$. Следовательно, в графе $$H$$ найдется дуга $$\nu \in U$$, входящая в вершину $$t$$ и принадлежащая по крайней мере двум путям из $$P$$. Тогда в графе $$H'$$ удалим одну дугу $$\nu'$$, соответствующую дуге $$\nu$$, и удалим одну замыкающую дугу, исходящую из $$t$$. Затем из начала дуги $$\nu'$$ в вершину $$s_0$$ проведем одну дугу. Легко видеть, что полученный граф $$H*$$ является эйлеровым и его эйлерову контуру соответствует покрытие графа $$G$$ длины $$d-1$$. Следовательно, $$P$$ не является покрытием минимальной длины. Противоречие доказывает, что $$P$$ - минимально еопкрытие.

    Рассмотрим, наконец, минимальное по длине покрытие $$P=\{p_1, \dots, p_k\}$$ графа $$G$$, у которого некоторые пути оканчиваются в $$s_0$$. Пусть кратность покрытия $$P$$ больше (8.1) и пути $$p_1, \dots, p_l$$ оканчиваются в $$s_0$$. Легко видеть, что покрытие $$P'=\{p_{1p2} \dots p_{l+1}p_{l+2}, \dots, p_k\}$$ также является покрытием минимальной длины и все пути из $$P'$$ оканчиваются только в положительных вершинах. Выше было показано, что кратность покрытия $$P'$$ минимальна. Теорема доказана.

    Перейдем к описанию алгоритма построения покрытия правильного графа $$G$$. Пути искомого покрытия обозначим через $$p_i$$. Каждой вершине $$s \in T$$ поставим в соответствие множество $$U_s^0$$ всех дуг, выходящих из $$s$$. Дуги в $$U_s^0$$ занумеруем числами $$1,2, \dots$$ причем если $$u_i, u_j \in U_s^0$$ и $$u_i$$ - петля, то $$i<j$$.

    В алгоритме будут использованы функции $$\varphi$$ и $$\delta$$, определяемые такими соотношениями: $$\varphi (u)$$ - номер дуги $$u$$ во множестве $$U_s^0, \delta(s,p)$$ - конечная вершина пути $$p$$, исходящего из вершины $$s$$.

    В описанном алгоритме кроме построения покрытия производится вычисление параметра $$j$$, необходимого для оценки длины полученного покрытия.

    Для краткости при описании алгоритма используем операцию присваивания ":=", употребляемую в том же смысле, что и в алгоритмических языках.

    Алгоритм А.

  • $$P:= \varnothing, i:=1, p_i:=e, s:=s_0, j=0$$ ; для всех $$s \in T:U_s:=U_s^0$$.
  • Если $$U_s \ne \varnothing$$, то перейти к пункту 3, иначе к пункту 4.
  • $$p_i=p_iu$$, где $$u$$ - дуга из множества $$U_s$$, имеющая наименьший номер; $$U_s:=U_s\ \{u\}, s:=\delta (s,u)$$ ; если $$\varphi (u) \ne 1$$, то $$j:=j+1$$ ; перейти к пункту 2.
  • Если $$Y_{s \in S} U_s \ne \varnothing$$ то перейти к пункту 5, иначе работа алгоритма завершается.
  • Если из вершины $$s$$ достижима хотя бы одна вершина $$t$$, для которой $$U_t \ne \varnothing$$, то перейти к пункту 6, иначе к пункту 7.
  • Построить кратчайший путь $$q_j$$, ведущий из вершины $$s$$ в вершину из множества $$\{t|U_t \ne \varnothing \}, p_i:=p_iQ_j$$, и перейти к пункту 3.
  • $$s:=s_0; P:=PY\{p_i\}; i:=i+1; p_i:=e$$ и перейти к пункту 3.
    •

    Заметим, что в случае сильно связного графа полученное по этому алгоритму покрытие имеет кратность 1.

    Оценим сверху длину покрытия, построенного с помощью алгоритма $$A$$. Пусть $$m_s$$ - мощность множества $$U_s, s \in T$$. Множество $$\{m_s\}_{s \in T}$$ упорядочим отношением " $$\le$$ " и обозначим через $$(m_1, \dots , m_s)$$, где $$m_i \le m_j$$, если $$i <j$$.

    Алгоритм $$A$$ можно считать пошаговым процессом, где $$j$$ -м шагом будут являться построения, выполняемые алгоритмом при фиксированном значении параметра $$j$$. Путь $$q_j$$, описанный в пункте 6 алгоритма $$A$$, будем называть транслирующим. Очевидно, что длина покрытия, построенного по алгоритму, равна сумме числа дуг графа и длин всех транслирующих путей.

    Оценим суммарную длину всех транслирующих путей покрытия, построенного по алгоритму $$A$$.

    Из описанного алгоритма следует, что длина транслирующего пути $$q_j$$ не превосходит числа таких вершин $$s$$ из $$T$$, для которых на $$j$$ -м шаге $$U_s= \varnothing$$. Поэтому для значений $$j$$ от 0 до $$m_1-1$$ включительно $$q_j=e$$, где $$e$$ - "пустой" путь. Далее, для значений $$j$$ от $$m_1$$ до $$m_2-1$$ включительно длина $$q_j$$ не превосходит единицы. Из описания алгоритма следует, что на последнем шаге работы алгоритма значение $$j$$ равно $$\sum_{i=1}^f(m_i-1)$$. Отсюда, учитывая предыдущие рассуждения, легко показать, что суммарная длина транслирующих путей, построенных по алгоритму, не превосходит величины

    $$Q=\sum_{i=1}^{f}(i-1)(m_i-1)$$

    Следовательно, справедливо следующее утверждение.

    Теорема 8.5. Для правильного графа $$G$$ всегда существует покрытие, длина которого не превышает величины

    $$W+Q$$

    где $$W$$ - число дуг графа.

    Следствие 1. Для правильного $$n$$ -вершинного автоматного графа степени $$m$$ всегда существует покрытие длины, не превышающей величины

    $$mn+\frac 12 (m-1)n(n-1)$$

    Следствие непосредственно вытекает из теоремы 8.5, так как для автоматного графа $$W=mn$$ и $$Q=\frac 12 (m-1)n(n-1)$$.

    В [16] доказано, что для всех $$n$$ и $$m$$ существует $$n$$ -вершинный сильно связный автоматный граф степени $$m$$, у которого имеется контур, проходящий через все дуги графа, минимальной длины, равной (8.5). Из этого факта следует, что оценка (8.5) достижима при всех $$n$$ и $$m$$. Следовательно, оценки (8.4) и (8.3) также достижимы.

    Перейдем теперь к автоматной интерпретации полученных результатов. Если автомат Мили задан в виде конечного ориентированного автоматного графа, то каждому пути покрытия графа ставится в соответствие некоторое входное слово, а множество слов, соответствующих всем путям покрытия, составит кратный безусловный эксперимент. Таким образом, для распознавания функции выходов заданного инициального автомата или ему эквивалентного с $$n$$ состояниями и $$m$$ входными сигналами может быть использован кратный эксперимент , длина которого не превышает величины (8.5), а кратность - величины (8.2). Необходимое и достаточное условие существования кратного эксперимента, а также алгоритм его построения получаются простой переформулировкой теоремы 8.1 и алгоритма А.

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

  • Приведите постановку задачи контроля функции выходов автомата с помощью кратного эксперимента.
  • Приведите определение покрытия графа и его кратности.
  • Каков критерий существований покрытия графа?
  • Дайте определение приведенного покрытия графа.
  • Приведите верхнюю и нижнюю оценки кратности для правильного не сильно связного графа.
  • Дайте определение минимального покрытия графа.
  • Каково условие существования минимального покрытия?
  • Опишите процедуру построения покрытия правильного графа.
    •
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^