![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм Краскала
Алгоритм построения кратчайшего дерева для графа G(X, U) состоит в следующем: 1. Выбираем самое короткое ребро графа U1, затем ребро U2, затем самое короткое из оставшихся; 2. Из оставшихся ребер выбираем самое короткое ребро U3 так, чтобы оно не образовывало цикла с выбранными ребрами; 3. Продолжаем эту процедуру. На k-м к выбранным ребрам U1, …, Uк-1 добавляем самое короткое ребро из оставшихся │ U│ -(к-1) ребер так, чтобы оно не образовывало цикла с выбранными ребрами; 4. При k=n-1 процесс заканчивается. Получим граф без циклов с (n-1)-м ребром. На основании теоремы 1 (пункт 2) построенный граф есть дерево, обозначим его T(n-1).
Докажем, что построенное по этому графу дерево T(n-1) кратчайшее. 1.Сначала предположим что G – полный граф, и длины всех его ребер различны. Для доказательства воспользуемся методом от противного. Предположим, что построенное T(n-1) дерево не кратчайшее и имеется отличное от него кратчайшее дерево T. В этом существует две возможности: а) T и Т(n-1) не имеют общих ребер. Присоединим к дереву Т ребро U1Є Т(n-1). В этом случае согласно пункту 4 теоремы 1 в получившемся графе имеется цикл, одним из ребер которого является U1. Выбросим из этого цикла любое ребро U’≠ U1.В результате этой операции получим частичное дерево Т', которое отличается от Т одним ребром: u’ заманено U1. Но l(U1)< l(U'), т.к. U1 – кратчайшее ребро. Следовательно, l(T')< l(T) т.е. Т не кратчайшее дерево; б) Т и Т(n-1) имеют общие ребра U1, U2, …, U(k-1). Пусть Uк есть первое ребро, принадлежащее Т(n-1), но не принадлежащее Т. Рассмотрим граф, который получится присоединением к дереву Т ребра Uк, т.е. Удалив из цикла μ ребро U’, получим дерево 2. Пусть G(X, U)- неполный граф, но его ребра имеют разную длину. Пусть l(U)=L –сумма длин всех ребер графа G. Присоединим к G столько новых ребер, сколько требуется для получения полного графа. Припишем каждому вновь построенному ребру длину lj> L. В полученном полном графе построим кратчайшее дерево Т(n-1). На основании теоремы 2 в графе G есть кратчайшее дерево, длина которого не превосходит L. Частичное дерево графа G будет являться частичным деревом для построенного полного графа. Поэтому ни одно новое ребро в кратчайшее дерево входить не может. Следовательно, для построения кратчайшего частичного дерева в графе G можно пользоваться алгоритмом Краскала.
3. Предположим теперь, что некоторые ребра графа G(X, U) имеют одинаковую длину. Пусть Δ – минимальная ненулевая разность длин ребер. Обозначим
В графе, где некоторые ребра имеют одинаковую длину, кратчайшее частичное дерево может не быть однозначно определенным. Пример Требуется построить газопровод, соединяющий 10 городов (рис.1.). Возможные соединения городов обозначены ребрами, длины которых l(Xi, Xj), представляющие собой стоимость строительства газопровода на участке (Xi, Xj), заданы и обозначены на графе. Как построить самый дешевый газопровод? Задача сводится к отысканию частичного дерева заданного графа, общая длина ребер которого минимальна. Воспользуемся алгоритмом Краскала. Частичное дерево должно содержать (n-1) ребер, т.е. 9. общее число ребер исходного графа
Заданные длины ребер удобно поместить в следующую симметрическую таблицу, в которой достаточно заполнить один из углов – верхний или нижний по отношению к главной диагонали (рис.3.2.2). На пересечении строки Xi и столбца Xj стоит число, равное длине дуги (Xi, Xj), т.е. l(Xi, Xj). Число заполненных клеток равно числу ребер графа. Следуя алгоритму, выбираем самые короткие ребра U1=(X1, X2), U2=(X4, X6), l(U1)=l(U2)=1.
Рис. 2. Отметим это, зачеркнув выбранные числа в таблице и пометив выбранные ребра на графе жирной чертой. Наименьшее из оставшихся чисел в таблице есть 2, т.е. длина дуги (X1, X3). Выбираем в качестве U3 ребро (X1, X3), т.к. оно не образует цикла с выбранными ребрами. Вновь делаем отметку в таблице и на графе и т.д. Получим в результате U4=(X9, X10), U5=(X1, X10), U6=(X4, X5), U8=(X8, X10), U7=(X2, X5), U9=(X7, X6). Длина последнего выбранного ребра равна 9, т.к. ребра графа с меньшими длинами 6, 7, 8 не могут являться ребрами дерева. Сумма длин ребер построенного дерева L=34. Стоимость строительства самого дешевого газопровода по исходным данным составляет 34 денежные единицы.
|