Алгоритм обратного удаления

Алгоритм обратного удаления — это алгоритм в теории графов, использующийся для получения минимального остовного дерева из данного связного рёберно взвешенного графа. Впервые алгоритм появился в статье Краскала[1], но не следует его путать с алгоритмом Краскала, который появился в той же статье. Если граф не связен, этот алгоритм найдёт минимальное остовное дерево для каждой отдельной части графа. Множество этих минимальных остовных деревьев называется минимальным остовным лесом, который содержит все вершины графа.

Алгоритм является жадным алгоритмом, дающим лучшее решение. Он противоположен алгоритму Краскала, который является другим жадным алгоритмом поиска минимального остовного дерева. Алгоритм Краскала начинает с пустого графа и добавляет рёбра, в то время как алгоритм обратного удаления начинает с исходного графа и удаляет рёбра из него. Алгоритм работает следующим образом:

• Начинаем с графа G, который содержит список рёбер E.
• Проходим через E в порядке убывания веса рёбер.
• Для каждого ребра проверяем, не приводит ли его удаление к несвязному графу.
• Осуществляем удаления, не приводящие к несвязности графа.

Псевдокод

 1  функция ReverseDelete(рёбра[] E)
 2    сортируем E в убывающем порядке
 3    Определяем индекс i ← 0
 4    пока i < размер(E)
 5       Определяем ребро ← E[i]
 6	   удаляем E[i]
 7	   если граф не связен
 8             E[i] ← ребро
 9   	        i ← i + 1
 10   возвращаем рёбра[] E

Пример

В следующем примере зелёные рёбра просматриваются алгоритмом, а красные рёбра алгоритмом удалены.

	Это исходный граф. Числа рядом с рёбрами отражают вес рёбер.
	Алгоритм начинает с максимального по весу ребра, в данном случае это ребро DE с весом 15. Поскольку удаление ребра DE не приводит к несвязному графу, ребро удаляется.
	Следующее самое тяжёлое ребро — FG, так что алгоритм проверит, не приведёт ли удаление ребра к несвязности. Поскольку удаление ребра не приводит к несвязности графа, ребро удаляется.
	Следующее самое тяжёлое ребро — BD, так что алгоритм проверит, не приведёт ли удаление ребра к несвязности и удаляет ребро.
	Следующее ребро для проверки — EG, которое удалять нельзя, поскольку это приведёт к отделению вершины G от графа. Следовательно, следующее ребро для удаления — BC.
	Следующее самоё тяжёлое ребро — EF, так что алгоритм проверит это ребро и удаляет его.
	Алгоритм просматривает оставшиеся рёбра и не находит пригодных для удаления, таким образом, это финальный граф, который и возвращает алгоритм.

Время работы

Можно показать, что алгоритм работает за время ${\displaystyle O(E\log V(\log \log V)^{3})}$ («O» большое и «o» малое), где E — число рёбер, а V — число вершин. Эта граница достигается следующим образом:

• Сортируем рёбра по весу с помощью сортировки сравнения, которая работает за время ${\displaystyle O(E\log E)}$, которое может быть сокращено до ${\displaystyle O(E\log V)}$ используя факт, что самое тяжёлое ребро E входит в V^2.
• Имеется E итераций цикла.
• Операции удаление ребра, проверки связности полученного графа и (если граф несвязен) вставки ребра могут быть сделаны за время ${\displaystyle O(\log V(\log \log V)^{3})}$ на операцию[2].

Доказательство корректности

Рекомендуется прочитать сначала доказательство алгоритма Краскала.

Доказательство состоит из двух частей. Сначала доказывается, что рёбра, которые остаются после работы алгоритм принимают форму остовного дерева. Затем доказывается, что это остовное дерево имеет оптимальный вес.

Остовное дерево

Оставшийся подграф (g), полученный алгоритмом связен, поскольку алгоритм проверяет это в строке 7. Подграф не может содержать цикла, поскольку в противном случае двигаясь вдоль цикла можно найти наибольшее по весу ребро и удалить его. Тогда g должна быть остовным деревом основного графа G.

Минимальность

Мы покажем по индукции, что следующее утверждение P верно: Если F является множеством рёбер, оставшихся в конце цикла, то имеется некоторое минимальное остовное дерево, которое (его рёбра) является подмножеством F.

1. Ясно, что P выполняется до начала цикла пока. Поскольку взвешенный связный граф всегда имеет минимальное остовное дерево и поскольку F содержит все рёбра графа, то это минимальное остовное дерево должно быть подмножеством F.
2. Теперь предположим, что P верно для некоторого промежуточного множества рёбер F и пусть T будет минимальным остовным деревом, которое содержится в F. Мы должны показать, что после удаления ребра e в алгоритме существует некоторое (возможно другое) остовное дерево T', которое является подмножеством F.
   1. если следующее удалённое ребро e не принадлежит T, то T=T' является подмножеством F и P выполняется.
   2. в противном случае, если ребро e принадлежит T: сначала заметим, что алгоритм удаляет только рёбра, которые не вызывают разрушения связности F. Таким образом, удаление ребра e не приводит к несвязности графа F, но удаление e приводит к несвязности дерева T (поскольку входит в T). Предположим, что e разбивает T на подграфы t1 и t2. Поскольку весь граф после удаления e остаётся связным, должен существовать путь между t1 и t2 (отличный от e), так что должен существовать цикл C в F (до удаления e). Теперь мы должны иметь другое ребро в этом цикле (пусть это будет f), которое не принадлежит T, но входит в F (поскольку если все рёбра цикла были бы в дереве T, оно не было бы деревом). Мы теперь утверждаем, что T' = T — e + f является минимальным остовным деревом, которое является подмножеством F.
   3. Сначала мы доказываем, что T' является остовным деревом. Мы знаем, что удаление ребра в дереве и добавление другого ребра не создаёт цикла и мы получаем другое дерево с теми же вершинами. Поскольку T было остовным деревом, T' должно быть также остовным деревом. Тогда добавление «f» не создаёт какого-либо цикла, поскольку удаляется «e» (заметим, что дерево T содержит все вершины графа).
   4. Затем мы доказываем, что T' является минимальным остовным деревом. У нас есть три случая для рёбер «e» и «f», определяемых функцией веса wt.
      1. Случай wt(f) < wt(e), что невозможно, поскольку из этого следует, что вес дерева T' строго меньше T. Поскольку T является минимальным остовным деревом, это просто невозможно.
      2. Случай wt(f) > wt(e), что невозможно, поскольку когда мы проходим по рёбрам в убывающем порядке весов, мы должны видеть «f» первым. Поскольку мы имеем C, то удаление «f» не приводи к несвязности в F, так что алгоритм должен был бы удалить ребро из F ранее. То есть, «f» не принадлежит F, что невозможно (мы доказали принадлежность f на шаге 4).
      3. Случай wt(f) = wt(e), так что T' является минимальным остовным деревом, так что снова P выполняется.
3. Таким образом, P выполняется после завершения цикла (то есть после просмотра всех рёбер) и мы доказали, что в конце F становится остовным деревом и мы знаем, что F имеет минимальное остовное дерево в качестве подмножества, так что F само должно быть минимальным остовным деревом.

См. также

• Алгоритм Краскала
• Алгоритм Прима
• Алгоритм Борувки
• Алгоритм Дейкстры

Примечания

1. Kruskal, 1956.
2. Thorup, 2000.

Ссылки

• Jon Kleinberg, Éva Tardos. Algorithm Design. — New York: Pearson Education, Inc., 2006.
• Joseph B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem // Proceedings of the American Mathematical Society. — 1956. — Т. 7, вып. 1. — С. 48–50. — doi:10.2307/2033241. — JSTOR 2033241.
• Mikkel Thorup. Near-optimal fully-dynamic graph connectivity // Proc. 32nd ACM Symposium on Theory of Computing. — 2000. — С. 343–350. — doi:10.1145/335305.335345.