5.4.1 Остовные деревья минимальной стоимости

Пусть даны n контактов на печатной плате, которые мы хотим электрически со- единить. Для этого достаточно использовать n  1 проводов, каждый из которых соединяет два контакта. При этом мы обычно стремимся сделать суммарную длину проводов как можно меньше.

Упрощая ситуацию, можно сформулировать задачу так. Пусть имеется связ- ный неориентированный граф G = (V, Е), в котором V  множество контактов, а Е множество их возможных попарных соединений. Для каждого ребра гра- фа (и, v) задан неотрицательный вес w(и, v) (длина провода, необходимого для соединения и и v). Задача состоит в нахождении подмножества Т Е, связы- вающего все вершины, для которого суммарный вес

минимален. Такое подмножество Т можно считать деревом (в любом цикле один из проводов можно удалить, не нарушая связности). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом (spanning tree) этого графа. (Иногда используют термин «остовное дерево», или, короче, «остов».)

В этом разделе мы рассматриваем задачу о минимальном покрывающем дереве (minimum-spanning-tree problem). Здесь слово «минимальное» означает «имеющее минимально возможный вес». (Заметим в скобках, что если мы рассматриваем только деревья, то условие неотрицательности весов можно отбросить, посколь- ку во всех покрывающих деревьях одинаковое число рёбер и все веса можно изменить на одну и ту же константу, сделав их положительными.) На рисунке 5.6 приведён пример связного графа и его минимального остова.

Возвращаясь к примеру с проводниками на печатной плате, объясним, по- чему задача о минимальном дереве является упрощением реальной ситуации. В самом деле, если соединяемые контакты находятся в вершинах единичного квадрата, разрешается соединять его любые вершины и вес соединения равен его длине, то минимальное покрывающее дерево будет состоять из трёх сторон квадрата. Между тем все его четыре вершины можно электрически соединить двумя пересекающимися диагоналями (суммарная длина < 3) и это ещё не предел (можно ввести две промежуточные точки, в которых проводники сходятся под углом 120⁰).

В этом разделе мы рассмотрим два способа решения задачи о минимальном покрывающем дереве: алгоритмы Крускала и Прима. Каждый их них легко реализовать с временем работы O(Е  log V), используя обычные двоичные ку- чи. Применив фибоначчиевы кучи, можно сократить время работы алгоритма Прима до O(E + V  log V) (выигрыш существен, если |V| много меньше |Е|).

Оба алгоритма (Крускала и Прима) следуют «жадной» стратегии: на каждом шаге выбирается «локально наилучший» вариант. Не для всех задач такой выбор приведёт к оптимальному решению, но для задачи о покрывающем дереве это так.

Рисунок 5.6 – Связный граф и его минимальный остов

На рис. 5.6 изображено минимальное покрывающее дерево. На каждом ребре графа указан вес. Выделены рёбра минимального покрывающего дерева (суммарный вес 37). Такое дерево не единственно: заменяя ребро (b, c) ребром (а, h), получаем другое дерево того же веса 37.