Т.Е. Бояринцева, А.А. Мастихина
2
(вершины — состояния, ребра — возможные переходы), то достижи-
мость означает, что можно попасть из одного фиксированного состо-
яния в другое. Рассматривается сведение подобных задач к операци-
ям с матрицами.
Второй раздел статьи имеет цель привнести элемент заниматель-
ности в преподавание предмета. Все необходимые сведения из тео-
рии графов и теории булевых функций содержатся в [1–4].
1. Компоненты связности графа; эйлеровы циклы.
Напомним,
что цикл в графе называется эйлеровым, если он проходит через каждое
ребро ровно один раз; если такой цикл существует, то граф называется
эйлеровым. Он характеризуется тем, что все его вершины имеют
четную степень. Исторический обзор задачи поиска эйлерова цикла
приведен в [5].
Следующий алгоритм Флери дает эйлеров цикл.
Исходя из произвольно выбранной вершины, идем по ребрам,
причем по мосту — только тогда, когда это неизбежно. Напомним,
что мост — это ребро, удаление которого увеличивает число связных
компонент.
Пройденные ребра за собой стираем.
Алгоритм заканчивает работу, когда ребер больше нет.
В таком виде алгоритм Флери не годится для реализации на
ЭВМ. Опишем матричную реализацию алгоритма Флери; она может
быть выполнена на ЭВМ. Для этого построим матрицу достижимости
графа, т. е. матрицу, в которой единицы на пересечении
i
-й строки и
j
-го столбца означают достижимость
i
-й вершины из
j
-й.
Пусть
A
— матрица смежности графа
G
, в которой на главной диа-
гонали стоят единицы. Такую матрицу смежности можно считать мат-
рицей достижимости не более чем за один шаг — на пересечении
i
-й
строки и
j
-го столбца стоит единица, если
i
-я и
j
-я вершины соединены
ребром, и каждая вершина достижима из себя же. Используем логиче-
ское умножение матриц (матрицы перемножаются как обычно, но в хо-
де вычислений все положительные числа заменяются на единицу).
То есть при таком перемножении матриц
n
n
результирующая матрица
C = A
B
получается по правилу
1, ...,
max
.
ik kj
ij
k
n
a b
с
Последователь-
но находим степени
A
,
A
2
, …, применяя описанное умножение. Едини-
цы в
k
-й степени матрицы будут означать существование пути длины
k
.
Например, матрица
A
2
— матрица достижимости не более чем за
два шага (причем отличные от нуля слагаемые при перемножении
i
-й
строки и
j
-го столбца соответствуют существующим вариантам путей
не более чем из двух ребер, соединяющих вершины
i
и
j
). Работа закан-
чивается на матрице
A
k
(с наименьшим
k
, для которого
A
k
=
A
k
+ 1
). Эта
матрица есть матрица достижимости графа
G
. (Отношение достижимо-
сти является рефлексивно-транзитивным замыканием отношения смеж-
ности.)
