Содержание к диссертации
Введение
Глава 1. Свойства контрольных экспериментов для детерминированных графов 21
1.1 Основные определения и обозначения 22
1.2 Безреверсный базис и его свойства 25
1.3 Существование и некоторые общие свойства контрольных экспериментов для детерминированных графов 30
Глава 2. Контроль детерминированных деревьев 43
2.1 Контрольный эксперимент для детерминированных деревьев 44
2.2 Контроль изоморфной вложимости 57
Глава 3. Контроль маркированных графов 62
3.1 Структура класса маркированных графов 63
3.2 Контрольные эксперименты для маркированных графов 68
Глава 4. Реализация контрольного эксперимента конечным автоматом 90
4.1 Автоматы, реализующие контрольный эксперимент 91
4.2 Автоматы с красками 94
4.2.1 Автомат с одной краской 96
4.2.2 Автомат с A(G) красками 98
Заключение 107
Список литературы 109
- Существование и некоторые общие свойства контрольных экспериментов для детерминированных графов
- Контрольный эксперимент для детерминированных деревьев
- Структура класса маркированных графов
- Автоматы, реализующие контрольный эксперимент
Введение к работе
Актуальность іемьі. Бурпое развитие ішбсрнетики и информатики стимулирует ипгснсивное развитие теории управляющих и вычислительных процессов, а также моделей (систем), реализующих эти процессы Одной из основных моделей при этом является модель взаимодействия управляющей и управляемой систем (управляготцего автомата и операционной среды). Взаимодействие этих систем зачастую представляє/ся как процесс перемещения управляющего автомата по ірафу ("лабиринт}") управляемой системы, что привело к возникновению обширной и ишенсивно развивающейся области исследований поведения автоматов в лабиринтах. Одним из направлений этих исследований является анализ с помощью автомата изображений, формальных языков, рабочих пространств робота и других дискретных систем
Одна из центральных и актуальных проблем такого анализа известна из работ Г.Дудека, М.Джснкина, Е Милиоса и Д Вилкеса как "проблема проверки правильности карты" Эта проблема сое шит в следующем: задан конечный граф-эталон (карта) и определен класс исследуемых графов рабочих пространств Требуется построить автомат, который, передвигаясь по произвольному графу из этого класса и воспринимая некоторую локальную информацию о вершинах пройденных путей, проверяет, изоморфен ли исследуемый граф эталону или не: Процесс прохождения путей по графу, восприятия локальной информации о вершинах путей и вывода заключений о свойствах графа называется контрольным экспериментом над графом При этом вершины и ребра исследуемого графа могут нести отметки, которые автомат во время эксперимента может изменять
При исследовании проблемы проверки правильности карты наметилось несколько подходов. Один из них основан на том, что исследуемые графы являются конечными инициальными автоматами без выхода, т е конечными ориентированными графами с постоянными отметками на дугах В рамках этого подхода в работах В.Б.Кудрявцева, Г Ю Кудрявцева, И С Грунского и Р.И.Олейника найдены точные верхние оценки наименьшего времени, ій которое различаются два графа, предложен метод построения контрольных экспериментов относительно класса всех таких графов число вершин которых не превосходит числа вершин эталона. Второй подход заключается в рассмотрении лабиринтов, являющихся неориентированными конечными графами, и в процессе эксперимента на ребрах графа управляющий ашомаї расставляет отметки. В работах Т.Левипа и 1 Дудека предложен ряд методов проведения контрольных экспериментов относительно конечных классов исстедуемых графов Третий подход исходит из предположения, что лабиринты являются нсориеитированными графами с отмеченными вершинами В работах
С В Сапунова пред Ю/кены методы различения таких графов и метопы проведения коні рольных экспериментов для конечных классов графов
Результаты, полученные в рамках тгих подходов, не образуют цельной картины и, в огличие 01 ' классической" теории экспериментов с автоматами, заложенной ') Муром и С В Яблонским и созданной трудами Л.М Богомолова, В Б.Кудрявпева. С В Алешина, Л С Подколзина, Д В.Сперанского и И С.Грунского, исследования в этой области находятся в зачаточном состоянии Поэтому разрабоїка этой тематики чрезвычайно актуальна
Данная диссертационная работ посвящена проблематике связанной с автоматным анализом ірафов (лабиринтов) с отмеченными вершинами, а именно вопросам исследования условий существования и методам построения контро тьных экспериментов над этими ірафами. Описание управляемых систем такими графами используется в сисіемах распознавания зрительных образов, в системах навигации роботов, в моделях представления знаний в интеллектуальных системах принятия решений, в системах поиска в сетях ЭВМ и в мультиагентных системах, при разработке операционных сред вычислительных систем. Поэтому тематика диссертации актуальна как в теоретическом, так и в прикладном плане.
Целью работы является нахождение условий существования контрольных экспериментов для потенциально бесконечных классов исследуемых графов; исследование свойств таких экспериментов; разработка методов построения контрольных экспериментов для потенциально бесконечных классов исследуемых графов, разработка алюритмов синтеза конечных автоматов, реализующих контрольный эксперимент в заданном классе исследуемых графов.
Мєіодьі исследования. Меюдологическуто основу рабош составляют методы теории графов, формальных языков, автоматов и алгоритмов.
Новые научные резулм а і ы и положения, выносимые на защиту.
В работе исследованы условия существования контрольных экспериментов над графами с отмеченными вершинами, их структурные и метрические свойства, методы построения таких экспериментов и методы их реалиіации в управляющих конечных автоматах
Введен новый класс ЙГ(М) всех детерминированных графов над алфавитом отметок М, у которых отметки любой нары различных вершин, смежных с одной и юй же вершиной, различны При лом отметки являются элементами заданного алфавита М Предполагается, что все рассматриваемые в работе трафы принадлежат классу А"(М) Потучены следующие результаты
1 Найден общий критерий существования контрольного эксперимента для
произвольного графа-эталона относительно произвольного класса исследуемых
графов Из этого критерия следует, что если класс исследуемых ірафов совпадает с
ЛГ(М), то контрольный эксперимеш существует точно тогда, когда эталон является
деревом Полностью решена задача характеризации таких экспериментов. Для
эталона-дерева предложен метол построения контрольного эксперимент
относительно ЛГ(М) квадратичной (от числа вершин эталона) сложности.
Предложен метод анализа резулыаюв эксперимента для этою случая,
позволяющий проверить не только изоморфизм эталона и исследуемого графа, но и
наличие их изоморфного вложения друг в друга.
2 В классе К(М) выделен, возможно, бесконечный класс K(M,U), UcM, всех ірафов,
у которых любой отметкой utU, называемой маркером, отмечена не более чем
одна вершина, и его подкласс Km(M,V) всех ірафов, содержащих, по крайней мере,
одну вершину, отмеченную маркером. Найдены критерии бесконечности,
конечности и пустоты выделенных классов, их интересных подклассов и
дополнения К(М, U) до К(М), Для случая, когда граф-эталон принадлежит классу
Km(M,\J), а класс исследуемых графов совпадает с K(M,\J) предложено несколько
способов построения контрольных экспериментов, различающихся априорной
информацией о графе-эталоне. В случае, когда зіалон задан полностью, эти
способы позволяю і построиіь контрольный эксперимент длины О(п), крашосіи
0(п2) и объема 0(п3), где п - число вершин зіалона.
3. Предложен метод синтеза, который по любому контрольному эксперименту Р объема $(Р) для некоторых эталона и класса исследуемых графов строит конечный авюмат с 3>(Р) |Р| 12 состояниями, реализующий этот эксперимент за время 29(Р)
4 Предложен метод проведения контрольного эксперимента для произвольною детерминированного эталона О относительно класса К(М) конечным автомаюм, который блуждает по исследуемому ірафу, исследует исходные о і метки вершин и можеі сіавигь дополнительные отметки вершин нестираемыми красками Предложен метод построения автоматов с одной или HG) красками, где k(G) не превосходит числа п вершин зіалона. При этом число состояний автомата, а также временная сложность проведения эксперимента не превосходят 0(п ) для автомата с одной краской и О(п) для автомата с WG) красками Эти результаты являются новыми и завершенными Таким образом, впервые
получен ряд критериев существования, методов построения и автоматной реализации
контрольных экспериментов для деіерминированньїх графов относительно
потенциально бесконечных классов исследуемых графов.
Теоретическая и практическая ценность. В рабо\ е получен ряд нетривиальных окончательных резулыаюв. позволяющих понять механизмы контроля графов с отмеченными вершинами из потенциально бесконечных классов с помощью блуждающею по ним автомаїа Работа носит теоретический хараюер, однако полученные в ней результаты могут иметь прикладное значение в задачах разработки мобильных роботов, задачах автоматного анализа изображений и задачах контроля автоматов для практически важных потенциально бесконечных классов неисправностей.
Апробация работы. Основные положения и результаты диссертации докладывались на конференции "Алгебраические методы дискретной математики" (Украина, Луїанск, 2002), 5-ом международном конгрессе но маїемашческому моделированию (Россия, Дубна, 2002), 8-ом международном семинаре "Дискретная математика и ее приложения" (Москва, МГУ, 2004), 6-ом международном конгрессе по математическому моделированию (Россия, Нижний Новгород, 2004), 6-ой международной конференции "Дискретные модели в теории управляющих систем" (Москва, МГУ, 2004).
Публикации. Но результатам диссертации опубликованы 8 работ, из коюрых [1,2,7,8] в соавторстве, остальные самостоятельно. В работах [1.21 диссертантом конструктивно введено понятие лабиринтной характеристики простого связного графа, доказано что совпадение лабиринтных характеристик любой пары графов влечет их изоморфизм. Кроме Ю10, для произвольною заданного графа-эгалона предложен алгоритм синтеза конечного автомата с красками, который, взаимодействуя с произвольным простым связным графом, проверяет, изоморфен этот граф эталону или нет В работе [7] диссертантом получен критерий существования контрольного эксперимент дія произвольных детерминированного графа-эталона и класса исследуемых детерминированных графов, установлен ряд общих свойств таких экспериментов, найдена конструктивная харакіеризация кошрольных эксперименте для эталона-дерева и обоснован способ построения такого эксперимента В работе [8] диссертантом определен класс маркированных детерминированных графов, доказано существование и предложен способ построения контрольною эксперимента для маркированного эталона относшельно класса всех маркированных графов
Объем и структура диссертации. Диссертация содержи) 113 машинописных страниц и состоит из введения, четырех глав, заключения и списка литературы, включающего 48 наименований
Существование и некоторые общие свойства контрольных экспериментов для детерминированных графов
Центральным результатом раздела 2.1 является следующая теорема. Теорема 2.1.3. Конечное множество слов РсМ является контрольным экспериментом для эталона Тє 7 (М) относительно класса К(М) тогда и только тогда, когда К(РпЬт)єУГ(Т) и в VF(T) найдется такой свободный базис достижимости VF(T), что/і(Р-Іт) содержит (VF(T)M)-Z,T.
Теорема 2.1.3 формулирует конструктивный критерий, позволяющий для любого конечного множества слов проверять: является это множество контрольным экспериментом для эталона-дерева Тє ДМ) относительно класса А (М) или нет. Следующая теорема предлагает один из способов построения такого эксперимента.
Теорема 2.1.4. Множество слов Ci(T)=B[V(T)Mi] является контрольным экспериментом для эталона ТєГ(М) относительно класса К(М). Кратность эксперимента Cj(T) составляет n(M—1)+2, а длина не превосходит п+1, где п — число вершин дерева Т. Объем этого эксперимента составляет не менее 2М+3(М-1)(п-1)+1, и не превосходит 2М+(М-1)(п-1)(п+4)/2+1. Если считать временем проверки исследуемого графа на изоморфизм эталону Т число перемещений автомата по вершинам исследуемого графа, то асимптотическая оценка временной сложности такой проверки с использованием контрольного эксперимента С[(Т) в наихудшем случае составляет 0(п ). Утверждение 2.1.1. Если РсМ — контрольный эксперимент для эталона Те ДМ) относительно класса ДМ), то Р является также контрольным экспериментом для Т относительно класса Л (М). Согласно утверждению 2.1.1 задачи построения контрольных экспериментов для дерева Те ДМ) относительно классов ДМ) и ЛГ(М) эквивалентны. В разделе 2.2 рассматривается задача контроля с помощью контрольного эксперимента изоморфной вложимости для детерминированных деревьев. Основные результаты этого раздела сформулированы в следующих теоремах. Теорема 2.2.1. Если РсМ+ - контрольный эксперимент для эталона Те ДМ) относительно класса К(М), то любой граф НєЛ (М) изоморфно вложим в Т тогда и только тогда, когда B[R(P)]nZ,n 0 и Е[К(Р)]г\цсБ[11(Р)]оЛт-Теорема 2.2.3. Пусть РсМ+ - контрольный эксперимент для эталона Тє ДМ) относительно класса Л"(М) и J - произвольное дерево из класса ДМ). Тогда равносильны следующие утверждения: Теорема 2.2.1 показывает, как с помощью контрольного эксперимента можно проверить, является исследуемый граф из класса ЛГ(М) изоморфно вложимым в эталон-дерево или нет. Согласно теореме 2.2.3, с использованием контрольного эксперимента можно проверять изоморфную вложимость эталона из ДМ) в исследуемый граф, если исследуемый граф тоже является деревом. В третьей главе исследуется специальный, возможно, бесконечный класс /f(M,U), где U с М, графов из /Г(М), в каждом из которых любой отметкой ueU отмечена не более чем одна вершина, причем множество U заранее задано. Элементы множества U назовем маркерами, а любой граф из класса A"(M,U), содержащий, по крайней мере, одну маркированную вершину, — маркированным графом. Через /fm(M,U) обозначим подкласс всех маркированных графов из Ar(M,U). Положим A N(M,U)= M)U)-A m(M,U), Л"(М5 U)=A(M)-A (M,U). В разделе 3.1 исследуются свойства классов A (M,U), A m(M,U), A"N(M,U) и K(M,\J). Найдены конструктивные критерии пустоты, конечности и бесконечности этих классов в терминах свойств множества маркеров. Раздел 3.2 посвящен задаче построения контрольных экспериментов для маркированных графов. Установлено, что ни для какого GeA(M)-r(M) не существует контрольного эксперимента относительно класса A(M,U). Рассмотрен подкласс Ка(М,и) класса K(M,V)t состоящий из всех графов, имеющих, по крайней мере, две отличимые вершины, отмеченные одинаковым маркером ueU. Для произвольного графа GeKa(M,u) установлена справедливость следующего утверждения. Теорема 3.2.!. Для любого эталона G из класса А а(М,и) существует контрольный эксперимент относительно класса К(М)—Ка(М,и) кратности не более 3 и длины не более 2п-Х0, где п - число вершин графа G. Следующая теорема устанавливает существование контрольного эксперимента для графа-эталона из класса A(M,U)ijArm(MJU) относительно класса A N(M,U). Теорема 3.2.2. Для любого эталона G из класса К(М,U)\jKm(M,\J) существует контрольный эксперимент относительно класса AK(M,U) кратности один, длиной не более п для случая GeAm(M,U) и не более (п-1) для случая Ge A"(M,U), где п-число вершин графа G. Пусть UGU - произвольный фиксированный маркер. Обозначим через А)(М,и) класс, состоящий из всех таких графов G, что в G найдется пара смежных вершин g и g", отмеченных символом и. Для графов из класса АГ](М,и) справедлива следующая теорема о существовании контрольного эксперимента. Теорема 3.2.3. Для любого эталона G из класса ATi(M,u) существует контрольный эксперимент относительно класса К(М)-К\(М,и) кратности один gl и длиной не более п, где п — число вершин графа G. Разобьем класс ifm(M,U) на два непересекающихся подкласса: Гт=/Гт(М,и)пЗП[М) и Zm=KJ№,U)m. Теорема 3.2.6. Для любого эталона G из класса Zm множество слов C5(G)=Z,G2n-2Mb где п - число вершин эталона, является контрольным экспериментом для G относительно класса /f(M,U). Теорема 3.2.6 устанавливает существование контрольного эксперимента для маркированных графов, не являющихся деревьями, относительно класса /f(M,U). Нетрудно показать, что утверждение этой теоремы остается справедливым и в том случае, когда эталон G - дерево. Для любого графа G из класса Л (М) через UQCXQ обозначим множество всех таких отметок х вершин графа G, для которых существует единственная вершина geSc такая, что n.(g)=x. Следующая теорема обобщает утверждение теоремы 3.2,6. Теорема 3.2.7. Для любого такого эталона G из класса А (М), что UQ- 0, множество слов C5(G)=iG2n 2Mb где п - число вершин графа G, является контрольным экспериментом относительно класса U К(М,{х}).
Контрольный эксперимент для детерминированных деревьев
В предыдущей главе было установлено (следствия 1.3.1-1.3.2), что контрольный эксперимент относительно класса Л"(М) всех детерминированных графов существует тогда и только тогда, когда граф-эталон принадлежит классу Т(М), т.е. является деревом. Также было установлено (теорема 1.3.2), что язык, представимый любым детерминированным деревом, отличается от всякого языка, представимого графом из K(M)(M)t и любые два детерминированных дерева изоморфны тогда и только тогда, когда представляемые ими языки совпадают.
В данной главе рассматривается задача построения контрольного эксперимента для эталона-дерева относительно класса К(М). Формулируется конструктивный критерий, позволяющий для любого конечного множества слов в алфавите отметок М проверять: является это множество контрольным экспериментом для дерева ТеГ(М) относительно класса Л (М) или нет. Предлагается способ построения такого контрольного эксперимента, оценивается его сложность. Асимптотическая оценка временной сложности проверки исследуемого графа на изоморфизм дереву-эталону с использованием предложенного контрольного эксперимента составляет 0(п ), где п - число вершин эталона. Обнаружено, что всякий контрольный эксперимент для детермиЕіированного дерева относительно класса Т(М) является контрольным экспериментом для этого дерева относительно класса К(Ы) и наоборот. Таким образом, классы контрольных экспериментов для детерминированного дерева относительно классов Г(М) и К(М) совпадают. В тоже время, контрольный эксперимент для произвольного дерева Те ДМ) относительно класса К(М)-Т(М) может не являться таковым относительно класса 7 (М).
Также в настоящей главе рассматривается задача контроля изоморфной вложимости для детерминированных деревьев. Показывается, как контрольный эксперимент для эталон а-дерева может быть использован для проверки изоморфной вложимости в него исследуемого графа из класса К(М) и изоморфной вложимости этого эталона в исследуемый граф из класса ДМ).
В этом разделе исследованы условия бесконечности, конечности и пустоты классов ДМ), К(М) и /Г(М)-ДМ), и рассмотрена задача построения контрольного эксперимента для эталона, являющегося деревом, относительно класса /Г(М). Найден конструктивный критерий того, что заданное непустое конечное множество слов в алфавите М является контрольным экспериментом для заданного эталона-дерева относительно класса К(Ш). Предложен способ построения таких экспериментов квадратичной сложности от числа вершин эталона. Установлено, что контрольный эксперимент для эталона Те ДМ) относительно класса ДМ) является также контрольным экспериментом для Т относительно класса К(Ш) и наоборот.
Прежде всего, исследуем условия бесконечности, конечности и пустоты классов ДМ), К(Щ и ATM)-ДМ).
Теорема 2.1.1. Класс ДМ) конечен, когда М=1, и бесконечен, когда М 2. Доказательство: По определению М 0. При М=1 класс ДМ), в силу требования детерминированности, состоит из двух деревьев с числом вершин один и два, соответственно, и, следовательно, он конечен.
Пусть М[ 2. Построим дерево Т, состоящее из / вершин go,..-,gM, ET={ gi,giH 0 i /-2}, Хт={х ,х"}, х ,х"єМ, xVx", u(gi)=x для всех і, 0 і /-1, таких, что либо і, либо (і-1) кратно четырем, и [i(gi)=xM для всех і, 2 І М, таких, что либо (і-2), либо (і-3) кратно четырем. Очевидно, что Тє ДМ) и, в силу произвольности /, класс ДМ) бесконечен. Теорема доказана.
Теорема 2.1.2. Класс ATM)-ДМ) бесконечен при М 2 и пуст при [М[=1. Доказательство: Пусть М=1. Предположим, что класс К(М) Т(М) не пуст и G — произвольный граф из этого класса. Тогда, поскольку граф G содержит, по крайней мере, один цикл, в нем найдется вершина g такая, что 0(g) 2. Следовательно, в множестве 0(g) найдется пара вершин с одинаковыми отметками, что противоречит детерминированости графа G. Полученное противоречие доказывает, что класс ATM)-ДМ) пуст.
Пусть М 2 и / — произвольное натуральное число. Построим граф G, EG={ gi,gi+i 0 i 4/-2}u{ g0,g4M }, XG={x ,x"}, х ,х"єМ, хУх", ц(&)=х для всех і, 0 і 4/-1, таких, что либо і, либо (і-1) кратно четырем, и u.(gi)=xM для всех і, 2 і 4/-1, таких, что либо (І-2), либо (і-3) кратно четырем. Очевидно, что G є ATM)-ДМ) и, в силу произвольности /, класс ATM)-ДМ) бесконечен. Теорема доказана. Непосредственно ш теорем 2.1.1 и 2.1.2 вытекает справедливость следующего следствия. Следствие 2.1.1. Класс К(М) конечен, когда М=1, и бесконечен, когда М 2. Теоремы 2.1.1, 2.1.2 и следствие 2.1.1 являются конструктивными критериями конечности н бесконечности классов ДМ), АГ(М)-ДМ) и ATM), соответственно. Рассмотрение задачи построения контрольного эксперимента для детерминированного дерева начнем с рассмотрения ряда его важных свойств, используемых в дальнейшем. Лемма 2.1.1. Если РсМ+ — контрольный эксперимент для эталона ТєДМ) относительно класса ATM), то R(B[P]) включает E[V(T)Mi]. Доказательство. Пусть Р - контрольный эксперимент. Тогда, по следствию 1.3.3 и следствию 1.3.4, R(E[P]) также является контрольным экспериментом. Предположим, что в B[V(T)M]] найдется слово со, не входящее в R(B[P]). Если meLj, то саєУ(Т) и, следовательно, в B[V(T)Mi] найдется слово и такое, что uLT и юєЯ(и). Понятно, что uR(B[P]). Без ограничения общности будем полагать, что toLT- Рассмотрим дерево Т такое, что E[Lj ]=B[Z,T] {co}. Нетрудно видеть, что Т получается из Т добавлением к нему одной вершины и одного ребра. Тогда, поскольку R(B[P]) состоит только из безреверсных слов и слово со также, очевидно, безреверсное, то R(E[P])nIT =R(E[P])nB[IT- ]=R(E[P])nB[Lr]. Так как Т неизоморфно Т, то R(E[P]) не является контрольным экспериментом для Т относительно К(М). Полученное противоречие доказывает лемму.
Структура класса маркированных графов
В этой главе вводится специальный, возможно, бесконечный класс K(M,U), где U с М, графов из К(М), в каждом из которых любой отметкой иєТІ отмечена не более чем одна вершина, причем множество U заранее известно. Элементы множества U назовем маркерами, а любой граф из класса K(M,U), содержащий, по крайней мере, одну маркированную вершину, -маркированным графом. Класс всех маркированных графов обозначен через (M,U).
В главе исследуются свойства класса K(M,\J), его подклассов и его дополнение до класса К(М). Найдены конструктивные критерии пустоты, конечности и бесконечности этих классов в терминах свойств множества маркеров.
Установлено, что любой маркированный граф является приведенным, и любые два маркированных графа изоморфны тогда и только тогда, когда представимые ими языки совпадают.
Далее рассмотрена задача существования и построения контрольных экспериментов для различных эталонов из классов K(M,V)t A"m(M,U) и ЩМ)-Л (М,и) относительно различных подклассов класса К(М). Особое внимание уделено построению контрольных экспериментов для эталона из /fm(M,U) относительно класса К(М,И). Предложено несколько способов построения таких экспериментов, различающихся использованием априорной информации о графе-эталоне. В случае, когда эталон задан полностью, эти способы позволяют строить контрольный эксперимент длины О(п), кратности 0(гґ) и объема 0(п ), где п - число вершин эталона.
Понятие маркера было впервые введено в работе [43] при построении контрольных экспериментов для конечных автоматов. Там же были введены классы, аналогичные классам, введенным в настоящей главе, В дальнейшем маркеры были подробно рассмотрены в работе [40]. В настоящей главе понятие маркера переносится на графы с отмеченными вершинами, т.е. на объекты совершенно другой природы.
В этом разделе исследуется структура классов A"(M,U), Km(M,V), A MJ-AlfMJJ) и их интересных подклассов. Найдены конструктивные критерии пустоты, конечности и бесконечности этих классов.
Пусть G - граф из класса А(М), XQ - множество отметок всех вершин графа G и UGCXG - множество всех таких отметок х, для которых существует единственная вершина geSo такая, что u.(g)-x. Произвольно зафиксируем множество UcrM. Пусть U(G)=UriXG. Через K(M,V) обозначим класс всех тех графов G из класса К(М% для которых U(G)cUG. Элементы множества U назовем маркерами. Вершину g графа G, отмеченную некоторым маркером, назовем маркированной вершиной. Легко показать, что для любого U класс A(M,U) не пуст, и при пустом U совпадает с классом А М). Через A m(M,U) обозначим подкласс класса АГ(М), состоящий из всех таких графов G, что U(G)CZUG И U(G) 0. Очевидно, что A"m(M,U) является также подклассом класса K(M,XJ) и состоит из всех графов класса /f(M,U) содержащих, по крайней мере, одну маркированную вершину. Класс A m(M,U) назовем классом маркированных графов. Не трудно видеть, что класс A"m(M,U) не пуст точно тогда, когда U не пусто.
Просмотром графа GeAr(M) легко проверить, входит этот граф в классы AT(M,U) или A m(M,U), или не входит ни в один из этих классов. Поэтому классы A(M,U) и A"m(M,U) рекурсивны. Граф G из класса K(M,V) будем называть насыщенным, если U(G)-U. Очевидно, что для всех U таких, что U 1, насыщенный граф содержит не менее U вершин, и найдется насыщенный граф, содержащий ровно U вершин.
Обозначим через Кц(М,\3) подкласс всех насыщенных графов из #(M,U). Ясно, что если U не пусто, то ЯГц(М}и)с/Гт(М,и). Через ЛГ(М,п) обозначим подкласс графов из К(М), число вершин которых не превосходит п. Пусть K(M,\J)=K(M)-K(M,IJ). Пустой класс будем считать конечным.
Доказательство: При U=0 очевидно, что K(M,U)=Kn(M,U)=K(M), Следовательно, A(M,M)cff(M,U) и JT(M,U)=0. Пусть М1=1. Тогда класс К(М) состоит из двух графов с числом вершин один и два, соответственно. Поэтому ЛГ(М)=Л (М,2). Если при этом U не пусто, то U совпадает с М,/Г(М,и)=Л (М,1)=ЛГ,,(М,и) и A (M,U)=jr(M,2)-A(M,l). Таким образом, утверждение 3) влечет утверждения 1), 2) и 4).
Покажем, что каждое из утверждений I), 2) и 4) влечет утверждение 3). Пусть 3) не выполняется, т.е. М 2 и U не пусто. Тогда в ЛГ(М,2) найдется такой граф G, что число его вершин равно двум, а отметки этих вершин совпадают и принадлежат U. Очевидно, что GK(Mt\J). Следовательно, утверждение 2) влечет утверждение 3). Если U=M, то любой граф, состоящий из одной вершины, принадлежит классу /f(M,U) и не принадлежит классу AH(M,U). Следовательно, при U=M утверждение 1) влечет утверждение 3). Если и М, то граф, состоящий из одной вершины с отметкой из M-U, очевидно, принадлежит классу ЛГ(М,Ц), но не является насыщенным.
Следовательно, при U M утверждение 1) также влечет утверждение 3). Построим граф G, состоящий из / вершин g0,...,gM, Ec}={ gi,gi+i l 0 i /-2}, XG={X,5X"}, причем x eU, p(gi)=x для всех і, 0 і /-1, таких, что либо і, либо (і-1) кратно четырем, и u,(g;)=x" для всех і, 2 і /-1, таких, что либо (і-2), либо (і-3) кратно четырем. При любых ї 2 граф G принадлежит классу К(М, U), и, следовательно, это класс содержит бесконечное число графов. Таким образом, утверждение 4) влечет утверждение 3). Теорема полностью доказана.
Положим KK(M,U)=K(M,U)-KJM,U). Класс ATN(M,U) состоит из всех графов класса К(М), не имеющих маркированных вершин, т.е. для любого графа G из класса /TN(M,U) справедливо равенство XGnU=0. Следовательно, класс JSTN(M,U) пуст при M=U, и i rN(M,U)cJr(M-U) при M U. С другой стороны, при M U любой граф из класса A"(M-U) принадлежит классу /T(M,U), не принадлежит классу ATm(M,U) и, следовательно, принадлежит классу /Гк(М,1Г). Таким образом, справедливо следующее
Автоматы, реализующие контрольный эксперимент
В этой главе рассматривается задача синтеза конечного автомата, реализующего контрольный эксперимент для заданных графа-эталона и класса исследуемых графов. Этот автомат, взаимодействует с исследуемым графом как с лабиринтом [3-5].
Задачу синтеза можно сформулировать следующим образом. Для произвольного графа-эталона G из класса К(Ш) требуется построить конечный автомат /4(G), который, взаимодействуя с произвольным графом Н из класса FQK(M), через конечное число шагов определяет: Н изоморфен эталону или нет. Такой автомат может блуждать по графу, перемещаясь по его рёбрам из вершины в вершину. В каждый момент времени автомат находится в некоторой вершине и способен пользоваться некоторой локальной относительно этой вершины информацией для выбора следующей вершины, причём следующая вершина может быть выбрана только из вершин, смежных текущей. Кроме того, будем полагать, что автомат может оставлять в вершинах графа специальные дополнительные нестираемые отметки называемые красками (не уничтожая при этом основных отметок вершин) и, находясь в любой вершине, "видеть" основные и дополнительные отметки всех вершин, ей смежных.
В первом разделе этой главы для любого контрольного эксперимента Р для графа G относительно класса F предложен метод синтеза автомата (G,P) (без красок) с числом состояний 39(Р)+1, реализующий этот эксперимент не более чем за 29(Р) временных тактов, где 9(Р) - объем эксперимента Р.
Во втором разделе синтезируется автомат, осуществляющий окрашивание вершин исследуемого графа путем приписывания вершинам дополнительных отметок при сохранении исходных отметок вершин. Это дополнительное окрашивание позволяет осуществлять контроль графа даже в случае, когда контрольный эксперимент без дополнительного окрашивания не существует.
Под конечным автоматом А, будем понимать конечный, всюду определенный, инициальный автомат Мили [2] с заключительными состояниями, т.е семёрку А,В,8,ф,ч/,8е,5{) , где А и В - входной и выходной алфавиты, соответственно, S — конечное множество состояний, ф и \\f — функции переходов и выходов, соответственно, SecS — множество заключительных состояний, SoeS - начальное состояние. Перейдя в любое из заключительных состояний, автомат останавливается.
В настоящем разделе рассматривается задача синтеза автомата А(Т ) по заданному контрольному эксперименту Р для графа GeK(M) относительно непустого класса FciK(M). Автомат имеет два заключительных состояния st и Sf, определяющих результат эксперимента при взаимодействии А(Р) с произвольным графом Н из F. Состояние st означает, что ЬцпР-Ь г Р, т.е. графы G и Н изоморфны. Переход в состояние Sf означает, что это равенство не выполняется и тем самым графы G и Н неизоморфны. Для такого автомата Л(Р) будем говорить, что он реализует контрольный эксперимент Р для G относительно класса F.
Пусть Н - произвольный граф из класса Л (М) и оа=Х]...хр слово из М+. Сначала построим вспомогательный автомат А( й), взаимодействующий с графом Н и проверяющий принадлежность слова со языку ц. В начальный момент времени автомат устанавливается в инициальную вершину графа Н. Для перемещения по графу автомат должен иметь специально организованную структуру ввода-вывода. Входной алфавит А автомата А(о) определим как Мх2м, а выходной алфавит В положим равным множеству Ми{Л}. Вход и выход автомата Л(со) интерпретируются следующим образом. Находясь в i-ый такт времени в вершине h фафа Н, автомат получает на вход пару (а ,,а 0 є А, где a i=(i(h) — отметка вершины h, а2, — множество отметок всех вершин графа Н смежных вершине h. Выходной символ bj =B интерпретируется как команда автомату переместиться в вершину отмеченную символом bj, если Ь Л, или остаться в той же вершине при bj=A. На функцию выходов накладывается естественное ограничение: bjea ІЬ {Л}, гарантирующее при Ь, Л наличие среди вершин, смежных текущей, вершины с отметкой Ь[, причем в силу детерминированости фафа Н, такая вершина может быть только одна.
Определим множество состояний S автомата Л(со). Положим заключительном состоянии st3 точно тогда, когда соц. При этом автомат Л(со) всегда возвращается в инициальную вершину графа, т.е. завершает работу только в вершине h0 графа 1-І,
Пусть, теперь, G - граф-эталон из класса К(Ы), FcA"(M) - класс исследуемых графов, причем G не является предельным графом класса F. Пусть, далее, Р={соі,...,Сй/}сМ — контрольный эксперимент кратности / для графа G относительно класса F (согласно теореме 1.3.1 такой эксперимент существует). Построим автомат Л(Р), который, взаимодействуя с произвольным графом Н из класса F, через конечное число шагов определяет: изоморфен ли Н эталону G или нет.
Построение автомата А(Р) начнем с того, что для каждого слова со,єР, і=1,...,/, построим описанный выше автомат А( И\). Далее объединим полученные автоматы А((0\) в один автомат путем отождествления одного конечного состояния каждого автомата Л(со;), 1=1,...,/-1, с инициальным состоянием автомата Л(СОІ+]). Причем, для всех і=1,...,/-1 с инициальным состоянием (s0)i+i автомата Л(соі+і) отождествляется заключительное состояние (si )І автомата Л(соО, если u\eLG, или состояние (sj ),, если C0J G, " все отождествленные состояния исключаются из множества заключительных. Объявим заключительным состоянием st полученного автомата состояние (si )/ автомата Л(со/), если co/eZ-G или состояние (si )/, если (UI LQ. Все остальные заключительные состояния отождествим в одно заключительное состояние sf.
Полученный автомат, будучи помещенным в инициальную вершину исследуемого графа Н, блуждает по его ребрам от вершины к вершине, проверяя включение СОІЄІС для всех слов со; из контрольного эксперимента Р. Автомат всегда завершает свою работу только в инициальной вершине графа Н, причем равенство PnLc=Pr\LH (а, значит, G = Н) выполняется тогда и только тогда, когда автомат останавливается в заключительном состоянии st. В противном случае автомат останавливается в заключительном состоянии sp Таким образом, требуемый автомат A(V) построен.
