Примеры решения задач
Пример 1. Привести примеры графов:
а) содержащих одновременно ЭЦ и ГЦ,
б) содержащих ГЦ и не содержащих ЭЦ,
в) содержащих ЭЦ и не содержащих ГЦ,
г) не содержащих ни ЭЦ и ГЦ.
На рис. 16.17 приведены примеры графов, соответствующих заданным в данном примере условиям. Для эйлеровых графов на рисунке стрелками показан порядок обхода ребер графа.
а б
в г
Рис. 16.17. Примеры эйлеровых и гамильтоновых графов
Пример 2. Для графа G = (X, U), заданного на рис. 16.17,в, построить ЭЦ, используя алгоритм Флери.
Решение: Из рисунка 16.17,в видно, что граф G ─ связный, поэтому переходим к алгоритму построения ЭЦ в графе.
1.1. Производим подсчет локальных степеней графа G. Все вершины имеют четные степени. Переходим к п. 1.2.
1.2. Выбираем вершину x1.
1.3. Выбираем ребро u(x1 – x4). Здесь и далее в алгоритме примем следующее обозначение: u(x1 – x4) = u14. Заносим его в список L и вычеркиваем из матрицы смежности R.
1.4. |L| m, где m ─ число ребер в графе G, переходим к п. 1.5.
1.5. Переходим к вершине x4.
2.3. Выбираем ребро u45.Заносим его в список L и вычеркиваем из матрицы смежности.
2.4. |L| m, переходим к п. 2.5.
2.5. Переходим к вершине x5.
3.3. Выбираем ребро u56 и заносим его в список L.
3.4. |L| m, переходим к п. 3.5.
3.5. Переходим к вершине x6.
4.3. Выбираем ребро u67 (ребро u61 не выбираем, поскольку в данный момент имеется возможность выбрать другое ребро).
4.4. |L| m, переходим к п. 4.5.
4.5. Переходим к вершине x7.
5.3. Выбираем ребро u73. Заносим его в список L.
5.4. |L| m, переходим к п. 5.5.
5.5. Выбираем вершину x3.
6.3. Выбираем ребро u34, и заносим его в список L.
6.4. |L| m, переходим к п. 6.5.
6.5. Выбираем вершину x4.
7.3. Выбираем ребро u46, заносим его в список L.
7.4. |L| m, переходим к п. 7.5.
7.5. Выбираем вершину x6.
8.3. Поскольку иных вариантов нет, выбираем ребро u61.
8.4. |L| m, переходим к п. 8.5.
8.5. Выбираем вершину x1.
9.3. Выбираем ребро u12, заносим его в список L.
9.4. |L| m, переходим к п. 9.5.
9.5. Выбираем вершину x2.
10.3. Выбираем ребро u25, заносим его в список L.
10.4. |L| m, переходим к п. 10.5.
10.5. Выбираем вершину x5.
11.3. Выбираем ребро u58, заносим его в список L.
11.4. |L| m, переходим к п. 11.5.
11.5. Выбираем вершину x8.
12.3. Выбираем ребро u81, заносим его в список L.
12.4. |L| = m, переходим к п. 12.6.
12.6. Построен ЭЦ (u14 – u45 – u56 – u67 – u73 – u34 - u46 – u61 – u12 – u25 – u58 – u81).
Поставленная задача выполнена. Работа алгоритма закончена.
Пример 3. Привести пример гамильтонова графа и показать на нем порядок обхода вершин.
Решение: На рис. 16.18 показан граф G, в котором имеется гамильтонов цикл. Ребра, входящие в гамильтонов цикл, выделены жирной линией. Последовательность обхода вершин графа в гамильтоновом цикле может быть следующей: ГЦ = (x1 ─ x2 ─ x15 ─ x13 ─ x18 ─ x16 ─ x14 ─ x6 ─ x7 ─ x17 ─ x20 ─ x19 ─ x11 ─ x12 ─ x3 ─ x4 ─ x10 ─ x9 ─ x8 ─ x5 ─ x1).
Рис. 16.18. Пример гамильтонова цикла в графе