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

  • H

  • Шаг №1

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

    		•

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


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


    После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.



    i j
    1
    2
    3
    4
    5
    6
    7

    1
    -
    0
    2
    2
    11
    7
    21

    2
    0
    -
    0
    3
    14
    16
    0

    3
    13
    0
    -
    16
    14
    6
    6

    4
    18
    3
    0
    -
    16
    0
    9

    5
    2
    7
    12
    0
    -
    15
    0

    6
    0
    25
    17
    22
    17
    -
    19

    7
    3
    15
    7
    9
    0
    0
    -


    Сумма констант приведения определяет нижнюю границу H:
    H = ∑di+ ∑dj
    H = 29+31+30+25+33+25+33+0+0+3+0+4+0+0 = 213
    Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
    Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij ≥ 0
    Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
    Длина маршрута определяется выражением:
    F(Mk) = ∑dij
    Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.

    Шаг №1    .

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



    i j
    1
    2
    3
    4
    5
    6
    7
    di

    1
    M
    0(2)
    2
    2
    11
    7
    21
    2

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

    3
    13
    0(6)
    M
    16
    14
    6
    6
    6

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

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

    6
    0(17)
    25
    17
    22
    17
    M
    19
    17

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

    dj
    0
    0
    0
    2
    11
    0
    0
    0


    d(1,2) = 2 + 0 = 2; d(2,1) = 0 + 0 = 0; 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(6,1) = 17 + 0 = 17; d(7,5) = 0 + 11 = 11; d(7,6) = 0 + 0 = 0;
    Наибольшая сумма констант приведения равна (17 + 0) = 17 для ребра (6,1), следовательно, множество разбивается на два подмножества (6,1) и (6*,1*).

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



    i j
    1
    2
    3
    4
    5
    6
    7
    di

    1
    M
    0
    2
    2
    11
    7
    21
    0

    2
    0
    M
    0
    3
    14
    16
    0
    0

    3
    13
    0
    M
    16
    14
    6
    6
    0

    4
    18
    3
    0
    M
    16
    0
    9
    0

    5
    2
    7
    12
    0
    M
    15
    0
    0

    6
    M
    25
    17
    22
    17
    M
    19
    17

    7
    3
    15
    7
    9
    0
    0
    M
    0

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

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