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

Граф 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

Тема 19 Булевы функции

 

Лекция 19.1 «Булевы функции»

Учебные вопросы:

1. Определение булевой функции. Формулы логики булевых функций

2. Булева алгебра (алгебра логики). Нормальные формы

3. Разложение булевой функции по переменным

4. Минимизация формул булевых функций в классе дизъюнктивных нормальных форм