Задать вопрос юристу

3.3.3. Минимальные остовные деревья нагруженных графов

Пусть теперь каждому ребру x Î X связного графа G=(V,X) c непустым множеством ребер Х поставлена в соответствие величина l(x) – длина ребра х, т.е. граф G является нагруженным. Приведем алгоритм, позволяющий найти остовное дерево графа G с минимальной суммой длин содержащихся в нем ребер (по сравнению со всеми другими остовными деревьями графа G).

Определение. Остовное дерево связного нагруженного граф G с минимальной суммой длин содержащихся в нем ребер будем называть минимальным остовным деревом (МОД) графа G.

Алгоритм выделения МОД нагруженного связного графа G:

Шаг 1. Выберем в графе G ребро минимальной длины. Вместе с инцидентными ему вершинами оно образует подграф G2 графа G. Положим i=2.

Шаг 2. Если i=n, где n=n(G), то задача решена, и Gi – искомое МОД графа G. В противном случае переходим к шагу 3.

Шаг 3. Строим граф Gi+1, добавляя к графу Gi новое ребро минимальной длины, выбранное среди всех ребер графа G, каждое из которых инцидентно к какой-нибудь вершине графа Gi и одновременно инцидентно какой-нибудь вершине графа G, не содержащейся в Gi. Вместе с этим ребром включаем в Gi+1 и инцидентные ему вершины, не содержащуюся в Gi . Присваиваем i:=i+1 и переходим к шагу 2.

Пример 89.

Определить МОД нагруженного графа G, изображенного на рисунке 41, используя алгоритм.

Решение.


На рисунке 42 приведена последовательность графов Gi, i=2,3,4,5, получаемых в результате выполнения алгоритма. При этом в силу того, что n(G)=5, G5 - МОД графа G. Причем, МОД(G) = 7.

Замечание. Возможно выделить в графе несколько остовных деревьев, каждое из которых будет являться минимальным, при этом величина МОД для всех этих деревьев будет равной.

Замечание. Для выделения МОД нагруженного псевдографа G следует предварительно удалить из G петли, из кратных ребер оставить лишь ребра минимальной длины.

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 3.3.3. Минимальные остовные деревья нагруженных графов:

  1. 3.3.2. Остовное дерево связного графа
  2. 3.2.3. Нахождение минимального пути в нагруженном графе
  3. § 5. Минимальная потребительская корзина, минимальный потребительский бюджет их взаимосвязь с оплатой труда
  4. 3.1. Элементы теории графов
  5. Деревья и циклы.
  6. Изоморфизм графов
  7. В.Н. Бурков, Д.А. Новиков. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ, 2001
  8. 6.2.2 Применение теории графов
  9. 3. ТЕОРИЯ ГРАФОВ
  10. 1. Основные понятия теории графов
  11. 3.1.4. Примеры графов. Операции над графами
  12. Матрицы графов.
  13. ряд примеров приложений теории графов.
  14. Кодировка дерева
  15. 3.1.3. Матричное задание графов. Матрицы смежности, инцидентности
  16. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
  17. §2.2. Способы задания графов
  18. §2.4. Раскраски графов. Планарность
  19. 2 Элементы теории графов
  20. 3.2. Выбор и постановка краевой задачи о невесомой плоскости, с заданными на бесконечности напряжениями, моделирующими гравитационное поле, и ослабленной круглым отверстием, равномерно нагруженным по контуру и моделирующим закрепленную подземную выработку