Дискретно-непрерывная математика (стр. 87 )

При заданном начальном состоянии s и произволь­ной ленте или конечной последовательности входов с по­мощью графа можно легко определить результирующее конечное состояние s' (после t переходов) и соответ­ствующую выходную последовательность y1,..., yt. Например, если в текущий момент машина находится в состоянии s1 и следующие пять входов равны 1, 1, 0, 1, 0, то она последовательно перейдет в состояние s3, s3, s4, s2, s3 и выходные сигналы будут равны с, а, b, а, а.

Отметим следующие классы задач, существующие в теории абстрактных машин.

1. Анализ реакции (переходов и выходов) заданной машины.

2. Синтез машины с заданными характеристиками реакций.

3. Приведение машины к более простой в некотором смысле эквивалентной форме.

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

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

Цепь Маркова формально можно определить как си­стему, которая состоит из

1) конечного множества S={s1, ..., sn} элементов, называемых состояниями,

2) n×n-матрицы переходов Р= { pij }, где pij— ве­роятность того, что в следующий момент наблюдения система будет находиться в состоянии sj при условии, что в текущий момент она находится в состоянии si. Конечно, требуется, чтобы выполнялось соотношение

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

Цепи Маркова соответствует ориентированный граф. Вершины графа определяются состояниями цепи. Каждой дуге из si в sj поставлено в соответствие число рij в слу­чае рij>0 (т. е. в случае, когда возможен одношаговый переход из si в sj. Граф цепи Маркова с пятью состояниями показан на рис. 5.69.

Рис. 5.69.

Если текущее состояние системы s2, то она переходит в состояние s3, s5 или остается в s2 с вероятностями 0,2; 0,3 и 0,5 соответствен­но. Другие дуги интерпретируются аналогично.

Качественную классификацию состояний или множеств состояний можно провести на основе структурных свойств графа без учета конкретных значений вероят­ностей (различаются только нулевые и ненулевые вероят­ности). Например, множество состояний Т S называется поглощающим, если ориентированный разрез {Т, S — Т}

является пустым (т. е. из состояний в Т нельзя попасть ни в какие другие состояния, не принадлежащие Т). В частности, отдельное состояние является поглощающим тогда и только тогда, когда pii= 1. Цепь Маркова называ­ется эргодической, если соответствующий граф сильно свя­зен. Таким образом, эргодическая цепь это такая цепь, для которой при любом текущем состоянии si существует ненулевая вероятность достижения любого другого со­стояния за соответствующее число шагов (переходов).

Эргодическая цепь называется регулярной, если суще­ствует положительное целое число t0 такое, что для лю­бых состояний si и sj (возможно i = j) есть путь из vi в vj , имеющий в точности t дуг для всех t≥t0. Цепь на рис. 5.70, а, например, является эргодической, но нерегулярной. (Действительно, если начать, скажем, с s1, то можно оказаться в s3 только после четного числа шагов.) В отличие от нее, цепь рис. 5.70, b регулярна.

Рис. 5.70.

Упражнения

26. Найти минимальное значение to, удовлетворяющее условию регулярности цепи рис. 5.70, b.

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

5.30. Группы и обыкновенные графы

Каждый обыкновенный граф обладает, по крайней мере, одним собственным изоморфизмом, а именно, тривиальным изоморфизмом, при котором каждая вер­шина и ребро соответствуют самим себе. Однако кроме изоморфизма тождественности можно установить и дру­гие виды собственного изоморфизма. Изоморфизм графа с самим собой называется автоморфизмом. Совокупность автоморфизмов графа образует группу, называемую группой графа. Такую группу всегда можно рассматри­вать как группу перестановок вершин графа. Авто­морфизмы многоугольника с 2п сторонами (п-угольника) образуют группу, которая называется группой диэдра порядка п. Группа автоморфизмов полного п-вершинного графа называется симметричной группой порядка п. По­рядок группы называется симметрическим числом графа. Задача о том, является ли каждая перестановочная группа в общем случае группой графа, до сих пор ие решена. Она возникает при определении числа неизо­морфных графов с заданной перестановочной группой.

Упражнение 28. Найти автоморфизмы графа рис. 5.71.

Pис. 5.71

Рассмотрим операцию сложения целых чисел по модулю заданного целого числа. Укажем с помощью графа отношения между элементами, входящими в вы­четы при добавлении ко всем этим элементам одного из них. Например, возьмем целые числа по mod 6. По­лучим вычеты 0, 1, 2, 3, 4 и 5. Добавим ко всем вычетам 4 и укажем полученные связи. Начнем с нуля. В результате получим два контура рис.5.72.

Рис. 5.72.

С другой стороны, умножение на 4 дает граф рис. 5.73.

Рис. 5.73

Точки 0, 2 и 4 называются фиксированными, так как они отображаются на себя. Аналогич­но можно получить граф для функции f(x) =ax+b mod 6, например, где а и b — элементы класса вычетов, а х принимает значение из этого же класса.

Упражнение 29. Нарисуйте графы, соответствующие возведению в квадрат и в куб каждого из вычетов по mod 6.

Замечание. Дробь 4/з mod 7 получается следую­щим образом. Сначала находится элемент х в классе вычетов, который после умножения на 3 дает 1 mod 7, т. е. 1/з ≡ mod 7; получаем, что x=5. Умножая 4×5, получим 6 mod 7. Следовательно, 4/3≡6 mod 7.

Упражнение 30. Получить граф класса вычетов по mod 7, отображенного в соответствии с f(x) = (2x+3)/(x+2).

Рассмотренные идеи приводят к графам, которые известны под названием цветных графов Кэли, или диаграмм Вениа. Начнем с некоторой конечной группы и выделим ее подмножество (например, множество элементов, которые формируют группу). Поставим в со­ответствие каждому элементу группы некоторую вершину и дугу, которая заканчивается'-в вершине, являющей­ся конечной точкой преобразования (например, умноже­ния или сложения), выполняемого элементом выделен­ного подмножества над рассматриваемым элементом.

Таким образом, каждая вершина является началь­ной для стольких дуг, сколько элементов содержится в рабочем подмножестве. Каждая дуга окрашивается в свой цвет, соответствующий цвету элемента рабочего подмножества. Заметим, что вершине соответствует петля, если воздействие тождественно. В результате формируется цветной граф Кэли. Известно, что такой граф связен тогда и только тогда, когда в процессе его получения образуется группа, т. е. существует путь между любой парой вершин, так как с помощью последователь­ных умножений на элементы подмножества любой рас­сматриваемый элемент можно преобразовать в любой другой. Таким образом, 4 не формирует группы, опре­деленной вычетами по mod 6 при сложении, так как соответствующий граф не связен.

Упражнение 31. Показать, что 5 является генератором такой группы, доказав, что соответствующий граф связен.

5.31. Построение деревьев минимальной общей длины

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

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

Для нахождения дерева минимальной общей длины пометим ребра в соответствии с увеличением их длины так, что длина еi меньше или равна ej, если i<j. После этого выберем е1 и добавим к этому ребру е2, если е2 не образует цикла с е1. Далее будем продолжать рас­смотрение ребер в порядке возрастания их индексов и выбирать ребро всякий раз, когда оно не образует цикла с уже выбранным множеством. В противном случае ребро отбрасывается. Во всех случаях после окончания такого процесса мы получим дерево мини­мальной общей длины.