Комбинаторика. Применение графовых моделей Вариант 3. Решение задач по теории графов Вариант 3 Задание Определить Эйлерову цепь в неориентированном графе G, изображенном на рисунке. Решение

• Название: Решение задач по теории графов Вариант 3 Задание Определить Эйлерову цепь в неориентированном графе G, изображенном на рисунке. Решение
• Анкор: Комбинаторика. Применение графовых моделей Вариант 3
• Дата: 23.12.2022
• Размер: 82.04 Kb.
• Имя файла: 3.docx
• Тип: Решение; #860144
• страница: 5 из 5

Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,7*) = 213 + 6 = 219

Включение ребра (2,7) проводится путем исключения всех элементов 2-ой строки и 7-го столбца, в которой элемент d₇₂ заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	2	3	6	di
1	0	2	M	0
3	0	M	6	0
4	3	0	0	0
dj	0	0	0	0

Сумма констант приведения сокращенной матрицы:
∑d_i + ∑d_j = 0
Нижняя граница подмножества (2,7) равна:
H(2,7) = 213 + 0 = 213 ≤ 219
Чтобы исключить подциклы, запретим следующие переходы: (4,7), (4,2),
Поскольку нижняя граница этого подмножества (2,7) меньше, чем подмножества (2*,7*), то ребро (2,7) включаем в маршрут с новой границей H = 213

Шаг №5.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	2	3	6	di
1	0(2)	2	M	2
3	0(6)	M	6	6
4	M	0(2)	0(6)	0
dj	0	2	6	0

d(1,2) = 2 + 0 = 2; d(3,2) = 6 + 0 = 6; d(4,3) = 0 + 2 = 2; d(4,6) = 0 + 6 = 6;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (4,6), следовательно, множество разбивается на два подмножества (4,6) и (4*,6*).

Исключение ребра (4,6) проводим путем замены элемента d₄₆ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,6*), в результате получим редуцированную матрицу.

i j	2	3	6	di
1	0	2	M	0
3	0	M	6	0
4	M	0	M	0
dj	0	0	6	6

Нижняя граница гамильтоновых циклов этого подмножества:
H(4*,6*) = 213 + 6 = 219

Включение ребра (4,6) проводится путем исключения всех элементов 4-ой строки и 6-го столбца, в которой элемент d₆₄ заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	2	3	di
1	0	2	0
3	0	M	0
dj	0	2	2

Сумма констант приведения сокращенной матрицы:
∑d_i + ∑d_j = 2
Нижняя граница подмножества (4,6) равна:
H(4,6) = 213 + 2 = 215 ≤ 219
Поскольку нижняя граница этого подмножества (4,6) меньше, чем подмножества (4*,6*), то ребро (4,6) включаем в маршрут с новой границей H = 215
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (1,3) и (3,2).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(6,1), (1,3), (3,2), (2,7), (7,5), (5,4), (4,6),

Итог:
Длина маршрута равна F(Mk) = 215