Лаб_р_№4_на А4 (553878), страница 3

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

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

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. Во всяком ли связном графе существует Эйлеров путь?

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

Список файлов лабораторной работы