Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
Алгоритмы и анализ сложности
Часть 3
Эффективные алгоритмы на графах
Задача выделения минимального остова
Пусть 
– связный неориентированный граф, содержащий 
вершин и 
ребер.
Остов (каркас) 
– это некоторый связный суграф 
, 
, не содержащий циклов (остовное дерево). В общем случае можно выделить множество каркасов (например, если – полный граф, то для него можно определить 
различных каркасов).
пары вершин 
в 
единственный соединяющий их путь, добавление к остову любого ребра всегда приводит к образованию цикла.
Любой остов связного графа содержит ровно 
ребро (док-во по МИ):
1. Остов включает 0 ребер при 
и 1 ребро при 
.
2. Пусть остов связного графа с 
вершинами содержит 
ребро. Если к графу будет добавлена новая вершина 
, то достаточно включить только одно ребро вида 
, 
, чтобы полученный граф стал связным. Добавление к графу еще одного ребра (любого) приведет к образованию цикла.
В общем случае, если граф содержит 
компонент связности, то для него можно выделить 
каркасов (остовный лес), которые в сумме будут содержать 
ребер.
Пусть – взвешенный граф (заданы либо списки\массив взвешенных ребер, либо матрица весов ребер 
, 
, 
, если 
). В этом случае можно поставить задачу выделения минимального по весу остова 
(пример – проектирование дорог).
Правила выделения ребер минимального остова определяет
Лемма:
Пусть 
– некоторые подграфы (поддеревья) с попарно непересекающимися множествами вершин 
, 
.
Тогда ребро 
с весом 
принадлежит минимальному остову.
Док-во (от противного): пусть 
и такое ребро 
, что 
, 
и 
.
В минимальном остове пути из 
в 
и из 
в 
. Подграф 
связан с остальной частью графа ребром 
. Поэтому при добавлении образуется цикл. Если из этого цикла удалить ребро , то будет получен новый остов, вес которого меньше, чем у - противоречие.
Пусть в остов добавлено ребро , причем 
. Тогда деревья 
и 
объединятся в одно, т. е. общее число построенных поддеревьев уменьшится на 1.
Процесс построения закончится, когда останется одно дерево, содержащее ребро (или отдельных деревьев, если исходный граф содержит компонент).
В алгоритмах выделения минимального остова в качестве начальных используются 
поддеревьев, содержащих по 1 вершине (и 0 ребер). Затем производится последовательный выбор минимальных по весу ребер, соединяющих текущие поддеревья, и объединение пар поддеревьев.
Алгоритм Прима
Данный алгоритм выгодно использовать, если граф задан матрицей весов и содержит много ребер. Будем считать, что если в графе отсутствует ребро , то соответствующий элемент матрицы весов 
.
В алгоритме производится постоянное расширение только одного поддерева (). Вначале содержит одну вершину 1, затем к последовательно добавляется по одному ребру и одной вершине, «ближайшей» к текущему поддереву.
Пусть на текущем шаге содержит 
вершин. Поиск очередного ребра остова с прямым перебором всех ребер 
потребует 
сравнений, и общая трудоемкость алгоритма составит 
.
Для снижения трудоемкости формируется дополнительный массив 
длины :
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)