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

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

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

  • Шаг №4

    		•

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


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


    Сумма констант приведения сокращенной матрицы:
    ∑di + ∑dj = 0
    Нижняя граница подмножества (7,5) равна:
    H(7,5) = 213 + 0 = 213 ≤ 224
    Поскольку нижняя граница этого подмножества (7,5) меньше, чем подмножества (7*,5*), то ребро (7,5) включаем в маршрут с новой границей H = 213
    Шаг №3.
    Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
    С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.



    i j
    2
    3
    4
    6
    7
    di

    1
    0(2)
    2
    2
    M
    21
    2

    2
    M
    0(0)
    3
    16
    0(6)
    0

    3
    0(6)
    M
    16
    6
    6
    6

    4
    3
    0(0)
    M
    0(6)
    9
    0

    5
    7
    12
    0(9)
    15
    M
    7

    dj
    0
    0
    2
    6
    6
    0


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

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



    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
    M
    15
    M
    7

    dj
    0
    0
    2
    0
    0
    9


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

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



    i j
    2
    3
    6
    7
    di

    1
    0
    2
    M
    21
    0

    2
    M
    0
    16
    0
    0

    3
    0
    M
    6
    6
    0

    4
    3
    0
    0
    9
    0

    dj
    0
    0
    0
    0
    0


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

    Шаг №4    .

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



    i j
    2
    3
    6
    7
    di

    1
    0(2)
    2
    M
    21
    2

    2
    M
    0(0)
    16
    0(6)
    0

    3
    0(6)
    M
    6
    6
    6

    4
    3
    0(0)
    0(6)
    M
    0

    dj
    0
    0
    6
    6
    0


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

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



    i j
    2
    3
    6
    7
    di

    1
    0
    2
    M
    21
    0

    2
    M
    0
    16
    M
    0

    3
    0
    M
    6
    6
    0

    4
    3
    0
    0
    M
    0

    dj
    0
    0
    0
    6
    6
    1   2   3   4   5

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