Расчет по Алгоритму Краскала

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

Рисунок 5.1

Решение

Составляем матрицу длин и всем элементам, лежащим на главной диагонали и ниже нее, присваиваем значение :

Формируем таблицу меток и локальных степеней (см. табл. 5.1).

На нулевом шаге все вершины получают метки, равные их номерам , а локальные степени , , длина строящегося дерева  и множество ребер в дереве êR ê= Æ.

На первом шаге просматриваем элементы верхней половины матрицы D и выбираем из них минимальный элемент  (при наличии нескольких элементов с одинаковыми минимальными значениями выбираем элемент с наименьшими индексами i и j).

Таблица  5.1.

Номер вершины	Значения меток  и степеней  вершин на очередном шаге
	0		1		2		3		4			5			6			7		8		9
1	1	0	1	0	1	0	1	1							3	1						3	2
2	2	0	2	0	2	0	2	1							2	0						3	1
3	3	0	3	1	3	1	3	2							3	2						3	2
4	4	0	4	0	4	1	3	2							3	2						3	2
5	5	0	3	1	3	1	3	1							3	2						3	2
6	6	0	6	0	4	1	3	1							3	1						3	1
	0
	0		3,6		7,2		11,3		11,3			11,3			17,6			17,6		17,6		18,3
	0		1		2		3		3			3			4			4		4		5

Помечаем элемент  и на его место записываем . Метки у 3-й и 5-й вершин разные ( , ), поэтому соединяем вершины 3-ю и 5-ю ребром (см. Рис 5.2, а): метки у них становятся равными: . Локальные степени обеих вершин равны единицам –  и .

а)	б)
в)	г)
д)	е)
ж)	з)

Рис. 5.2.

Длина L строящегося дерева равна 3,6, а множество ребер êR ê = 1 (см. 1-й шаг табл. 1). На втором шаге выбирается минимальный элемент , на третьем –  (см. рис. 5.2, б,в). На места выбранных элементов в матрице D записываем . Получили матрицу D₁:

В выделяемом минимальном дереве построены один фрагмент с суммарной длиной . У вершин фрагмента (3-й, 4-й, 5-й, 6-й) метки , а локальные степени - , .

Выбранный из оставшихся минимальный элемент , на очередном 4-м шаге, не может быть включен во множество R ребер дерева, поскольку образует цикл с ребрами ранее построенного фрагмента (на это указывают одинаковые метки у 5-й и 6-й вершин ).(см. рис. 5.2, г).

На пятом шаге выбранные ребра  соответственно не образуют циклов, но их присоединение нарушает ограничение на локальную степень 3-й вершины. (см. рис. 5.2, д).

Выбранный из оставшихся минимальный элемент , на очередном 6-м шаге, метки у 1-й и 5-й вершин разные ( , ), поэтому соединяем вершины 1-ю и 5-ю ребром (см. Рис 5.2, е): метки у них становятся равными: . Локальные степени обеих вершин равны единицам –  и .

На седьмом шаге выбранные ребра  соответственно не образуют циклов, но их присоединение нарушает ограничение на локальную степень 3-й вершины. (см. рис. 5.2, ж)

На восьмом шаге выбранные ребра  соответственно образует цикл, и их присоединение нарушает ограничение на локальную степень 3-й вершины. (см. рис. 5.2, з)

На девятом шаге присоединяется ребро , при этом выполняется условие , т. е. дерево построено: , длина дерева  (рис. 5.3).

Рис. 5.3

Машинный расчет по Алгоритму Краскаля

Рис. 5.5 (а)

Рис. 5.5 (б)

\ Рис. 5.5 (в)

Рис. 5.5 (г)

Рис. 5.5 (д)

Рис. 5.5 (е)

В результате машинного расчета решения дерево построено: , длина дерева  (см. рис. 5.5, а-е).

Расчет по Алгоритму Прима

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

Решение

Составляем матрицу расстояний

D=		1	2	3	4	5	6
	1	0	11	10	9	14	22
	2	11	0	3	12	11	13	1
	3	10	3	0	9	8	12	1+1
	4	9	12	9	0	7	15
	5	14	11	8	7	0	8	1
	6	22	13	12	15	8	0

Просматриваем все строки матрицы и выбираем элемент, являющийся минимальным. Поскольку таких элементов два . Помечаем его, локальные степени 2-й и 3-й вершин увеличиваем на единицу – . Исключаем из рассмотрения (вычеркиваем) все элементы второго и третьего столбцов. Соединяем  и  (рис. 5.6, а).

Просматриваем вторую и третью строки матрицы. Выбираем элемент ; локальные степени 3-й и 5-й вершин увеличиваем на единицу – ; . Исключаем из рассмотрения элементы 5-го столбца и 3-й строки (к 3-й вершине  подключено уже два ребра). Соединяем  с  (рис. 5.6, б). Получили матрицу D₁:

D1=		1	4	6
	1	0	9	22	1
	2	11	12	13	1+1
	4	9	0	15	1+1
	5	14	7	8	1+1
	6	22	15	0	1

Просматриваем вторую и пятую строки. Выбираем элемент ; ; . Соединяем вершины  и  (рис. 5.6, в). Исключаем из рассмотрения четвертый столбец и пятую строку, поскольку .

Просматриваем вторую и четвертую строки. Выбираем элемент ; ; . Соединяем  с  (рис. 5.6, г). Поскольку , исключаем из рассмотрения первый столбец и вторую строку. И, наконец, просматриваем первую и четвертую строки. Выбираем ; , . Соединяем  с  (рис. 5.6, д). Исключаем из рассмотрения последний шестой столбец.

Минимальное связывающее дерево, полученное в результате решения, приведено на рис.5.6, д.

Рис. 5.5

а)	б)
в)	г)
д)

Рис. 5.6

Множество ребер в нем . Суммарная длина его ребер L равна 43.