Практикум по дискретной математике в среде виртуальной лаборатории системы ДО ИТМО (стр. 5 )

5.  Если ограничение на степень вершины нарушено, то соответствующий минимальный элемент вычеркивается из рассмотрения и повторяется выполнение п.3, т. е. ищется новый минимум.

6.  Матрица просматривается до тех пор, пока не будут включены все строки.

Пример:

Пусть дан взвешенный псевдограф G(X, U). Достроим его до полного, присвоив добавленным ребрам (на рисунке эти ребра показаны прерывистыми линиями) веса равные . Присвоим также имеющимся петлям веса равные .

Рассмотрим решение задачи по шагам. Для этого построим матрицу весов полного графа D, порожденного исходным псевдографом. Обозначим: X* - множество вершин остовного дерева, а U* - множество его ребер. Положим вначале, что X* = { x1 }.

Помечаем в матрице D 1-ую строку "*" и находим min в этой строке:

	1	2	3	4	5
*1	Б	7	3	4	4
2	7	Б	Б	Б	9
3	3	Б	Б	Б	2
4	4	Б	Б	Б	5
5	4	9	2	5	Б

*Здесь и далее Б - обозначает .
Т. к. d13 = 3 - min, то U* = {(x1, x3)} и X* = {x1, х3)}.

Вычеркиваем 1-ый и 3-ий столбцы, а 3-ью строку помечаем "*". Находим минимальный элемент в строках, отмеченных символом "*":

	1	2	3	4	5
*1	-	7	-	4	4
2	-	Б	-	Б	9
*3	-	Б	-	Б	2
4	-	Б	-	Б	5
5	-	9	-	5	Б

Т. к. d35 = 2 - min, то U* = {(x1, x3), (х3, х5)} и X* = {x1 ,х3 ,х5 }

Отмечаем 5-ую строку и вычеркиваем 5-ый столбец:

	1	2	3	4	5
*1	-	7	-	4	-
2	-	Б	-	Б	-
*3	-	Б	-	Б	-
4	-	Б	-	Б	-
*5	-	9	-	5	-

Т. к. d14 = 4 - min, то U* = {(x1, x3), (х3, х5), (х1, х4)} и X* = {x1 ,х3 ,х4 ,х5 }

Отмечаем 4-ую строку и вычеркиваем 4-ый столбец:

	1	2	3	4	5
*1	-	7	-	-	-
2	-	Б	-	-	-
*3	-	Б	-	-	-
*4	-	Б	-	-	-
*5	-	9	-	-	-

Т. к. d12 = 7 - min, то U* = {(x1, x3), (х3, х5), (х1, х4), (х1, х2)} и X* = {x1, х2, х3, х4, х5}

Дерево построено, суммарный вес= d13 +d35 +d14 +d12 =3+2+4+7=16.

Метод Краскала

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

Алгоритм состоит из следующей последовательности действий:

1.  Создается список ребер R, содержащий длину ребра, номер исходной вершины ребра (i), номер конечной вершины ребра (j),признак включения данного ребра в дерево.

2.  Данный список упорядочивается в порядке возрастания длин ребер.

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

4.  Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к п. 3.

Пример:

Вначале полагают, что количество деревьев равно n. Каждый шаг алгоритма - попытка добавить из отсортированного списка ребер очередное ребра. Ребро включается, если оно не образует цикла. Каждое включенное ребро уменьшает количество деревьев в списке на 1, пока в списке не останется ровно одно дерево. Это дерево и есть решение, минимальное остовные дерево графа или дерево Прима, полученное с помощью алгоритма Краскала.

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

Отсортированный по возрастанию список ребер этого графа:

N	1	2	3	4	5	6	7
ребро	(х3 ,х5 )	(х1 ,х3 )	(х1 ,х4 )	(х1 ,х5 )	(х4 ,х5 )	(х1 ,х2 )	(х2 ,х5 )
длина	2	3	4	4	5	7	9

Решение задачи по шагам приведено в следующей таблице: