Т.Е. Бояринцева, А.А. Мастихина
4
лучим состав компоненты связности, содержащей первую строку.
Строки с номерами, попавшими в список достижимых вершин, мож-
но заменить на получившуюся первую строку. Далее ищем строку,
номер которой не попал в этот список, и для нее проделываем ту же
процедуру, которая уже описана для первой строки. Снова получаем
список компоненты связности. Так поступаем до тех пор, пока все
вершины не окажутся в каком-либо из найденных списков. Количе-
ство списков есть количество компонент связности.
Пример 2.
Пусть граф задан матрицей смежности
1 0 0 0 1
0 1 0 0 1
.
0 0 1 1 0
0 0 1 1 0
1 1 0 0 1
A
Первая единица первой строки не меняет строку, следующая
единица встречается в пятом столбце. Первая строка становится
(1 1 0 0 1), а
D
1
= {1, 5}. Просматривая первую строку сначала, дохо-
дим до единицы во втором столбце. Теперь
D
1
= {1, 5, 2}, а первая
строка не изменилась от добавления единиц второй строки. Новых
единиц нет, компонента связности найдена. Повторяем процедуру
для третьей строки,
D
3
= {3, 4}. Компоненты связности получены.
Эта же процедура нахождения матрицы достижимости позволяет
выяснить, является ли данное ребро мостом. Достаточно удалить это
ребро и для полученного нового графа найти (тем же способом) компо-
ненты связности. Ребро будет мостом лишь в том случае, если при пе-
реходе к новому графу число компонент связности увеличилось.
В алгоритме Флери приходится многократно выяснять, является ли
очередное «испытуемое» ребро мостом. Выбираем ребро и пробуем его
удалить, стабилизируем матрицу смежности, анализируем полученное
число компонент связности. Если оно возросло, то восстанавливаем
удаленное ребро и ищем другое из той же вершины. Мы видим, что ал-
горитм Флери может сводиться к матричным вычислениям и в таком
модифицированном виде годится для реализации на ЭВМ.
При аудиторном рассмотрении данной задачи можно напомнить
студентам о популярной задаче «нарисуй, не отрывая карандаша».
Эта задача может быть решена с помощью теоремы Эйлера и алго-
ритма Флери. Собственно, большинство интуитивно решает эту зада-
чу правильно, начиная рисовать из точки, где сходится нечетное
количество линий, и при движении стараются не оставлять изолиро-
ванными фрагменты рисунка.
Большое количество задач поиска эйлерова цикла содержится
в [6].
