Лабораторная работа 4 ОТКДС (553864), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Для нахождения Эйлеровой линии на графе удобнее воспользоваться следующим алгоритмом (рассматривается неориентированный граф):

0. Задается начальный шаг итерации k =0. Проверяется условие существования Эйлерова пути. Задается начальная (она же и конечная) вершина Эйлерова пути V_{0 .} Если, например, V₀ = A₃, то это означает, что начальной вершиной Эйлерова пути на шаге k = 0 выбрана третья вершина графа.

1. k=k+1. Определяются все вершины, непосредственно связанные непомеченными ребрами с вершиной V_k-1.

2. Определяется число S_k этих непомеченных ребер. Если S_k= 1, то вторая вершина, инцидентная этому ребру, становится очередной вершиной V_k Эйлерова пути, и это ребро помечается. Возвращаемся на п. 1.

При S_k >1, среди вершин, смежных V_k-1, выбирается вершина с наименьшим номером k, которая становится очередной вершиной V_k Эйлерова пути. Ребро, соединяющее эту вершину с вершиной V_k-1, помечается. Возвращаемся на п. 1.

При S_k = 0, для каждой, уже найденной вершины, принадлежащей Эйлеровому пути и имеющей непомеченные инцидентные ребра, строится цикл по этим ребрам. Определение каждой вершины этого цикла начинается с п. 1.

Каждый построенный таким образом цикл объединяется с ранее построенными, и они образуют Эйлерову линию.

Отметим, что выбор вершины с наименьшим номером нужен для того, чтобы была определенность при выборе вершины на каждом шаге. Можно, однако, предложить выбор вершин и с наибольшим номером.

В качестве примера рассмотрим задачу нахождения Эйлеровой линии для графа (рис. 4.3) с начальной вершиной 3.

0. k = 0. Эйлерова линия существует, так как степени всех вершин четные. Выберем начальную вершину номер 3, т.е. V₀ = 3. Число непомеченных ребер n = 11.

1. k = 1. С вершиной 3 связаны вершины 1, 2.

2. S₁ = 2. Следующей вершиной Эйлерова пути является вершина 1. Ребро 3-1 помечается. Возвращаемся к 1.

1. k = 2. С вершиной 1 связаны вершины 2, 4, 6.

2. S₂ = 3. Вершина 2. Помечается ребро 1-2. Возвращаемся к 1.

1. k = 3. С вершиной 2 связаны вершины 3, 5, 7.

Рис. 4.3

2. S₃ = 3. Вершина 3. Помечается ребро 2-3. Возвращаемся к 1.

1. k = 4. С вершиной 3 связаны вершины 1, 2.

2. S₄ = 0. Вершин таких нет. Следовательно, получен цикл 3-1-2-3, который еще не является Эйлеровой линией.

Вершины 1 и 2, входящие в этот цикл, имеют непомеченные инцидентные ребра. Рассмотрим вершину 1 в качестве начальной точки следущего цикла A₄ = 1.

1. k = 5. Вершины 4, 6.

2. S₅ = 2. Вершина 4. Ребро 1-4.

1. k = 6. Вершина 5.

2. S₆ = 1. Вершина 5. Ребро 4-5.

1. k = 7. Вершины 2, 7, 8.

2. S₇ = 3. Вершина 2. Ребро 5-2.

1. k = 8. Вершина 7.

2. S₈ = 1. Вершина 7. Ребро 2-7.

1. k = 9. Вершины 5, 6, 8.

2. S₉= 3. Вершина 5. Ребро 7-5.

1. k = 10. Вершина 8.

2. S₁₀ = 1. Вершина 8. Ребро 5-8.

1. k = 11. Вершина 7.

2. S₁₁ = 1. Вершина 7. Ребро 8-7.

1. k = 12. Вершина 6.

2. S₁₂ = 1. Вершина 6. Ребро 7-6.

1. k = 13. Вершина 1.

2. S₁₃ = 1. Вершина 1. Ребро 6-1.

1. k = 14. Вершин, связанных непомеченными ребрами, нет.

2. S₁₄ = 0. В найденных циклах нет вершин, имеющих инцидентные непомеченные ребра. Следовательно, работа алгоритма заканчивается и для нахождения Эйлеровой линии необходимо объединить два найденных цикла 3-1-2-3 и 1-4-5-2-7-5-8-7-6-1 в вершине_1. Результатом объединения будет Эйлерова линия 3-1-4-5-2-7-5-8-7-6-1-2-3.

Контрольные вопросы

1. Как определить по матрице смежности начальные и конечные вершины графа?

2. Какое максимальное число классов эквивалентности может быть в графе?

3. Чему равно число Гамильтоновых путей в насыщенном графе?

4. Что такое связный граф?

5. Как по матрице смежности неориентированного графа определить существование Эйлерова пути?

6. Во всяком ли связном графе существует Эйлеров путь?

Характеристики

Список файлов книги