Задача об оптимальном каркасе
Задача об оптимальном каркасе (стягивающем дереве) состоит в следующем.
Дан обыкновенный граф $$G=(V,E)$$ и весовая функция на множестве
ребер $$w:V\texto R$$. Вес множества $$X\subseteq E$$ определяется как сумма
весов составляющих его ребер. Требуется в графе $$G$$ найти каркас
минимального веса. В этом разделе будем предполагать, что граф $$G$$
связен, так что решением задачи всегда будет дерево. Для решения
задачи об оптимальном каркасе известно несколько алгоритмов. Рассмотрим
два из них.
Алгоритм Прима
В алгоритме Прима на каждом шаге рассматривается частичное решение задачи,
представляющее собой дерево. Вначале это дерево состоит из единственной
вершины, в качестве которой может быть выбрана любая вершина графа. Затем
к дереву последовательно добавляются ребра и вершины, пока не получится
остовное дерево, т.е. каркас. Для того чтобы из текущего дерева при
добавлении нового ребра опять получилось дерево, это новое ребро должно
соединять вершину дерева с вершиной, еще не принадлежащей дереву. Такие
ребра будем называть подходящими относительно рассматриваемого
дерева. В алгоритме Прима применяется следующее правило выбора: на каждом
шаге из всех подходящих ребер выбирается ребро наименьшего веса. Это ребро
вместе с одной новой вершиной добавляется к дереву. Если обозначить
через $$U$$ и $$F$$ множества вершин и ребер строящегося
дерева, то алгоритм Прима можно представить следующим образом.
Алгоритм 1. Построение
оптимального каркаса методом Прима
$$U\, :=\{ a\}$$, где $$a$$ - произвольная
вершина графа
$$F\, :=\varnothing$$
while $$U\ne V$$ do
найти ребро наименьшего веса $$e=(x,y)$$ среди всех подходящих ребер
$$F\, :=F\cup \{ e\}$$
$$U\, :=U\cup \{ y\}$$
Докажем, что алгоритм Прима действительно находит оптимальный каркас.
Дерево $$F$$ назовем фрагментом, если существует такой
оптимальный каркас $$T_{0}$$ графа $$G$$, что $$F$$
является
подграфом дерева $$T_{0}$$. Иначе говоря, фрагмент - это
дерево, которое
можно достроить до оптимального каркаса.
Теорема 1. Если $$F$$ - фрагмент, $$e$$ - подходящее ребро наименьшего веса относительно $$F$$, то $$F\cup \{
e\}$$ - фрагмент.
Доказательство. Пусть $$T_{0}$$ - оптимальный каркас, содержащий $$F$$
в качестве подграфа. Если ребро $$e$$ принадлежит $$T_{0}$$,
то $$F\cup \{e\}$$ - подграф $$T_{0}$$ и,
следовательно, фрагмент.
Допустим, $$e$$ не принадлежит $$T_{0}$$.
Если добавить ребро $$e$$ к дереву $$T_{0}$$, то
образуется цикл.
В этом цикле есть еще хотя бы одно подходящее ребро относительно $$F$$
(никакой цикл, очевидно, не может содержать единственное подходящее
ребро). Пусть $$e'$$ - такое ребро. Тогда подграф $$T'_{0}
=T_{0}-e'+e$$,
получающийся из $$T_{0}$$ удалением ребра $$e'$$
и добавлением ребра $$e$$, тоже будет деревом.
Так как $$w(e')\ge w(e)$$, то $$w(T'_{0})\le w(T_{0})$$.
Но $$T_{0}$$ - оптимальный
каркас, следовательно, $$w(T'_{0} )=w(T_{0})$$
и $$T'_{0}$$ - тоже
оптимальный каркас. Но $$F\cup \{ e\}$$ является подграфом графа $$T'_{0}$$ и, следовательно, фрагментом.
Дерево, состоящее из единственной вершины, очевидно, является фрагментом.
Из теоремы 1 следует, что если после некоторого количества шагов алгоритма
Прима дерево $$F$$ является фрагментом, то оно будет фрагментом и
после следующего шага. Следовательно, и окончательное решение, полученное
алгоритмом, будет фрагментом, т.е. оптимальным каркасом.
Оценим время работы алгоритма Прима. Цикл while в строке 4
повторяется один раз для каждой вершины графа, кроме стартовой. Внутри
этого цикла есть еще скрытый цикл в строке 5, где ищется ребро наименьшего
веса среди всех ребер, соединяющих вершины из множества $$U$$
с вершинами, не принадлежащими $$U$$. Допустим, что этот поиск
производится самым бесхитростным образом, т.е. просматриваются все пары
вершин $$(x,y)$$ с $$x\in U$$, $$y\notin U$$.
Если $$|U|=k$$, то
имеется $$k(n-k)$$ таких пар. Так как k меняется от 1
до $$n-1$$, то всего получаем
$$\suml_{k=1}^{n-1}k(n-k)=n\suml_{k=1}^{n-1}k-\suml_{k=1}^{n-1}k^{2}
=\frac{n^{2} (n-1)}{2} -\frac{(n-1)n(2n-1)}{6}
=\frac{n^{3} -n}{6}$$
пар, которые нужно рассмотреть. Таким образом, трудоемкость алгоритма
будет $$O(n^{3})$$.
Небольшое усовершенствование позволяет на порядок ускорить этот алгоритм.
Допустим, что для каждой вершины $$y$$ из множества $$\overline{U}=V-U$$
известна такая вершина $$b(y)\in U$$, что $$w(b(y),y)=\min_{x\in U} w(x,y)$$.
Тогда при $$|U|=k$$
необходимо будет выбрать ребро наименьшего веса среди $$n-k$$ ребер,
а общее число анализируемых ребер будет равно
$$\suml_{k=1}^{n-1}(n-k)=\frac{n(n-1)}{2}.$$
В этом случае, однако, необходимы дополнительные действия для обновления
таблицы значений функции $$b$$ при добавлении одной вершины к дереву,
т.е. при переносе одной вершины из множества $$\overline{U}$$
в множество $$U$$. Сначала, когда множество $$U$$ состоит
из
единственной вершины $$a$$, полагаем $$b(x)=a$$ для всех $$x\in \overline{U}$$. В дальнейшем эти значения могут меняться. Допустим,
на
некотором шаге к дереву присоединяется вершина $$y$$. Тогда для
каждой
вершины $$z\in \overline{U}$$ либо сохраняется старое значение $$b(z)$$,
либо устанавливается новое $$b(z)=y$$, в зависимости от того, какое
из
ребер $$(b(z),z)$$ и $$(y,z)$$ имеет меньший вес. Иначе
говоря, для
модификации функции $$b$$ достаточно в алгоритме 10 после строки 8
(и внутри цикла while ) добавить
следующее:
for $$z\in
\ol{U}$$ do
if $$w(b(z),z)>w(y,z)$$ then $$b(z):=y$$
При $$|U|=k$$ цикл в строке 9 повторяется $$n-k$$ раз.
Таким
образом, дополнительное время, необходимое для обслуживания
таблицы $$b$$, тоже оценивается сверху квадратичной функцией
от $$n$$
и общая оценка трудоемкости усовершенствованного алгоритма Прима
будет $$O(n^{2} )$$.
Другой путь к усовершенствованию алгоритма Прима подсказывает следующее
замечание. При выборе подходящего ребра (в строке 5 алгоритма 10) можно
рассматривать не все пары $$(x,y)\in U\textimes \overline{U}$$, а только те,
которые являются ребрами графа. Если граф разреженный, т.е. содержит
намного меньше ребер, чем полный граф, то это может значительно ускорить
решение задачи. Дополнительный выигрыш можно получить, если использовать
приоритетную очередь для хранения множества ребер, подлежащих
исследованию.
Алгоритм Крускала
Другой жадный алгоритм для задачи об оптимальном каркасе известен как алгоритм Крускала.
В нем тоже на каждом шаге
рассматривается частичное решение. Отличие от алгоритма Прима состоит
в том, что в алгоритме Крускала частичное решение всегда представляет собой
остовный лес $$F$$ графа $$G$$, т.е. лес, состоящий из
всех вершин
графа $$G$$ и некоторых его ребер. Вначале $$F$$ не
содержит ни
одного ребра, т.е. состоит из изолированных вершин. Затем к нему
последовательно добавляются ребра, пока не будет построен каркас
графа $$G$$.
Пусть $$F$$ - лес, построенный к очередному шагу. Ребро
графа, не принадлежащее $$F$$, назовем красным, если вершины этого
ребра принадлежат одной компоненте связности леса $$F$$, и зеленым,
если они принадлежат разным компонентам. Если к $$F$$ добавить
красное
ребро, то образуется цикл. Если же к $$F$$ добавить зеленое ребро, то
получится новый лес, в котором будет на одну компоненту связности меньше,
чем в $$F$$, так как в результате добавления ребра две компоненты
сольются в одну. Таким образом, к $$F$$ нельзя добавить никакое
красное ребро и можно добавить любое зеленое. Для выбора добавляемого
ребра применяется тот же "жадный" принцип, что и в алгоритме Прима
-
из всех зеленых ребер выбирается ребро наименьшего веса. Для того чтобы
облегчить поиск этого ребра, вначале все ребра графа упорядочиваются по
возрастанию весов: $$w(e_{1} )\le w(e_{2} )\le \ldots \le w(e_{m})$$.
Теперь последовательность ребер $$e_{1},e_{2} \ldots e_{m}$$
достаточно просмотреть один раз и для очередного рассматриваемого ребра
нужно только уметь определять, является ли оно красным или зеленым
относительно построенного к этому моменту леса $$F$$. Красные ребра
просто пропускаются, а зеленые добавляются к $$F$$.
Для более формального описания алгоритма заметим, что текущий
лес $$F$$
определяет разбиение множества вершин графа на области связности этого
леса: $$V=P_{1} \cup P_{2} \cup \ldots \cup P_{k}$$ и что красное
ребро - это такое ребро, у которого обе вершины принадлежат одной части
разбиения. Пусть $$\Part(x)$$ - функция, возвращающая для
каждой
вершины $$x$$ имя той части разбиения, которой
принадлежит $$x$$,
а $$\Unite(x,y)$$ - процедура, которая по именам $$x$$
и $$y$$ двух
частей разбиения строит новое разбиение, заменяя эти две части их
объединением. Пусть $$e_{i} =(a_{i},b_{i})$$, $$i=1\ldots
m$$.
Тогда алгоритм Крускала (после упомянутого упорядочения ребер) можно
записать следующим образом.
Алгоритм 2. Построение оптимального каркаса методом
Крускала
for $$i:=1$$ to $$m$$ do
$$x:=\Part(a_{i})$$
$$y:=\Part(b_{i})$$
if $$x\ne y$$ then $${F:=F\cup \{ e_{i}}$$, $$\Unite(x,y)}$$
Более подробно алгоритм Крускала рассматривается во второй части
(в разделе, посвященном разделенным множествам). Корректность этого
алгоритма следует из общей теоремы Радо-Эдмондса, которая будет
рассмотрена в следующей лекции.
Задача об оптимальном каркасе
Задача об оптимальном каркасе (стягивающем дереве) состоит в следующем.
Дан обыкновенный граф $$G=(V,E)$$ и весовая функция на множестве
ребер $$w:V\texto R$$. Вес множества $$X\subseteq E$$ определяется как сумма
весов составляющих его ребер. Требуется в графе $$G$$ найти каркас
минимального веса. В этом разделе будем предполагать, что граф $$G$$
связен, так что решением задачи всегда будет дерево. Для решения
задачи об оптимальном каркасе известно несколько алгоритмов. Рассмотрим
два из них.
Алгоритм Прима
В алгоритме Прима на каждом шаге рассматривается частичное решение задачи,
представляющее собой дерево. Вначале это дерево состоит из единственной
вершины, в качестве которой может быть выбрана любая вершина графа. Затем
к дереву последовательно добавляются ребра и вершины, пока не получится
остовное дерево, т.е. каркас. Для того чтобы из текущего дерева при
добавлении нового ребра опять получилось дерево, это новое ребро должно
соединять вершину дерева с вершиной, еще не принадлежащей дереву. Такие
ребра будем называть подходящими относительно рассматриваемого
дерева. В алгоритме Прима применяется следующее правило выбора: на каждом
шаге из всех подходящих ребер выбирается ребро наименьшего веса. Это ребро
вместе с одной новой вершиной добавляется к дереву. Если обозначить
через $$U$$ и $$F$$ множества вершин и ребер строящегося
дерева, то алгоритм Прима можно представить следующим образом.
Алгоритм 1. Построение
оптимального каркаса методом Прима
$$U\, :=\{ a\}$$, где $$a$$ - произвольная
вершина графа
$$F\, :=\varnothing$$
while $$U\ne V$$ do
найти ребро наименьшего веса $$e=(x,y)$$ среди всех подходящих ребер
$$F\, :=F\cup \{ e\}$$
$$U\, :=U\cup \{ y\}$$
Докажем, что алгоритм Прима действительно находит оптимальный каркас.
Дерево $$F$$ назовем фрагментом, если существует такой
оптимальный каркас $$T_{0}$$ графа $$G$$, что $$F$$
является
подграфом дерева $$T_{0}$$. Иначе говоря, фрагмент - это
дерево, которое
можно достроить до оптимального каркаса.
Теорема 1. Если $$F$$ - фрагмент, $$e$$ - подходящее ребро наименьшего веса относительно $$F$$, то $$F\cup \{
e\}$$ - фрагмент.
Доказательство. Пусть $$T_{0}$$ - оптимальный каркас, содержащий $$F$$
в качестве подграфа. Если ребро $$e$$ принадлежит $$T_{0}$$,
то $$F\cup \{e\}$$ - подграф $$T_{0}$$ и,
следовательно, фрагмент.
Допустим, $$e$$ не принадлежит $$T_{0}$$.
Если добавить ребро $$e$$ к дереву $$T_{0}$$, то
образуется цикл.
В этом цикле есть еще хотя бы одно подходящее ребро относительно $$F$$
(никакой цикл, очевидно, не может содержать единственное подходящее
ребро). Пусть $$e'$$ - такое ребро. Тогда подграф $$T'_{0}
=T_{0}-e'+e$$,
получающийся из $$T_{0}$$ удалением ребра $$e'$$
и добавлением ребра $$e$$, тоже будет деревом.
Так как $$w(e')\ge w(e)$$, то $$w(T'_{0})\le w(T_{0})$$.
Но $$T_{0}$$ - оптимальный
каркас, следовательно, $$w(T'_{0} )=w(T_{0})$$
и $$T'_{0}$$ - тоже
оптимальный каркас. Но $$F\cup \{ e\}$$ является подграфом графа $$T'_{0}$$ и, следовательно, фрагментом.
Дерево, состоящее из единственной вершины, очевидно, является фрагментом.
Из теоремы 1 следует, что если после некоторого количества шагов алгоритма
Прима дерево $$F$$ является фрагментом, то оно будет фрагментом и
после следующего шага. Следовательно, и окончательное решение, полученное
алгоритмом, будет фрагментом, т.е. оптимальным каркасом.
Оценим время работы алгоритма Прима. Цикл while в строке 4
повторяется один раз для каждой вершины графа, кроме стартовой. Внутри
этого цикла есть еще скрытый цикл в строке 5, где ищется ребро наименьшего
веса среди всех ребер, соединяющих вершины из множества $$U$$
с вершинами, не принадлежащими $$U$$. Допустим, что этот поиск
производится самым бесхитростным образом, т.е. просматриваются все пары
вершин $$(x,y)$$ с $$x\in U$$, $$y\notin U$$.
Если $$|U|=k$$, то
имеется $$k(n-k)$$ таких пар. Так как k меняется от 1
до $$n-1$$, то всего получаем
$$\suml_{k=1}^{n-1}k(n-k)=n\suml_{k=1}^{n-1}k-\suml_{k=1}^{n-1}k^{2}
=\frac{n^{2} (n-1)}{2} -\frac{(n-1)n(2n-1)}{6}
=\frac{n^{3} -n}{6}$$
пар, которые нужно рассмотреть. Таким образом, трудоемкость алгоритма
будет $$O(n^{3})$$.
Небольшое усовершенствование позволяет на порядок ускорить этот алгоритм.
Допустим, что для каждой вершины $$y$$ из множества $$\overline{U}=V-U$$
известна такая вершина $$b(y)\in U$$, что $$w(b(y),y)=\min_{x\in U} w(x,y)$$.
Тогда при $$|U|=k$$
необходимо будет выбрать ребро наименьшего веса среди $$n-k$$ ребер,
а общее число анализируемых ребер будет равно
$$\suml_{k=1}^{n-1}(n-k)=\frac{n(n-1)}{2}.$$
В этом случае, однако, необходимы дополнительные действия для обновления
таблицы значений функции $$b$$ при добавлении одной вершины к дереву,
т.е. при переносе одной вершины из множества $$\overline{U}$$
в множество $$U$$. Сначала, когда множество $$U$$ состоит
из
единственной вершины $$a$$, полагаем $$b(x)=a$$ для всех $$x\in \overline{U}$$. В дальнейшем эти значения могут меняться. Допустим,
на
некотором шаге к дереву присоединяется вершина $$y$$. Тогда для
каждой
вершины $$z\in \overline{U}$$ либо сохраняется старое значение $$b(z)$$,
либо устанавливается новое $$b(z)=y$$, в зависимости от того, какое
из
ребер $$(b(z),z)$$ и $$(y,z)$$ имеет меньший вес. Иначе
говоря, для
модификации функции $$b$$ достаточно в алгоритме 10 после строки 8
(и внутри цикла while ) добавить
следующее:
for $$z\in
\ol{U}$$ do
if $$w(b(z),z)>w(y,z)$$ then $$b(z):=y$$
При $$|U|=k$$ цикл в строке 9 повторяется $$n-k$$ раз.
Таким
образом, дополнительное время, необходимое для обслуживания
таблицы $$b$$, тоже оценивается сверху квадратичной функцией
от $$n$$
и общая оценка трудоемкости усовершенствованного алгоритма Прима
будет $$O(n^{2} )$$.
Другой путь к усовершенствованию алгоритма Прима подсказывает следующее
замечание. При выборе подходящего ребра (в строке 5 алгоритма 10) можно
рассматривать не все пары $$(x,y)\in U\textimes \overline{U}$$, а только те,
которые являются ребрами графа. Если граф разреженный, т.е. содержит
намного меньше ребер, чем полный граф, то это может значительно ускорить
решение задачи. Дополнительный выигрыш можно получить, если использовать
приоритетную очередь для хранения множества ребер, подлежащих
исследованию.
Алгоритм Крускала
Другой жадный алгоритм для задачи об оптимальном каркасе известен как алгоритм Крускала.
В нем тоже на каждом шаге
рассматривается частичное решение. Отличие от алгоритма Прима состоит
в том, что в алгоритме Крускала частичное решение всегда представляет собой
остовный лес $$F$$ графа $$G$$, т.е. лес, состоящий из
всех вершин
графа $$G$$ и некоторых его ребер. Вначале $$F$$ не
содержит ни
одного ребра, т.е. состоит из изолированных вершин. Затем к нему
последовательно добавляются ребра, пока не будет построен каркас
графа $$G$$.
Пусть $$F$$ - лес, построенный к очередному шагу. Ребро
графа, не принадлежащее $$F$$, назовем красным, если вершины этого
ребра принадлежат одной компоненте связности леса $$F$$, и зеленым,
если они принадлежат разным компонентам. Если к $$F$$ добавить
красное
ребро, то образуется цикл. Если же к $$F$$ добавить зеленое ребро, то
получится новый лес, в котором будет на одну компоненту связности меньше,
чем в $$F$$, так как в результате добавления ребра две компоненты
сольются в одну. Таким образом, к $$F$$ нельзя добавить никакое
красное ребро и можно добавить любое зеленое. Для выбора добавляемого
ребра применяется тот же "жадный" принцип, что и в алгоритме Прима
-
из всех зеленых ребер выбирается ребро наименьшего веса. Для того чтобы
облегчить поиск этого ребра, вначале все ребра графа упорядочиваются по
возрастанию весов: $$w(e_{1} )\le w(e_{2} )\le \ldots \le w(e_{m})$$.
Теперь последовательность ребер $$e_{1},e_{2} \ldots e_{m}$$
достаточно просмотреть один раз и для очередного рассматриваемого ребра
нужно только уметь определять, является ли оно красным или зеленым
относительно построенного к этому моменту леса $$F$$. Красные ребра
просто пропускаются, а зеленые добавляются к $$F$$.
Для более формального описания алгоритма заметим, что текущий
лес $$F$$
определяет разбиение множества вершин графа на области связности этого
леса: $$V=P_{1} \cup P_{2} \cup \ldots \cup P_{k}$$ и что красное
ребро - это такое ребро, у которого обе вершины принадлежат одной части
разбиения. Пусть $$\Part(x)$$ - функция, возвращающая для
каждой
вершины $$x$$ имя той части разбиения, которой
принадлежит $$x$$,
а $$\Unite(x,y)$$ - процедура, которая по именам $$x$$
и $$y$$ двух
частей разбиения строит новое разбиение, заменяя эти две части их
объединением. Пусть $$e_{i} =(a_{i},b_{i})$$, $$i=1\ldots
m$$.
Тогда алгоритм Крускала (после упомянутого упорядочения ребер) можно
записать следующим образом.
Алгоритм 2. Построение оптимального каркаса методом
Крускала
for $$i:=1$$ to $$m$$ do
$$x:=\Part(a_{i})$$
$$y:=\Part(b_{i})$$
if $$x\ne y$$ then $${F:=F\cup \{ e_{i}}$$, $$\Unite(x,y)}$$
Более подробно алгоритм Крускала рассматривается во второй части
(в разделе, посвященном разделенным множествам). Корректность этого
алгоритма следует из общей теоремы Радо-Эдмондса, которая будет
рассмотрена в следующей лекции.
