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

Граф G = (X, A) называется нагруженным, если для каждого ребра (x_i,x_j) определена его длина (или вес) c_ij.

Пусть G - связный нагруженный граф. Задача построения минимально­го остовного деревазаключается в том, чтобы из множества остовных де­ревьев найти дерево, у которого сумма длин ребер минимальна.

Приведем типичные случаи, когда возникает необходимость построе­ния минимального остовного дерева графа.

а) Нужно соединить n городов железнодорожными линиями (автомобиль­ными дорогами, линиями электропередач, сетью трубопроводов и т.д.) так, чтобы суммарная длина линий или стоимость была бы минимальной.

б)Требуется построить схему электрической сети, в которой клеммы должны быть соединены с помощью проводов наименьшей общей длины.

Зада­чу построе­ния минимального остовного дерева можно решить с помощью следующего алгоритма.

Алгоритм 3.2 (Алгоритм Краскала).

Шаг 1. Установка начальных значений.

Вводится матрица длин ребер C графа G.

Шаг 2. Выбрать в графе G ребро минимальной длины. Построить граф G₂, состоящий из данного ребра и инцидентных ему вершин. Положить i = 2.

Шаг 3. Если i = n, где n - число ребер графа, то закончить работу (задача решена), в противном случае перейти к шагу 4.

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

Пример 3.19.

Найдем минимальное остовное дерево для графа, изображенного на рис. 3.14.

Рис. 3.14

Шаг 1. Установка начальных значений.

Введем матрицу длин ребер C:

С = .

Шаг 2. Выберем ребро минимальной длины. Минимальная длина ребра равна единице. Таких ребер три: (x₁, x₂), (x₁, x₄), (x₂, x₄). В этом случае можно взять любое. Возьмем (x₁, x₂). Построим граф G₂, состоящий из данного ребра и инцидентных ему вершин x₁ и x₂. Положим i = 2.

Шаг 3. Так как n = 5, то i ¹ n, поэтому переходим к шагу 4.

Шаг 4. Строим граф G_3, добавляя к графу G₂новое ребро мини­мальной длины, выбранное среди всех ребер графа G, каждое из которых инцидентно одной из вершин x₁, x₂ и одновременно инцидентно какой-нибудь вершине графа G, не содержащейся в G₂ т. е. одной из вершин x₃, x₄, x₅. Таким образом, нужно выбрать ребро мини­мальной длины из ребер (x₁, x₄), (x₁, x₅), (x₂, x₃), (x₂, x₄), (x₂, x₅). Таких ребер длины единица два: (x₁, x₄) и (x₂, x₄). Можно выбрать любое. Возьмем (x₁, x₄). Вместе с этим ребром включаем в G₃вершину x₄, не содержащуюся в G₂. Полагаем i =3 и переходим к шагу 3.

Шаг 3. Так как i ¹ n, поэтому переходим к шагу 4.

Шаг 4. Строим граф G_4, добавляя к графу G₃новое ребро мини­мальной длины из ребер (x₁, x₅), (x₂, x₃), (x₂, x₅), (x₄, x₅). Такое ребро длины два одно: (x₂, x₃). Вместе с этим ребром включаем в G₄вершину x₃, не содержащуюся в G₃. Полагаем i =4 и переходим к шагу 3.

Шаг 3. Так как i ¹ n, поэтому переходим к шагу 4.

Шаг 4. Строим граф G_5, добавляя к графу G₃новое ребро мини­мальной длины из ребер (x₁, x₅), (x₂, x₅), (x₄, x₅). Таких ребер длины три два: (x₂, x₅) и (x₄, x₅). Возьмем (x₂, x₅). Вместе с этим ребром включаем в G₅вершину x₅, не содержащуюся в G₄. Полагаем i =5 и переходим к шагу 3.

Шаг 3. Так как i = n, то граф G₅ – искомое минимальное остовное дерево. Суммарная длина ребер равна 1 + 1 + 2 + 3 = 7.

Процесс построения минимального остовного дерева изображен на рис. 3.15.

Рис. 3.15

Контрольные вопросы к теме 3

1. Какое из двух утверждений верно: а) ориентированный граф яв­ляется частным случаем неориентированного графа; б) неориентированный граф является частным случаем ориентированного графа?

2. Перечислите все возможные способы задания графов.

3. Что характеризует сумма элементов столбца матрицы смежности неориентированного графа?

4. Что характеризует сумма элементов строки матрицы смежности неориентированного графа?

5. Что характеризует сумма элементов столбца матрицы смежности ориентированного графа?

6. Что характеризует сумма элементов строки матрицы смежности ориентированного графа

7. Всегда ли матрица смежности симметрична относительно главной диагонали?

8. Как по матрице смежности определить число ребер неориентиро­ванного графа?

9. Как по матрице инцидентности, не рисуя граф, определить его матрицу смежности?

10. Может ли матрица быть матрицей смежности неориентированного графа?

11. Какие из следующих утверждений являются правильными: а) если матрица смежности несимметричная, то граф ориентированный; б) если граф неориентированный, то матрица смежности симметричная; в) если диагональные элементы матрицы смежности – нули, то граф неориентированный?

12. Может ли вершина, входящая в цикл графа, иметь степень, мень­шую двух?

13. Как называется путь, у которого начало первой дуги совпадает с концом последней?

14. Как называется маршрут, у которого первая вершина совпадает с последней?

15. Можно ли утверждать, что сильно связный граф всегда содержит контур?

16. Какие из следующих матриц полностью задают граф:

а) матрица инцидентности; б) матрица од­носторонней связности; в) матрица связности; г) матрица сильной связности; д) матрица смежности?

17. По какой матрице можно без дополнительных вычислений определить число компонент связности неориентированного графа: а) матрице смежности; б) матрице инциденций; в) матрице расстояний; г) матрице связности?

18. Может ли число компонент связности графа превосходить число его вершин?

19. Верно или неверно утверждение, что в ориентированном графе с контурами минимальный путь может содержать контуры?

20. Как называется связный граф без циклов?

21. Пусть n - число вершин, а m - число ребер в связном графе без циклов. Какие из следующих соотношений возможны:

а) n = m; б) n < m; в) n m; г) n > m; д) n m?

22. Сколько ребер имеет связный граф без циклов с n вершинами?

23. Чему равно наименьшее и наибольшее число ребер в связном гра­фе без петель и кратных ребер с n вершинами?

24. Чему равно наименьшее и наибольшее число ребер в графе без петель и кратных ребер с n вершинами?

25. Верно или неверно следующее утверждение: Минимальное остовное дерево может содержать циклы?

26. Постройте дерево наименьшей общей длины, ребра которого соеди­няют вершины правильного шестиугольника.

27. Сколько компонент связности может иметь дерево?

28. Можно ли построить дерево, все вершины которого имеют сте­пень больше, чем единица?

29. Какая модель теории графов адекватна следующей задаче:

Различные организации x₁, ... , x_n обмениваются некоторой информаци­ей (при этом связи могут быть направленными). Если между организациями x_i и x_j возможен непосредственный обмен информацией, то затраты на не­го составляют r_ij рублей. Возможен ли обмен информацией между двумя организациями? Если возможен, то как осуществить этот обмен с наимень­шими затратами?

30. Какая модель теории графов адекватна следующей задаче:

Имеется схема городских дорог с перекрестками и, возможно, однос­торонним движением. Необходимо найти маршрут, соединяющий две точки на карте. Как найти такой маршрут при условии, что его длина минимальна?

31. Какая модель теории графов адекватна следующей задаче: Требуется построить схему электрической сети, в которой клеммы должны быть соединены с помощью проводов наименьшей общей длины.

32. Какая модель теории графов адекватна следующей задаче:

Имеется сеть связи, соединяющая n узлов. Если выйдут из строя не­которые каналы, то связь между узлами может быть нарушена. Какие кана­лы можно удалить без нарушения связи? Какие каналы нужно удалить, что­бы связь не нарушалась, а общая стоимость всех каналов была минималь­ной?

33. Какая модель теории графов адекватна следующей задаче:

Разрабатывается проект газопровода, соединяющего буровые скважины в Мексиканском заливе с находящейся на берегу приемной станцией. Сле­дует выбрать проект, в котором строительство газопровода имеет мини­мальную стоимость.

34. Какая модель теории графов адекватна следующей задаче:

Пусть имеется n изолированных городов. Какое минимальное коли­чество дорог между некоторыми городами надо построить, чтобы иметь возможность попасть из любого города в любой другой? Если заданы расс­тояния между городами, то как выбрать сеть дорог с минимальной общей длиной?

ТЕМА 4. БУЛЕВЫ ФУНКЦИИ