Глава іv. Некоторые приложения графов
§ 1. Эйлеровы графы. Алгоритм флери. Гамильтоновы
ГРАФЫ. МЕТОД РОБЕРТСА – ФЛОРЕСА
Эйлеровы графы
Цикл называется эйлеровым, если каждое ребро графа участвует в его образовании один раз.
Граф, содержащий такой цикл, называется эйлеровым.
Теорема. Граф является эйлеровым тогда и только тогда, когда он связен и степень каждой вершины графа есть четное число.
Эйлеровой цепью называется цепь, которая содержит все ребра данного графа G , но имеющая различные начало vi и конец vj.
Чтобы в графе существовала эйлерова цепь, необходимы его связность и четность степеней всех вершин, кроме начальной vi и конечной vj. Последние две вершины должны иметь нечетные степени: из vi мы лишний раз выходим, а в vj лишний раз входим.
В орграфе вместо эйлерова цикла рассматривают эйлеров контур, вместо эйлеровой цепи – эйлеров путь.
Рассмотрим задачу обхода эйлерова графа, т.е. задачу построения одного из существующих эйлеровых циклов (эйлеровых контуров).
Алгоритм Флери.
1. Произвольно
выбирают некоторую вершину v1
и ребро u1,
инцидентное v1.
Этому ребру присваивают номер 1.
Вычеркивают это ребро u1
и переходят в вершину v2
по ребру
.
2. Находясь в вершине vi , не следует выбирать ребро, соединяющее vi c v1 , если имеется возможность иного выбора; не следует выбирать ребро, которое является перешейком (т.е. ребром, при удалении которого граф, образованный не вычеркнутыми ребрами, распадается на две компоненты связности, каждая из которых имеет хотя бы по одному ребру).
3. После того как в графе будут занумерованы все ребра, образуется эйлеров цикл, причем порядок нумерации соответствует последовательности обхода ребер.
Пример. Построить эйлеров цикл в графе G , изображенном на рис. 5. 1.
□ Граф G
эйлеров, так как
,
и граф связный.
1. Выберем v1
и ребро
и присвоим ему номер 1, затем перейдем
в вершину vi
= v7
.
2. Находясь в v7, не выбираем вычеркнутое ребро 1. Из оставшихся трех
Рис. 5.1
ребер ни одно не
является перешейком, поэтому выбираем
любое, например,
,
присваиваем ему номер 2 и переходим в
вершину vi
= v6
.
3. После восьми шагов опять приходим в вершину v1 . Построенный цикл :
Но построенный
цикл не охватывает все ребра графа (рис.
5.1). Для выполнения этого условия можно
было взять ребро
,
присвоить ему номер 2 и перейти в
вершину vi
= v2
. Дальнейший
обход графа показан на рисунке
■
Аналогично алгоритм Флери используется для построения эйлерова контура. Орграф должен быть сильно связным. Иначе можно не вернуться в начальную вершину.
Эйлеров контур можно использовать при диагностировании микросхем памяти. Точнее, при выявлении отказов, вызванных взаимным влиянием запоминающих ячеек микросхемы при различных сочетаниях хранимой информации. Задача состоит в построении эйлерового обхода двоичного куба.