Главная страница
Навигация по странице:

  • Шаг №2

  • Исключение ребра

  • Включение ребра

    		•

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


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


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

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



    i j
    2
    3
    4
    5
    6
    7
    di

    1
    0
    2
    2
    11
    M
    21
    0

    2
    M
    0
    3
    14
    16
    0
    0

    3
    0
    M
    16
    14
    6
    6
    0

    4
    3
    0
    M
    16
    0
    9
    0

    5
    7
    12
    0
    M
    15
    0
    0

    7
    15
    7
    9
    0
    0
    M
    0

    dj
    0
    0
    0
    0
    0
    0
    0


    Сумма констант приведения сокращенной матрицы:
    ∑di + ∑dj = 0
    Нижняя граница подмножества (6,1) равна:
    H(6,1) = 213 + 0 = 213 ≤ 230
    Поскольку нижняя граница этого подмножества (6,1) меньше, чем подмножества (6*,1*), то ребро (6,1) включаем в маршрут с новой границей H = 213

    Шаг №2    .

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



    i j
    2
    3
    4
    5
    6
    7
    di

    1
    0(2)
    2
    2
    11
    M
    21
    2

    2
    M
    0(0)
    3
    14
    16
    0(0)
    0

    3
    0(6)
    M
    16
    14
    6
    6
    6

    4
    3
    0(0)
    M
    16
    0(0)
    9
    0

    5
    7
    12
    0(2)
    M
    15
    0(0)
    0

    7
    15
    7
    9
    0(11)
    0(0)
    M
    0

    dj
    0
    0
    2
    11
    0
    0
    0


    d(1,2) = 2 + 0 = 2; d(2,3) = 0 + 0 = 0; d(2,7) = 0 + 0 = 0; d(3,2) = 6 + 0 = 6; d(4,3) = 0 + 0 = 0; d(4,6) = 0 + 0 = 0; d(5,4) = 0 + 2 = 2; d(5,7) = 0 + 0 = 0; d(7,5) = 0 + 11 = 11; d(7,6) = 0 + 0 = 0;
    Наибольшая сумма констант приведения равна (0 + 11) = 11 для ребра (7,5), следовательно, множество разбивается на два подмножества (7,5) и (7*,5*).
    Исключение ребра (7,5) проводим путем замены элемента d75 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (7*,5*), в результате получим редуцированную матрицу.



    i j
    2
    3
    4
    5
    6
    7
    di

    1
    0
    2
    2
    11
    M
    21
    0

    2
    M
    0
    3
    14
    16
    0
    0

    3
    0
    M
    16
    14
    6
    6
    0

    4
    3
    0
    M
    16
    0
    9
    0

    5
    7
    12
    0
    M
    15
    0
    0

    7
    15
    7
    9
    M
    0
    M
    0

    dj
    0
    0
    0
    11
    0
    0
    11


    Нижняя граница гамильтоновых циклов этого подмножества:
    H(7*,5*) = 213 + 11 = 224
    Включение ребра (7,5) проводится путем исключения всех элементов 7-ой строки и 5-го столбца, в которой элемент d57 заменяем на М, для исключения образования негамильтонова цикла.
    В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
    После операции приведения сокращенная матрица будет иметь вид:



    i j
    2
    3
    4
    6
    7
    di

    1
    0
    2
    2
    M
    21
    0

    2
    M
    0
    3
    16
    0
    0

    3
    0
    M
    16
    6
    6
    0

    4
    3
    0
    M
    0
    9
    0

    5
    7
    12
    0
    15
    M
    0

    dj
    0
    0
    0
    0
    0
    0
    1   2   3   4   5

    написать администратору сайта