Минимальное остовное дерево

V Гомельская научно-практическая конференция школьников по математике, ее приложениям и информационным технологиям "Поиск"

Учебно-исследовательская работа

«Минимальное остовное дерево»

Ученицы

11/ «Б» класса

ГУО СОШ№22 г. Гомеля

Самсоновой Галины Викторовны

Научный руководитель

Горский Сергей Михайлович

учитель математики

Государственного учреждения образования

«Гимназия №14 г. Гомеля»

Гомель, 2009

Содержание

• Введение 3
• 1. Построение минимального остовного дерева 5
• 1.1 Алгоритм Борувки 6
• 1.2 Алгоритм Крускала 7
• 1.3 Алгоритм Прима 8
• 2. Поиск ММОД 10
• Заключение 17
• Список использованных источников 18
• Введение

Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: допустим, есть n городов, которые необходимо соединить дорогами, так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Разрешается строить дороги между заданными парами городов и известна стоимость строительства каждой такой дороги. Требуется решить, какие именно дороги нужно строить, чтобы минимизировать общую стоимость строительства.

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

У задачи построения минимального остовного дерева длинная и богатая история. Грэхем и Хелл в своей статье «История задачи построения минимального остовного дерева» начинают отсчет истории проблемы с работы Чекановского 1909 года. Первый и, наверное, простейший алгоритм восходит к Борувке, который в 1926 году, намного раньше, чем появились первые компьютеры, и даже раньше, чем была создана конструктивная теория графов, представил свое решение данной задачи. Немного позднее, в 1938 году Шоке, а затем Флорек, Лукасевич, Перкал, Штейнгауз и Зубжицкий в 1951 году и Соллин в начале шестидесятых снова переоткрывают алгоритм.

Другой известный алгоритм построения минимального остовного дерева восходит к Войтеху Ярнику (1930). Он больше известен под именем алгоритма Прима. Р.Прим независимо от Ярника придумал его в 1956 и представил более подробное и детальное описание, чем первооткрыватель. Еще раз этот алгоритм открыл Эдсгер Дейкстра в 1958 году, но название осталось за Примом, т.к. у Дейкстры уже был алгоритм с его именем.

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

Проблема построения минимального остовного дерева достаточно разносторонняя, и продолжает исследоваться и сегодня.

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

Дано некое выпуклое множество (в нашем случае круг и квадрат). Как в нем надо разместить n точек, чтобы длина минимального остовного дерева была максимальной?

В дальнейшем такое дерево мы будем называть максимальное минимальное остовное дерево (ММОД).

Целью моего исследования является изучить длину ММОД в зависимости от формы выпуклого множества (на примере квадрата и круга). А также установить примерную зависимость длины ММОД от количества вершин.

1. Построение минимального остовного дерева

Рассмотрим общую схему работы алгоритмов построения минимального остовного дерева с использованием жадной стратегии. Итак, пусть дан связный неориентированный граф G(V;E) c n вершинами и весовая функция w: E > R.

Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграф А исходного графа G, который называется промежуточным остовным лесом. Изначально G состоит из n вершин-компонент, не соединенных друг с другом (n деревьев из одной вершины). На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Очередное добавляемое ребро e=(u,v) выбирается так, чтобы не нарушить этого свойства: A u {e} тоже должно быть подграфом минимального. Такое ребро называется безопасным.

Вот как выглядит общий алгоритм построения минимального остовного дерева: MST-GENERIC(G,w) 1: A < 0 2: while (пока) A не является остовом 3: do найти безопасное ребро (u,v) c E для A 4: A < A u {(u,v)} 5: return A

По определению A, он должен оставаться подграфом некоторого минимального остова после любого числа итераций. Конечно, главный вопрос состоит в том, как искать безопасное ребро на шаге 3. Понятно, что такое ребро всегда существует, если A еще не является минимальным остовом (любое ребро остова, не входящее в A). Заметим, что так как A не может содержать циклов, то на каждом шаге ребром соединяются различные компоненты связности (изначально все вершины в отдельных компонентах, в конце A - одна компонента). Таким образом цикл выполняется (n-1) раз.

Далее приводится общее правило отыскания безопасных ребер. Для этого доказана теорема, которая поможет находить безопасные ребра. Предварительно докажем маленькую лемму:

Лемма: пусть Т - минимальное остовное дерево. Тогда любое ребро е из T -безопасное.

Док-во: в Т - (n-1) ребро. На каждом шаге Generic-MST мы добавляли одно безопасное ребро. Всего выполнено (n-1) шагов, следовательно, все ребра в T - безопасные по определению.

Теорема: Пусть G(V;E) - связный неориентированный граф и на множестве Е определена весовая функция w. Пусть А - некоторый подграф G, являющийся в то же время подграфом некоторого минимального остовного дерева T. Рассмотрим компоненту связности К из А. Рассмотрим множество E(K) ребер графа G, только один конец которых лежит в К. Тогда ребро минимального веса из E(K) будет безопасным.

Док-во: Пусть e=(u,v) - минимальное по весу ребро из E(K). Пусть минимальный остов T не содержит e (в противном случае доказываемое утверждение очевидно по приведенной выше лемме). Т.к. T связен, в нем существует некоторый (единственный) ациклический путь p из u в v, и e замыкает его в цикл. Поскольку один из концов e лежит в K, а другой в V \ K, в пути p существует хотя бы одно ребро e'=(x,y), которое обладает тем же свойством. Это ребро не лежит в A, т.к. в A пока что нет ребер между K и V \ K. Удалим из T ребро e' и добавим e. Так как w(e') < w(e), мы получим остовное дерево T', суммарный вес которого меньше суммарного веса T. Таким образом, T не является минимальным остовом. Противоречие. Следовательно, T содержит e. В связи с приведенной теоремой введем следующее Определение. Безопасным ребром e относительно некоторой компоненты связности К из А назовем ребро с минимальным весом, ровно один конец которого лежит в К.

1.1 Алгоритм Борувки

Итак, пусть дан связный неориентированный граф G(V;E) и на нем задана весовая функция . Пусть A - промежуточный остовный лес для графа V. На первом шаге A состоит из всех вершин G и пустого множества ребер. В начале очередной фазы алгоритма Борувки, для каждой компоненты связности промежуточного остовного леса выбирается или корень - вершина, сопоставляемая каждой компоненте. Сделать это можно в простейшем случае с помощью обхода A в глубину: вершина, с которой начинается обход очередной компоненты, и будет ее лидером. В алгоритме за это отвечает процедура CHOOSE-LEADERS. Лидер для вершины v хранится в переменной leader(v).

После того, как лидеры выбраны, для каждой компоненты связности находится безопасное для нее ребро, по существу методом грубой силы. Это работа процедуры FIND-SAFE_EDGES. Безопасное ребро для лидера v' хранится в переменной safe(v'). Как только все такие ребра отобраны, они добавляются к A. Процесс продолжается до тех пор, пока в A присутствует больше одной компоненты связности.

MST-BORUVKA(G,w) 1: A < (V,0) 2: while (пока) в A больше одной компоненты связности 3: do CHOOSE-LEADERS(A) 4: FIND-SAFE-EDGES(G) 5: foreach (для каждого) лидера v' 6: добавить safe(v') в A 7: return A/ Вот простой возможный вид процедуры поиска безопасных ребер: FIND-SAFE-EDGES(G) 1: foreach (для каждого) лидера v' 2: safe(v') < ? 3: foreach (для каждого) ребра (u,v) c E 4: u' < leader(u) 5: v' < leader(v) 6: if u' ? v' then 7: if w(u,v) < w(safe(u')) then 8: safe(u') < (u,v) 9: if w(u,v) < w(safe(v')) then 10: safe(v') < (u,v)

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

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

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

Удобно использовать для хранения компонент структуры данных для непересекающихся множеств, как, например, списки или, что лучше, лес непересекающихся множеств со сжатием путей и объединением по рангу (один из самых быстрых известных методов). Элементами множеств являются вершины графа, каждое множество содержит вершины одной связной компоненты. Для работы с множествами используются следующие процедуры:

Make-Set(v)	Создание множества из набора вершин
Find-Set(v)	Возвращает множество, содержащее данную вершину
Union(u,v)	Объединяет множества, содержащие данные вершины

Общая схема алгоритма выглядит так: MST-KRUSKAL(G,w) 1: A < 0 2: foreach (для каждой) вершины v c V[G] 3: do Make-Set(v) 4: упорядочить ребра по весам 5: for (u,v) c E (в порядке возрастания веса) 6: do if Find-Set(u) ? Find-Set(v) then 7: A < A u {(u,v)} 8: Union(u,v) 9: return A

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

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

При реализации надо уметь на каждом шаге быстро выбирать безопасное ребро. Для этого удобно воспользоваться очередью с приоритетами (кучей). Алгоритм получает на вход граф G и его корень r - вершина, на которой будет наращиваться минимальный остов. Все вершины G, еще не попавшие в дерево, хранятся в очереди с приоритетом Щ. Приоритет вершины v определяется значением key[v], которое равно минимальному весу ребер, соединяющих v с вершинами минимального остова. Поле p[v] для вершин дерева указывает на родителя, а для вершин из очереди, указывает на ноду дерева, в которою ведет ребро с весом key[v] (одно из таких ребер, если их несколько).

Тогда алгоритм Прима выглядит следующим образом: MST-PRIM(G,w, r) 1: Щ < V[G] 2: foreach (для каждой) вершины u c Щ 3: do key[u] < ? 4: key[r] < 0 5: p[r] = NIL 6: while (пока) Щ ? 0 7: do u < EXTRACT-MIN(Щ) 8: foreach (для каждой) вершины v c Adj(u) 9: do if v c Щ и w(u,v) < key[v] then 10: p[v] < u 11:key[v] < w(u,v)

2. Поиск ММОД

Поиск ММОД осуществлялся методом Монте Карло, ввиду вычислительной сложности алгоритма. Поиск осуществлялся с точностью двух знаков после запятой, для каждого значения n от 2 до 20 было произведено 1 000 000 итераций, в каждой из которых случайным равновероятным образом были заданы n точек, для которых было найдено минимальное остовное дерево, и впоследствии была выбрано дерево с максимальной длиной. Естественно полученные данные нельзя считать абсолютно точными. Но для длины ММОД они дают неплохое приближение.

Ниже представлена таблица данных для круга диаметром 1.

Количество вершин дерева	Длина ММОД	Отношение длины ММОД к периметру
2	0.985	0.314
3	1.642	0.523
4	1.904	0.606
5	2.060	0.656
6	2.213	0.705
7	2.462	0.784
8	2.476	0.789
9	2.597	0.827
10	2.617	0.834
11	2.730	0.869
12	2.884	0.919
13	2.883	0.918
14	2.980	0.949
15	3.044	0.969
16	3.082	0.981
17	3.145	1.002
18	3.241	1.032
19	3.352	1.068
20	3.347	1.066
500 (10 000 итераций)	151.799	48.344

Таблица для квадрата со стороной 1

Количество вершин дерева	Длина ММОД	Отношение длины ММОД к периметру
2	1.400	0.350
3	2.025	0.506
4	2.666	0.666
5	2.697	0.674
6	2.799	0.700
7	2.952	0.738
8	3.056	0.764
9	3.187	0.797
10	3.268	0.817
11	3.404	0.851
12	3.491	0.873
13	3.726	0.932
14	3.771	0.943
15	3.765	0.941
16	3.823	0.956
17	4.003	1.001
18	3.951	0.988
19	4.115	1.029
20	4.241	1.060
500 (10 000 итераций)	218.062	54.516

Таблица для прямоугольника со сторонами 1 и 2

Количество вершин дерева	Длина ММОД	Отношение длины ММОД к периметру
2	2.209	0.368
3	2.912	0.485
4	3.616	0.603
5	3.889	0.648
6	4.145	0.691
7	4.286	0.714
8	4.521	0.753
9	4.625	0.771
10	4.789	0.798
11	4.960	0.827
12	5.020	0.837
13	5.085	0.847
14	5.285	0.881
15	5.389	0.898
16	5.603	0.934
17	5.595	0.932
18	5.808	0.968
19	5.829	0.972
20	5.942	0.990

График отношения длины к периметру ММОД для круга (n=)

ММОД для круга (n=500) ММОД для квадрата (n=500)

program gg99dlt12;

Const

MaxN=500;

MaxIter:longint=10000;

Var

output:text;

k:longint;

N,i,j,e,l:1..MaxN;

x,xcopy,y,ycopy:array[1..MaxN] of longint;

D,Dcopy:array[1..MaxN,1..MaxN] of real;

Pred,Predcopy:array[1..MaxN] of byte;

maxlength:real;

procedure InputData;

var p,phi:integer;

begin

for i:=1 to N do

begin

{ p:=random(50);

phi:=random(360);

x[i]:=round(p*cos(phi));

y[i]:=round(p*sin(phi));}

x[i]:=random(101);

y[i]:=random(101);

end;

for i:=1 to N do

for j:=1 to N do

D[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));

end;

function OutputData:real;

var

answer:real;

begin

answer:=0;

for i:=2 to N do answer:=answer+D[i,Pred[i]];

OutputData:=answer;

end;

procedure MinTree;

const

MaxD=1e16;

free=0;

used=1;

var

lbl:array[1..MaxN] of byte;

key:array[1..MaxN] of real;

u,v:byte;

min:real;

begin

for i:=1 to n do begin

key[i]:=MaxD;

lbl[i]:=free; end;

key[1]:=0;

pred[1]:=0;

for i:=1 to N do begin

Min:=MaxD;

for j:=1 to N do

if (lbl[j]=free) and (key[j]<min) then begin

u:=j;

min:=key[j] end;

lbl[u]:=used;

for v:=1 to n do

if (lbl[v]=free) and (D[u,v]<key[v]) then begin

key[v]:=d[u,v];

pred[v]:=u; end;

end;

end;

Begin

randomize;

assign(output,'out.txt');

rewrite(output);

for n:=500 to 500 do begin

maxlength:=0;

for k:=1 to MaxIter do begin

InputData;

MinTree;

if maxlength<OutputData then

begin

maxlength:=OutputData;

xcopy:=x;

ycopy:=y;

Dcopy:=D;

end;

end;

writeln(output,'');

writeln(output,'mmot ',n,' equals ',maxlength/100:0:3,'--',maxlength/400:0:3);

writeln('mmot ',n,' equals ',maxlength/100:0:3,'--',maxlength/400:0:3);

writeln(output,'----x-y--');

write(output,'{');

for e:=1 to N-1 do write(output,'{',xcopy[e],',',ycopy[e],'},');

writeln(output,'{',xcopy[n],',',ycopy[n],'}}');

writeln(output,'---D---');

for l:=1 to n do begin

write(output,'{');

for e:=1 to n do

if e=n then write(output,dcopy[l,e]:0:0) else write(output,dcopy[l,e]:0:0,',');

if l=n then writeln(output,'}') else writeln(output,'},') end;

writeln(output,'');

end;

close(output);

end.

Заключение

Ввиду того, что точные значения для ММОД нами не получены, мы лишь можем выдвигать гипотезы.

Гипотеза 1. Отношение длины ММОД к периметру выпуклой фигуры существенно не зависит от самой фигуры.

Обозначим отношение длины ММОД к периметру выпуклой фигуры для n вершин через C(n).

Гипотеза 2. C(n)~a ln n.

Гипотеза 3. ММОД с n вершинами разбивает множество не более, чем на n областей.

Гипотеза 4. В общем ММОД не симметрично.

В дальнейшем планируется создать алгоритм точного построения ММОД и доказать гипотезы.

Список использованных источников

1. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. -- М.: Вильямс, 2005. -- 1296 с.

2. Курант Р., Роббинс Г. Что такое математика-Элементарный очерк идей и методов. М.: МЦНМО, 2001. 568 с.

3. Зетель С.И. Задачи на максимум и минимум. М.,Л.: ОГИЗ, 1948. 224 с.

4. Шклярский Д.О., Чепцов Н.И., Яглом И.М. Геометрические неравенства и задачи на максимум и минимум. М.: Наука, 1970. 336 с.

5. Берн М.У., Грэм Р.Л. Поиск кратчайших сетей. В мире науки,1989, №3, с. 64-70.