Оптимальность алгоритмов Крускала и Прима
Теперь мы можем легко доказать оптимальность алгоритмов Крускала и Прима. Оба алгоритма включают ребро только в том случае, когда это включение оправдывается свойством сечения (4.17).
(4.18) Алгоритм Крускала строит минимальное остовное дерево графа G.
Более того, никакое ребро из S в V − S еще не было обнаружено, так как любое такое ребро может быть добавлено без создания цикла, а значит, было бы добавлено алгоритмом Крускала.
Следовательно, e — ребро с минимальной стоимостью, у которого один конец принадлежит S, а другой — V – S, и, согласно (4.17), оно принадлежит минимальному остовному дереву.
Итак, если нам удастся показать, что результат (V, T) алгоритма Крускала действительно является остовным деревом графа G, то дело будет сделано. Очевидно, (V, T) не содержит циклов, поскольку алгоритм проектировался для предотвращения создания циклов.
Кроме того, если граф (V, T) не был связным, то существовало бы непустое множество узлов S (не равное всему множеству V ), такое, что не существует ребра из S в V − S. Но это противоречит поведению алгоритма: мы знаем, что поскольку граф G является связным, между S и V – S существует как минимум одно ребро, и алгоритм добавит первое из таких ребер при его обнаружении.
Алгоритм Прима строит минимальное остовное дерево графа G.
Доказательство. Для алгоритма Прима также очень легко показать, что он добавляет только ребра, принадлежащие любому возможному минимальному остовному дереву.
В самом деле, при каждой итерации алгоритма существует множество S Ӭ V, на базе которого было построено частичное остовное дерево, и добавляется узел v и ребро e, которые минимизируют величину mine=(u, v):uѮS ce.
По определению e является ребром с минимальной стоимостью, у которого один конец принадлежит S, а другой — V – S, поэтому по свойству сечения (4.17) оно присутствует в каждом минимальном остовном дереве.
Также тривиально показывается, что алгоритм Прима строит остовное дерево графа G — а следовательно, он строит минимальное остовное дерево.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу