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

 

 

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

 

Рассмотрим неориентированный граф 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 число остовов в полном графе  равно .

 

 

 

II.               Практический пример.

 

 

4.)       • Дан граф :     

 

 

         •  Задача :

 

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

 

         •  Решение :

 

 

1.)   Т.к. нам дан полный граф с числом вершин n=4 , то используя Теорему 1 сможем найти количество всех остовов:

K_n = n^n-2 = 4² = 16

 

 

2.)   Находим все остовные деревья графа:

 

 1. - 16.

 

 

 

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

 

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

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

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

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

Воспользуемся алгоритмом Р. Прима (1957 г.), применимый к произвольному связному графу

 

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

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

 

 

IV.            Текст программы.

 

 

 

 

 

 

 

 

V.               Вывод.

 

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