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

  • Алгоритм выделения Эйлерова цикла в связном мультиграфе

  • 2.7.6. Минимальное остовное дерево (Алгоритм Краскала)

    		•

    Теория графов. 02 Теория графов. 2. теория графов общие понятия теории графов


    Скачать 1.41 Mb.
    Название2. теория графов общие понятия теории графов
    АнкорТеория графов
    Дата30.09.2022
    Размер1.41 Mb.
    Формат файлаpdf
    Имя файла02 Теория графов.pdf
    ТипДокументы
    #706797
    страница8 из 8
    1   2   3   4   5   6   7   8
    2.7.5. Эйлеровы циклы и цепи
    Найти Эйлерову цепь в неориентированном псевдографе.
    Исходя из утверждений 1 и 2 (подглава 2.2), чтобы найти
    Эйлерову цепь, нужно соединить две вершины с нечетными степенями фиктивным ребром. Тогда задача сводится к нахождению
    Эйлерова цикла по приведенному ниже алгоритму. Из найденного цикла удаляется фиктивное ребро, тем самым находится искомая
    Эйлерова цепь.
    Алгоритм выделения Эйлерова цикла в связном мультиграфе
    с четными степенями вершин
    1. Выделим из G цикл µ
    1
    (так как степени вершин четны, то висячие вершины отсутствуют). Положим l = 1, G′ = G.
    2. Удаляем из G′ ребра, принадлежащие выделенному циклу µ
    1
    Полученный псевдограф снова обозначаем как G′. Если в G′ отсутствуют ребра, то переходим к шагу 4. Если ребра есть, то выделяем из G′ цикл µ
    l+1
    и переходим к шагу 3.
    3. Присваиваем l: = l + 1 и переходим к шагу 2.

    67 4. По построению выделенные циклы содержат все ребра по одному разу. Если l = 1, то искомый Эйлеров цикл найден (конец работы алгоритма). В противном случае находим циклы, содержащие хотя бы по одной общей вершине (в силу связности графа это всегда можно сделать). Склеиваем эти циклы. Повторяем эти операции, пока не останется один цикл, который является искомым.
    Пример
    Найдем Эйлерову цепь в неориентированном графе G (рис.
    2.40).
    Прежде чем приступать к нахождению Эйлеровой цепи, необходимо проверить степени вершин графа G. Согласно утверждению 2, для существования Эйлеровой цепи необходимо и достаточно, чтобы в графе G было ровно две вершины нечетной степени.
    Рис. 2.40. Граф для поиска Эйлеровой цепи
    В рассматриваемом графе нечетные степени имеют вершины v
    3
    и v
    1
    (степень этих вершин равна 3). Соединяя эти вершины фиктивным ребром так, как показано на рис.
    2.41, получаем граф G′.
    Рис. 2.41. Введение фиктивного ребра в неориентированном графе
    Поскольку в конечном итоге будет получена цепь, то очевидно, что началом и концом этой цепи будут вершины с нечетными степенями. Поэтому, следуя описанному выше алгоритму, будем выделять циклы µ
    i
    так, чтобы хотя бы один из них начинался или кончался на вершинах v
    3
    или v
    1

    68
    Пусть цикл µ
    1
    составят ребра, проходящие через следующие вершины:
    µ
    1
    : v
    3
    v
    4
    v
    7
    v
    6
    v
    1
    v
    2
    v
    3
    Согласно алгоритму, удаляем из G′все ребра, задействованные в цикле µ
    1
    . Теперь граф G′ будет таким, как показано на рис.
    2.42,
    а.
    Выделяем следующий цикл µ
    2
    µ
    2
    : v
    4
    v
    5
    v
    6
    v
    2
    v
    5
    v
    7
    v
    4
    Граф G′ после удаления ребер, составляющих цикл µ
    2
    , изображен на рис.
    2.42,
    б.
    а
    б
    Рис. 2.42. Выделение циклов и удаление составляющих их ребер:
    а – удаление цикла µ
    1
    ;
    б – удаление цикла µ
    2
    Очевидно, что последний цикл µ
    3
    будет состоять из оставшихся вершин и ребер
    µ
    3
    : v
    3
    v
    5
    v
    1
    |v
    3
    , где последнее ребро, соединяющее вершины v
    1
    и v
    3
    – фиктивно.
    После удаления ребер, составляющих цикл µ
    3
    , в графе G′ не останется ни одного ребра.
    Теперь по общим вершинам склеиваем полученные циклы.
    Поскольку µ
    1
    и µ
    2
    имеют общую вершину v
    4
    , то, объединяя их, получим следующий цикл:
    v
    3
    v
    4
    v
    5
    v
    6
    v
    2
    v
    5
    v
    7
    v
    4
    v
    7
    v
    6
    v
    1
    v
    2
    v
    3
    Теперь склеим получившийся цикл с циклом µ
    3
    :
    v
    3
    v
    4
    v
    5
    v
    6
    v
    2
    v
    5
    v
    7
    v
    4
    v
    7
    v
    6
    v
    1
    v
    2
    v
    3
    v
    5
    v
    1
    |v
    3
    Удаляя фиктивное ребро, получаем искомую Эйлерову цепь:
    v
    3
    v
    4
    v
    5
    v
    6
    v
    2
    v
    5
    v
    7
    v
    4
    v
    7
    v
    6
    v
    1
    v
    2
    v
    3
    v
    5
    v
    1

    69
    2.7.6. Минимальное остовное дерево (Алгоритм Краскала)
    Алгоритм выделения минимального остовного дерева
    в неориентированном нагруженном графе G
    1. Выберем в графе G ребро минимального веса. Вместе с инцидентными ему двумя вершинами оно образует подграф G
    2
    графа G. Положим i = 2.
    2. Если i = n(G), то задача решена, и G
    i
    – искомое минимальное остовное дерево графа G. Иначе переходим к шагу 3.
    3. Строим граф G
    i+1
    . Для этого добавим к графу G
    i
    новое ребро минимального веса из оставшихся, которое инцидентно какой- либо вершине графа G
    i
    и одновременно вершине, не содержащейся в G
    i
    . Вместе с этим ребром включаем в G
    i+1
    и эту инцидентную ему вершину. Присваиваем i: = i + 1 и переходим к шагу 2.
    Пример
    Найдем минимальное остовное дерево в неориентированном нагруженном графе, изображенном на рис.
    2.43.
    Рис. 2.43. Поиск минимального остовного дерева в неориентированном нагруженном графе
    Обозначим ребро, соединяющее вершины v
    i
    и v
    j
    через x
    ij
    Для удобства использования приведенного выше алгоритма решения поставленной задачи составим матрицу длин ребер.
    В рассматриваемом графе количество вершин n = 8, следовательно, матрица длин ребер графа G будет иметь размерность 8 × 8 и выглядеть следующим образом:

    70


























    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    ∞
    =
    9 8
    7 9
    6 4
    1 6
    11 3
    8 4
    11 14 12 5
    2 1
    3 14 10 8
    7 12 3
    5 10 3
    2 2
    8 2
    )
    (G
    C
    Согласно приведенному выше алгоритму, выбираем ребро минимальной длины (веса) (выбираем среди элементов матрицы
    C(G), минимальное − это c
    47
    = 1) и вместе с инцидентными ему двумя вершинами относим к графу G
    2
    . Таким образом,
    {
    } { }
    (
    )
    47 7
    4 2
    ,
    ,
    x
    v
    v
    G =
    Длина дерева G
    2
    будет равна l(G
    2
    ) = c
    47
    = 1. Поскольку
    )
    (
    2
    G
    n
    i
    ≠
    =
    , то продолжаем работу алгоритма.
    По четвертой и седьмой строкам ищем минимальное число (за исключением использованной единицы) − ребро минимальной длины, инцидентное либо вершине v
    4
    , либо v
    7
    . Выбираем ребро x
    46
    с длиной c
    46
    = 3 и вместе с вершиной v
    6
    добавляем к графу G
    2
    , обозначая его теперь как G
    3
    :
    {
    } {
    }
    (
    )
    46 47 7
    6 4
    3
    ,
    ,
    ,
    ,
    x
    x
    v
    v
    v
    G =
    , при этом
    l(G
    3
    ) = c
    47
    + c
    46
    = 1+3 = 4.
    Аналогично находим последующие графы:
    {
    } {
    }
    (
    )
    75 46 47 7
    6 5
    4 4
    ,
    ,
    ,
    ,
    ,
    ,
    x
    x
    x
    v
    v
    v
    v
    G =
    ,
    8 4
    4
    )
    (
    )
    (
    75 3
    4
    =
    +
    =
    +
    =
    c
    G
    l
    G
    l
    ;
    {
    } {
    }
    (
    )
    51 75 46 47 7
    6 5
    4 1
    5
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    x
    x
    x
    x
    v
    v
    v
    v
    v
    G =
    ,
    10 2
    8
    )
    (
    )
    (
    51 4
    5
    =
    +
    =
    +
    =
    c
    G
    l
    G
    l
    ;
    {
    } {
    }
    (
    )
    12 51 75 46 47 7
    6 5
    4 2
    1 6
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    x
    x
    x
    x
    x
    v
    v
    v
    v
    v
    v
    G =
    ,
    12 2
    10
    )
    (
    )
    (
    12 5
    6
    =
    +
    =
    +
    =
    c
    G
    l
    G
    l
    ;
    {
    } {
    }
    (
    )
    23 12 51 75 46 47 7
    6 5
    4 3
    2 1
    7
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    x
    x
    x
    x
    x
    x
    v
    v
    v
    v
    v
    v
    v
    G =
    ,
    15 3
    12
    )
    (
    )
    (
    23 6
    7
    =
    +
    =
    +
    =
    c
    G
    l
    G
    l
    ;
    {
    } {
    }
    (
    )
    38 23 12 51 75 46 47 8
    7 6
    5 4
    3 2
    1 8
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    ,
    x
    x
    x
    x
    x
    x
    x
    v
    v
    v
    v
    v
    v
    v
    v
    G =
    ,
    22 7
    15
    )
    (
    )
    (
    38 7
    8
    =
    +
    =
    +
    =
    c
    G
    l
    G
    l
    Поскольку i = 8 = n(G), работа алгоритма заканчивается.
    Таким образом, искомое минимальное остовное дерево графа G − граф G
    8
    , изображенный на рис.
    2.44, длина которого равна 22.

    71
    Рис. 2.44.
    Искомое минимальное остовное дерево
    1   2   3   4   5   6   7   8

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