ТЕМА. НАХОЖДЕНИЕ МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА.

ЛАБОРАТОРНАЯ РАБОТА № 3.

1. Деревья. Остовы.

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

Рассмотрим неориентированный граф G= (X, U) с n вершинами. Следующие определения дерева, как легко показать, эквивалентны друг другу:

i. связный граф, не имеющий циклов;

ii. связный граф, содержащий n вершин и n -1 ребер;

iii. граф, в котором каждая пара вершин соединена одной единственной простой цепью.

Граф G ¹ = (X ¹, U ¹) называется подграфом (или частью) графа G= (X, U), если , . Подграф G ¹ называется остовным подграфом, если .

Остовным деревом (или остовом) графа G называется всякий остовный подграф графа G, являющийся деревом. Например, если G – граф, показанный на рис. 1.а, то граф, на рис. 1.б является остовом графа G, как и граф, изображенный на рис. 1.в.

рис. 1.а рис. 1.б рис. 1.в

Очевидно, что в каждом графе существует остов: разрушая в каждой компоненте связности циклы, т.е. удаляя лишние ребра, придем к остову. В общем случае остов определен неоднозначно. Естественно возникает вопрос: как много остовов в графе?

Теорема 1. Пусть G – n -вершинный граф без петель и – его матрица инциденций с одной удаленной строкой (т.е. с n -1 независимыми строками). Пусть – транспонированная матрица к . Тогда определитель равен числу различных остовных деревьев графа G.

Теорема 2. При n >1 число остовов в полном графе равно .

С помощью теоремы 1 легко проверить, что у графа, изображенного на рис. 2, действительно, 21 остов.

рис. 2

Матрица инциденций данного графа имеет следующий вид:

.

Удалив строку x ₂, получим матрицу . Матрица выглядит так:

.

1. Кратчайший остов графа (остов минимального веса).

Рассмотрим взвешенный связный неориентированный граф G= (X, U); вес ребра (x_i, x_j) обозначим c_ij. Из большого числа остовов графа нужно найти один, у которого сумма весов ребер наименьшая. Такая задача возникает, например, в том случае, когда вершины являются клеммами электрической цепи которые должны быть соединены друг с другом с помощью проводов наименьшей общей длины (для уменьшения уровня наводок).

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

Поскольку полный граф содержит различных остовных деревьев, то решение этой задачи “слепым” перебором вариантов потребовало бы чрезвычайно больших вычислений даже при относительно малых n. Однако для ее решения имеются эффективные алгоритмы. Опишем два из них – алгоритмы Дж. Краскала (1956 г.) и Р. Прима (1957 г.), применимые к произвольному связному графу.

Алгоритм Краскала

Шаг 1. Строим граф , присоединяя к пустому графу на множестве вершин X ребро минимального веса.

Шаг 2. Если граф уже построен и , то строим граф , где – ребро графа G= (X, U), имеющее минимальный вес среди ребер, не входящих в и не составляющих циклов с ребрами из .

В качестве иллюстрации рассмотрим взвешенный граф, изображенный на рис. 3

рис. 3

Алгоритм Прима

отличается от алгоритма Краскала только тем, что на каждом этапе строится не просто ациклический граф, но дерево. Именно:

Шаг 1. Выбираем ребро минимального веса и строим дерево .

Шаг 2. Если дерево порядка уже построено и , то среди ребер, соединяющих вершины этого дерева с вершинами графа G= (X, U), не входящими в , выбираем ребро минимального веса. Строим дерево , присоединяя к ребро вместе с его не входящим в концом.

В некоторых случаях требуется построить остов не минимального, а максимального веса. К этой задаче также применимы и алгоритм Краскала, и алгоритм Прима. Следует только всюду минимальный вес заменить максимальным.

Задачи

Найти все остовные деревья в графе:

1. K _5. 2. K _3,3. 3. 4.

5. 6. 7. 8.