Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 122
Текст из файла (страница 122)
(2) Добавить это ребро во множество ребер Е. (3) Продолжать, пока имеются ребра, обладающие указанными свойствами. ПРИМЕР 16.36. Рассмотрим взвешенный граф, изображенный на рис. 15.125. РЛЗДЕЛ тб.б. Минимальные вотивные деревья 683 Я Рис. 15.125 Выберем ребро (Ь, Н) и добавим его в Е. Далее — ребро (И, е), так что Е = ЦЬ,Ы), (5,е)). Затем добавим ребро (а, е), после чего Е = ЦЬ,41), (д,е), (а, е)). Ребро (а, Ь) добавить нельзя, так как это приведет к образованию цикла, поэтому добавим ребро (1, д), так что Е = ЦЬ, а), (Н, е), (а, е), (У, д) ). Следующим можно добавить (е, 1), и Е = ЦЬ, 4!), (5, е), (а, е), (1, д), (е, 1)). Наконец, добавляем ребро (с,Н), после чего Е = ЦЬ,Н),(й,е), (а,е),(1',д),(е, !')),(с,й). Больше не осталось ребер, которые можно добавлять, поэтому искомое дерево выглядит, как изображенное на рис.
!5.!26. Я Рис. 15.125 ТЕОРЕМА 15.37. Алгоритм Крускала создает минимальное остовное дерево. ДОКАЗАТЕЛЬСТВО. Алгоритм Крускала дает минимальное остовное дерево по построению. Пусть Е1 Е2 ЕЗ Е4 ° ° Ен — ребра дерева Т в том порядке, в котором их выбирает алгоритм Крускала. ПУсть й — наибольшее Целое число такое, что ег, ез, ез, е4,..., еь — РебРа минимального остовного дерева, и пусть Т' является этим деревом.
Если Ь Ф п, то присоединим ребро ее+4 к дереву Т'. Теперь дерево Т' с присоединенным ребром содержит цикл. Удалим из этого цикла е, где е ~ е;, для 1 < 1 < й + 1, и обозначим полученное дерево Т". Вес ребра е не может быть меньше веса еьч.ы если бы это было так, то ребро уже было бы выбрано алгоритмом Крускала или создавало бы цикл, поэтомУ РебРа (ег, ез, ез, е4,, .., еь, е) не могУт составлЯть часть РебеР дерева.
Но это невозможно, поскольку данное множество ребер является частью дерева Т'. Таким образом, поскольку дерево Тн создано из дерева Т' заменой ребра е на ребро, которое не тяжелее, то вес дерева Т" меньше или равен весу дерева Т'. Поэтому Т" — минимальное остовное дерево, которое как часть своего множества РебеР содеРжит (емез,ез,е4,...,еьеь+~). Но это пРотивоРечит определению числа й. Поэтому й = п и Т вЂ” минимальное остовное дерево.
° 884 ГпкВа 75. Деревья Второй и последний из представленных алгоритмов построения минимального остовного дерева называется алгоритмом Прима. Принципиальное отличие алгоритма состоит в том, что всегда имеется дерево, к которому ребра добавляют до тех пор, пока не получится остовное дерево. Используя алгоритм Прима, сначала выбираем вершину оо графа С, а затем выбираем ребро с наименьшим весом е, = (пы оо), инцидентное к вершине оо, и формируем дерево Т,. Следующим выбираем ребро с наименьшим весом ез такое, что одна вершина ребра принадлежит дереву Т,, а вторая — нет, и добавляем его в дерево, после чего получаем дерево Тз с двумя ребрами.
Сформировав дерево Ть, формируем дерево Тьч.ы выбирая ребро с минимальным весом еьч.1 такое, что одна его вершина принадлежит дереву Ть, а другая — нет, и добавляем это ребро в дерево. Продолжаем процесс до тех пор, пока дерево не будет содержать все вершины графа С. Теперь опишем алгоритм формально. Алгоритм Прима нахождения минимального остовного дерева (1) Выбрать вершину по графа С и ребро с наименьшим весом еы для кото- рого оо — одна из вершин, и сформировать дерево Ть (2) Для заданного дерева Ть с ребрами еы ез, ез,..., еь если имеется вершина, не принадлежащая Т„, выбрать ребро с наименьшим весом, смежное с ребром дерева Ть и имеющее вершину вне дерева Ть. Добавить это ребро в дерево Тю формируя дерево Ть~ы (3) Продолжать, пока имеются вершины графа С, не принадлежащие дереву.
ПРИМЕР 15.38. Снова рассмотрим дерево (рис. 15.127). Рис. 15.127 Начав с вершины а, первым выбираем ребро (а, е), поскольку оно имеет минимальный вес. Таким образом, дерево Т, состоит из ребра (а,е). Теперь выбираем ребро (е, п), так как это ребро с минимальным весом из тех, что имеют только одну вершину в дереве Т,. Получаем дерево Тз, изображенное на рис. 15.128. Далее выбираем ребро (4,67, поскольку это ребро с минимальным весом из тех, что имеют только одну вершину в Тз. Получаем Тз — дерево, изображенное на рис. 15.129. Теперь, так как имеется два ребра с одинаковым весом и одной вершиной в Тз, имеем выбор. Предположим, выбрано ребро (Н, с), поэтому дерево Т4 имеет следующий вид (рис.
15.130). РАЗДЕЛ 15УД ЬГинимвпьные осгповные деревья 688 Рис. 15.150 Рис. 15. 129 Рис. 15.125 Следующим выбираем ребро (е, Д. Это ребро имеет минимальный вес из тех, что имеют только одну вершину в дереве Тв, отсюда Тз — дерево на рисунке 15.!31. Ь с Рис 15151 Наконец, выбираем ребро (г,д1. Поскольку это ребро минимального веса из тех, что имеют одну вершину в Т~, а вершина д — последняя из оставшихся вершин, имеем дерево Тв, которое является искомым остовным деревом. сз Теперь докажем, что данный алгоритм в действительности создает минимальное остовное дерево.
ТЕОРЕМА 18.39. Для заданного взвешенного графа С дерево, создаваемое в соответствии с алгоритмом Прима нахождения минимального остовного дерева, является минимальным остовным деревом. ДОКАЗАТЕЛЬСТВО. Из построения дерева следует, что оно остовное. Доказательство того, что оно является минимальным остовным деревом, аналогично доказательству подобного утверждения для алгоритма Крускала.
Пусть ез, ез, ез, е4,..., е — ребра дерева Т в том порядке, в каком они выбраны согласно алгоритму Прима нахождения минимального остовного дерева, и й — наибольшее целое число такое, что емез,ез,ев,...,еь являются ребрами минимального остовного дерева, и Т' является этим деревом. Пусть Ть — дерево, сформированное ребрами ез, ез, ез, е4,..., еь. Если й Ф п, присоединяем ребро еьч.з к дереву Т'. Теперь Т' с новым присоединеннным ребром содержит цикл. В цикле содержится другое ребро е, имеющее только одну вершину в дереве Ть. Удалим ребро е из дерева Т' в (еь.ь~~, формируя дерево Т" с ребром еьвг вместо ребра е. Поскольку ее~~ — ребро с наименьшим весом среди тех, что имеют одну вершину в дереве Ты вес еь.ь~ меньше или равен весу е. Поэтому вес Т" меньше или равен весу Т', так что Т" также является минимальным остовным деревом с ребрами ем ее,ез, е4,..., еь еьвы но это противоречит определению и.
Поэтому й = п, и алгоритм Прима нахождения минимального остовного дерева создает минимальное остовное дерево. 686 ГЛАВА 15. Деревья Алгоритм Прима можно также реализовать с помощью матриц. Для графа С с п вершинами требуется матрица размерности (и+1) х (и+1). Сначала определим и х и весовую матрицу Иг, где И'Π— вес ребра из ея в п,, если ребро из гл в о; существует, и О, если такого ребра нет. После этого добавим и+ 1-ую строку и и+ 1-ый столбец, которые пока будут пустыми. Новую матрицу обозначим через Иг'.
Формально изложим следующий алгоритм. Матричный алгоритм Прима (1) Создать весовую матрицу Иг. (2) Добавить дополнительную строку и столбец, чтобы создать матрицу И". (3) В строке 1 матрицы И" поместить * в последнем столбце. В столбце 1 заменить все числа на О и поместить У в последней строке. (4) Выбрать наименьшее число, так что строка с этим числом имеет * в столбце и+ 1, а столбец с этим числом не содержит У в строке п+ 1. (5) Если число выбрано в строке 1 и столбце 1, то поместить е в последний столбец строки 1, заменить оставшиеся числа в столбце 7' на О, поместить У в строке и + 1 столбца ~' и добавить ребро (о„ о,) в остовное дерево. (6) Продолжать выполнение шагов 4 и 5, пока не останется чисел, которые можно выбирать.
ПРИМЕР 16.40. Предположим, что имеется граф, изображенный на рис. 15.132 поэтому матрицы И' н И'* имеют, соответственно, вид Сначала выбираем строку 1, что означает выбор первой вершины щравной О, так как не собираемся больше возвращаться к вершине ьы и помешаем У в восьмой ((и+ 1)-ой) строке столбца 1, чтобы показать, что столбец 1 не будет больше использован.
Помещаем е в строке 1, тем самым указывая, что можно О 3 О О 2 О 8 3 О 6 1 О О О О 6 О 4 О 5 О О 1 4 О 2 О О 2 О О 2 О 4 О О О 5 О 4 О 3 8 О О О О 3 О О 3 О О 2 О 8 3 О 6 1 О О О О 6 О 4 О 5 О О 1 4 О 2 О О 2 О О 2 О 4 О О О 5 О 4 О 3 8 О О О О 3 О РАЗДЕЛ 1б.б. Минимальные оотовные деревья 667 выбирать значения из этой строки, поскольку она содержит значения ребер из и1 в соседние вершины. Отсюда имеем О 3 О О 2 О О 6 1 О О 6 О 4 О О 1 4 О 2 О О О 2 О О О 5 О 4 О О О О О У Выбираем наименьшее ненулевое значение в этой строке (т.е.
выбираем ребро с наименьшим весом, смежное с и1). В данном случае это значение равно 2 и находится в столбце 5. Таким образом, в качестве первого ребра выбрано ребро (и1 из). Все другие значения в столбце 5 полагаем равными О и в восьмой строке этого столбца устанавливаем значение, равное У, поэтому данную строку уже не будем использовать и не будем больше возвращаться к вершине из. Помещаем * в восьмом столбце строки 5, показывая, что элементы в строке 5 можно теперь использовать так же, как элементы первой строки, поскольку эти строки представляют ребра из и1 и та в смежные вершины. Имеем О 3 О О 2 О О 6 1 О О 6 О 4 О О 1 4 О О О О О 2 О О О 5 О О О О О О О У У Далее выбираем наименьшее ненулевое значение в строке 1 или в строке 5.
В данном случае это значение 2 в столбце 4 строки 5. Таким образом, в качестве следующего ребра выбрано (из и4). Остальные значения в данном столбце полагаем равными О и в восьмой строке данного столбца устанавливаем значение, равное У, поэтому строку не будем больше использовать и не будем больше возвращаться к вершине и4. Помещаем * в восьмом столбце строки 4, показывая, что элементы в этой строке можно теперь использовать так же, как и элементы строки 1 и строки 5, поскольку эти строки представляют ребра из иг и4 и из в смежные вершины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
