Примеры решения задач

Пример 1. Для графа G = (X, U), изображённого на рис. 16.30, записать матрицу расстояний и список расстояний.

Рис. 16.30. Граф G

Решение: запишем матрицу расстояний для заданного графа.

Матрица расстояний будет иметь вид:

^.

Таким образом, первая часть задания выполнена. Теперь построим список расстояний. Его можно записать следующим образом:

D = {<1,2,1>;<1,3,1>;<1,4,2>;<2,3,2>;<2,4,1>;<3,4,1>}.

Пример 2. Для графа G = (X,U), заданного на рис. 16.31, построить его отображение в координатную решётку и матрицу геометрии. Подсчитать суммарную длину рёбер L(G) графа, отображённого в координатную решётку.

Рис. 16.31. Граф G

Решение: после отображения в координатную решётку графа G получим граф G_r, показанный на рис. 16.32.

Рис. 16.32. Отображение графа G в координатную решетку

Теперь для полученного графа G_r запишем матрицу геометрии. Как уже говорилось ранее, матрица геометрии получается путём перемножения матрицы расстояний D и матрицы смежности:

^.

В результате перемножения матриц мы получили матрицу геометрии D. Сумма элементов данной матрицы равна 24. Следовательно, суммарная длина рёбер L(G) графа G_r равна 12.

Вопросы для самоконтроля

1. Что такое метрика графа?

2. Как определяется расстояние между двумя вершинами графа?

3. Каким образом формируется матрица расстояний?

4. В чем состоит отличие между матрицей расстояний и матрицей геометрии?

5. Каким образом определяется диаметр графа?

6. Каким образом граф отображается в координатную решетку?

7. Как построить список расстояний?

8. Как определяется радиус графа?

9. Что такое число протяженности?

10. Каким образом определяется расстояние между узлами решетки?

Задания для самостоятельной работы

1. Для графа G = (X, U) построить матрицу и список расстояний.

2. Для произвольного графа G = (X, U) построить его отображение в координатную решетку G_r, матрицу расстояний, матрицу геометрии, а также подсчитать суммарную длину ребер.

3. Для произвольного графа определить диаметр и радиус графа.

4. Для произвольного графа определите центр графа.

5. Определите в произвольном графе G длиннейшие простые цепи и число протяженности.

6. Постройте произвольный граф на 10 вершин, отобразите его в решетку и определите расстояние между его вершинами.

7. Постройте словесный алгоритм определения матрицы геометрии.

8. Запишите псевдокод алгоритма определения матрицы геометрии.

9. Приведите структурную схему алгоритма определения матрицы геометрии по рисунку графа.

10. Приведите словесный алгоритм отображения графа в координатную решетку.

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

16.5. Деревья

Связный граф без циклов называется деревом и обозначается T = (X, U), |X| = n. Любое дерево T имеет n – 1 ребро. Начальная вершина называется корнем, из которого выходят ребра – ветви дерева. Очевидно, что в дереве любые две вершины x_i, x_j связаны единственной цепью. В любом связном графе G можно выделить произвольное дерево Т. В любом дереве порядка n  2 имеется не менее двух концевых вершин.

Теорема 16.8. Пусть Т – граф из n вершин. Следующие утверждения эквивалентны:

• Т является деревом,

• Т не содержит циклов и имеет n – 1 ребер,

• Т связен и имеет n – 1 ребер,

• Т связен и каждое его ребро является мостом,

• любые две вершины графа Т соединены ровно одной простой цепью,

• Т не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один цикл.

Для задач конструкторского и технологического проектирования наибольший интерес представляют деревья, у которых число вершин равно числу вершин графа, из которого выделено это дерево. Такие деревья называются покрывающими (ПД) или остовными. На рис 16.33 показан полный граф K₄ и все его 16 ПД.

1-й ряд

2-й ряд

3-й ряд

4-й ряд

Рис. 16.33. Граф K₄ и его покрывающие деревья

Отметим, что здесь всего 4 различных покрывающих дерева. Остальные графы в каждом ряду одинаковые, только нарисованы по-разному.

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

Граф, в котором число ребер не меньше чем число вершин, содержит цикл. Число ребер m произвольного графа G = (X, U), |X| = n, |U| = m, которые необходимо удалить для получения каркаса, не зависит от последовательности их удаления.

Например, на рис. 16.34, а показан граф G, а на рис. 16.34, б его каркас (остовное дерево).

а б

Рис. 16.34. Граф G (а) и его остовное дерево (б)

Утверждение 16.4. Всякий ациклический подграф G’ = (X’, U’) произвольного графа G = (X, U), X’  X, U’  U содержится в некотором каркасе O графа G (O = (X, U’), G = (X, U), U’  U).

Утверждение 16.5. Если O₁ = (X₁, U₁) и O₂ = (X₂, U₂) два каркаса графа G = =(X, U) (X = X₁ = X₂, U₁  U, U₂  U), то для любого ребра u_i  U₁ графа O₁ существует такое ребро u_j  U₂ графа O₂, что граф O₁ - u_i + u_j также является каркасом. Например, имеем граф G (рис. 16.35, а) и два каркаса этого графа O₁ (рис. 16.35, б) и O₂ (рис. 16.35, в). Пусть ребро u_i = u_3,4, а ребро u_j = u_5,6, ребро u_i  U₁ графа O₁ и ребро u_j  U₂ графа O₂. Тогда граф O₁ - u_i + u_j = O₁ - u_3,4 + u_5,6 также будет каркасом (рис. 16.35, г).

а б

в г

Рис. 16.35. Граф G и его каркасы

Теорема 16.9 (Кэли). Существует ровно n^n-2 различных помеченных деревьев с n вершинами.

Следствие 16.1. Число остовных деревьев в K_n равно n^n-2.

Множество деревьев графа называется лесом. На рис. 16.36 показан лес, состоящий из 3 деревьев T1 - T3.

Рис. 16.36. Множество деревьев графа

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

Задача о лабиринте в терминах теории графов формулируется как задача отыскания в связном графе G = (X, U) такого маршрута, который начинается в заданной вершине x_i  X и приводит в искомую вершину x_j  X, причем маршрут должен содержать кратчайшее число ребер.

Пусть нам необходимо проложить сеть проводов, связывающих n терминалов вычислительной аппаратуры, причем так, чтобы из одного терминала можно было связаться с любым другим. Если из экономических соображений требуется, чтобы количество затраченного провода было минимально, то граф, вершины которого соответствуют терминалам, а ребра соединяющим их проводам, должен быть деревом. Задача состоит в определении одного из n^n-2 возможных деревьев, соединяющих терминалы, с минимизацией числа проводов. На языке теории графов эту задачу можно сформулировать следующим образом. Пусть G = (X, U) связный граф и каждому ребру u_i  U ставится в соответствие некоторое неотрицательное (u_i), называемое его мерой или весом. Необходимо найти алгоритм построения покрывающего дерева Т, у которого сумма мер, взятая по всем ребрам, минимальна. Такие деревья будем называть кратчайшими покрывающими деревьями (КПД). Графы с весами на ребрах или вершинах будем называть взвешенными.

Запишем алгоритм Краскала для построения кратчайшего покрывающего дерева.

1. Пусть задан граф G = (X, U), для которого нужно построить кратчайшее покрывающее дерево. Строим граф G₁ = O_п + u₁, присоединяя к пустому графу O_п на множестве вершин X ребро u₁  U минимального веса.

2. Если граф G_i уже построен и i < n – 1, то строим граф G_i+1 = G_i + u_i+1,

где u_i+1 – ребро графа G, имеющее минимальный вес среди ребер, не входящих в G_i и не составляющих циклов с ребрами из G_i. При i = n – 1, переход к пункту 3.

3. Конец работы алгоритма.

Теорема 16.10. При i < n – 1 граф G_i+1 можно построить. Граф G_n-1 является каркасом с минимальным весом ребер в графе G.

Например, пусть задан граф с G весами на ребрах (рис. 16.37).

а б

Рис. 16.37. Взвешенный граф G(а); каркас графа G (б)

Согласно алгоритму Краскала выбираем сначала ребро u_1,4 с весом 1. Далее берем ребро u_1,5 с весом 1. Затем среди оставшихся ребер с минимальным весом есть ребро u_4,5, однако оно не пригодно для каркаса, т.к. образует цикл с ребрами u_1,4 и u_1,5. Далее выбираем ребра u_3,6 и u_5,6 с весом 2. Итак, каркас с минимальным весом равным 8 построен (рис. 16.37, б)

Приведем логическую схему алгоритма (ЛСА) Краскала решения данной задачи:

A₀A₁²¹A₂p₁¹p₂²A_к,

здесь А₀ – оператор начала;

А₁ – оператор, устанавливающий i = 1;

А₂ – оператор, выбирающий ребро u_i с наименьшим весом;

р₁ – проверка логического условия несовпадения ребра u_i с предыдущим и необразования цикла с предыдущими ребрами. При p₁ = 0, i = i + 1 переход к A₂, при p₁ = 1 переход к p₂;

p₂ – проверка логического условия, что мощность выбранных ребер равна n – 1. При p₂ = 0, i = i + 1 переход к А₂, при p₂ = 1 переход к А_к;

А_к – оператор конца алгоритма.

Опишем алгоритм Прима построения кратчайшего покрывающего дерева (КПД) на взвешенном по ребрам графе. Алгоритм основан на разрастании поддеревьев. Дерево T’ = (X’, U’) является поддеревом T = (X, U), если X’  X, U’  U. Причем поддерево T’ может состоять и из одной вершины. Поддерево Т’ последовательно разрастается за счет прибавления ребер (x_i, x_j), (x_i  T, x_j  T’). Каждое добавляемое ребро должно иметь наименьший вес. Процесс продолжается, пока число ребер в T’ не станет равным n – 1. Покажем работу алгоритма на построении кратчайшего покрывающего дерева в графе G. Пусть граф задан матрицей смежности:

		1	2	3	4	5	6
R =	1	0	5	8	0	37	0	.
	2	5	0	0	7	10	0
	3	8	0	0	3	0	0
	4	0	7	3	0	11	20
	5	37	10	0	11	0	12
	6	0	0	0	20	12	0

Выбираем вершину x₁ и считаем ее на первом шаге поддеревом T’ = (X’, U’), X’ = {x₁}, U’ = . Строим упорядоченный список ребер, инцидентных вершине x₁. Упорядочивание производится по возрастанию веса ребер.

	ui	(ui)
L=	(1, 2)	5	.
	(1, 3)	8
	(1, 5)	37

Из списка выбирается ребро (1, 2) (т.е. (x₁, x₂)). Производится разрастание поддерева T’ = (X’, U’), X’ = {x₁, x₂}, U’ = {(1, 2)}. В список L вносятся ребра, инцидентные вершине x₂. После этого ребра снова упорядочиваются, и список примет вид

	ui	(ui)
	(2, 4)	7	.
L=	(1, 3)	8
	(2, 5)	10
	(1, 5)	37

Выбирается ребро (2, 4) с наименьшим весом и добавляется к поддереву T’, если оно не образует цикла с ребрами T’. Остальные ребра, объединяющие вершины X’ между собой, удаляются из L; X’ = {x₁, x₂, x₄}, U’ = {(1, 2), (2, 4)}. Проверяется |X’| = |X|, если нет, то выбирается вершина x₄ и ребра, инцидентные ей, пополняют список L:

	ui	(ui)
	(4, 3)	3	.
	(1, 3)	8
L=	(2, 5)	10
	(4, 5)	11
	(4, 6)	20
	(1, 5)	37

Продолжая, получаем U’ = {(1, 2), (2, 4), (4, 3), (2, 5), (5, 6)}, |X| = |X’|, процесс окончен, ₁^n-1(u_i) = 32. На рис. 16.38 кратчайшее покрывающее дерево показано жирными линиями.

Рис. 16.38. Исходный граф G и его кратчайшее покрывающее дерево

Алгоритмы построения покрывающих деревьев с минимальной суммарной длиной ребер на взвешенных графах основаны на двух принципах:

• каждая изолированная вершина соединяется с ближайшей соседней;

• каждое изолированное поддерево соединяется с ближайшей соседней вершиной (или поддеревом) кратчайшим ребром (или цепью).

Задача построения КПД усложняется, если при соединении множества вершин (контактов цепи) разрешается использование дополнительных точек соединения. В общем виде данная задача формируется так: для заданных x₁, x₂, ..., x_n точек плоскости построить КПД с n’  n вершинами — и называется задачей Штейнера (ЗШ). Обычно решение ЗШ рассматривают в областях прямоугольной конфигурации. Для n  5 известно решение ЗШ, в общем же случае известны условия, которым должны удовлетворять деревья Штейнера (ДШ) и эвристические алгоритмы. Дополнительные точки, вводимые при построении КПД, называют точками Штейнера (ТШ).

Приведем ряд лемм, полученных Фридманом и Меноном, дающих необходимые условия существования и построения ДШ.

Лемма 16.1. Для n вершин, которые должны быть соединены между собой, всегда можно построить ДШ, в котором каждая ТШ g_i соединена по крайней мере с тремя другими.

Лемма 16.2. Для множества вершин {x₁, x₂, x₃}, которые должны быть соединены, координаты ТШ g, минимизирующей ³_{i = 1} d(g, n_i), будут Sср, Тср и справедливо выражение ³_{i = 1} d(g, n_i) = 1/2 P(x₁, x₂, x₃), где Sср, Тср – средние значения S_i (i = 1, 2, 3) и T_j (j = 1, 2, 3); P(x₁, x₂, x₃) – длина периметра прямоугольника, построенного на вершинах x₁, x₂, x₃; d(g, n_i) – прямоугольное расстояние между g и n_i.

На рис. 16.39 показан пример, иллюстрирующий условия леммы 16.2 при построении ДШ, соединяющего вершины x₁, x₂, x₃. Точка Штейнера g имеет координаты Sg = 3,Tg = 5.

Рис. 16.39. Построения дерева Штейнера

Лемма 16.3. Дано ДШ, состоящее из x_i точек плоскости. Пусть ТШ g соединена только с тремя вершинами x₁, x₂, x₃. Тогда g находится внутри прямоугольника, построенного на вершинах x₁, x₂, x₃, и ТШ единственная.

Следствие 16.2. Для заданного множества вершин x₁, x₂, x₃ ДШ содержит одну ТШ g c координатами (Sср, Тср), если она не совпадает ни с одной из вершин x₁, x₂, x₃ и суммарная длина ребер ДШ равна 1/2P(x₁, x₂, x₃).

Лемма 16.4. Дано ДШ на множестве X = {x₁, x₂, ..., x_n}, а ТШ этого дерева образуют множество G = {g₁, g₂, ..., g_k}. Если g₁  G и g_i  I, то g₁ содержит элемент g_1.k, соединенный не менее чем с двумя вершинами из I, в противном случае g₁ пусто. Здесь I — множество точек пересечения линий координатной сетки.

На основе приведенных лемм сформулирована известная теорема.

Теорема 16.11. Дано ДШ на множестве вершин X = {x₁, x₂, ..., x_n} с множеством ТШ G = {g₁, g₂, ..., g_k}. Тогда для этого множества существует такое другое ДШ с множеством ТШ G’, что (g’_i  G’)(g’_i  I).

Из рассмотрения теоремы следует метод определения ДШ на основе полного перебора в качестве ТШ всех возможных подмножеств точек I. Очевидно, что такой метод применим только при построении ДШ для небольшого числа ТШ. В этой связи разрабатываются эвристические процедуры построения квазиоптимальных ДШ.

Процедура 1.

1. Все вершины x_i  X проектируются на ось S(T).

2. Расстояние от наименьшей до наибольшей координаты делится пополам, и из этой точки i  I проводится перпендикуляр (столб Штейнера).

3. Из каждой вершины x_i  X опускается перпендикуляр до пересечения со столбом Штейнера.

4. Построено ДШ. Конец работы алгоритма.

На основе данной процедуры можно предложить следующий алгоритм построения дерева Штейнера.

Итак, во-первых, мы отображаем заданный граф G в координатную решётку, а затем находим координаты всех вершин полученного графа G_r и вычисляем по какой из осей координат разность максимального и минимального значений координат будет максимальной.

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

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

Данный алгоритм очень прост, ВСА равна O(n), но суммарная длина проводников дерева Штейнера далеко не оптимальна.

Процедура 2 (Алгоритм Ханана).

1. Все множество вершин x_i  X разбивается на классы S₀, S₁, ..., S_i в порядке возрастания координаты S_i так, чтобы у всех вершин одного класса была одинаковая координата S_i.

2. Анализируется множество вершин класса S₀, и соединяются перпендикуляром все вершины этого множества с точкой S_min оси S.

3. Образуется множество I’, состоящее из всех точек I, которые были до этого соединены с произвольной вершиной x_i, включая и вершины x_i строящегося ДШ.

4. Выбирается следующее множество S_i+1, имеющее наименьшую координату S. Определяются точка i_m  I’ и вершина x_j  S_i+1, для которых

d(i_m, x_j)  d(i_q, x_j’), i_q  I’, x_j’  S_i+1.

Другими словами, x_i находится на кратчайшем расстоянии от рассматриваемого фрагмента ДШ в классе S_i+1. Точка i_m с координатами (s_m, t_m) соединяется с вершиной x_j с координатами (s_i, t_i) двухзвенной линией. Причем звенья параллельны координатным осям S и T.

5. Для каждой вершины x_k  S_i+1 производятся операции, аналогичные 4. При этом вершина x_k соединяется с ближайшей в I’.

6. Пункты 4 и 5 повторяются для всех по порядку множеств S_j до построения ДШ.

Отметим, что существует большое число модификаций описанных процедур. Можно проводить упорядочивание координат не по увеличению S(T), а по уменьшению S(T). Временная сложность алгоритма процедуры 2 составляет O(n²). На рис. 2.39, б показана реализация процедуры 2 с упорядочиванием вершин в 1 в порядке убывания координат S. Суммарная длина ДШ составляет 22 условные единицы, при этом число ТШ равно 2.

Для построения ДШ можно использовать методы поиска или ветвей и границ в зависимости от требований на ВСА.

Заметим, что на основе модели дерева можно описывать любое алгебраическое выражение, например, дерево (рис. 16.40) может моделировать следующие записи:

(2+у)*7, *+2у7, *(2+у)7, 2у+7*, (2+у)7* и т.п.

Запись, где символы операций предшествуют операндам, называется Польским выражением или Польской записью. Это – *+2у7. Использование таких моделей позволяет разрабатывать эффективные программы и алгоритмы преобразования алгебраических выражений.

Рис. 16.40. Пример записи алгоритма на основе модели дерева