Как найти максимальное остовное дерево?

Ответ 1

Да, это так.

Один метод вычисления связующего дерева максимального веса сети G - благодаря Крускалу - можно обобщить следующим образом.

1. Сортируйте края G в порядке убывания веса. Пусть T будет множеством ребер, составляющих связующее дерево максимального веса. Установите T = ∅.
2. Добавьте первое ребро к T.
3. Добавьте следующее ребро к T тогда и только тогда, когда оно не образует цикл в T. Если оставшихся ребер нет, выйдите и сообщите G, что нужно отключиться.
4. Если T имеет n − 1 ребер (где n - количество вершин в G), остановитесь и выведите T. В противном случае перейдите к шагу 3.

Источник: https://web.archive.org/web/20141114045919/http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf.

Ответ 2

Из этот веб-сайт:

"Максимальное связующее дерево - это остовное дерево взвешенного графика, имеющего максимальный вес. Его можно вычислить, отрицая веса для каждого ребра и применяя алгоритм Крускаля (Pemmaraju and Skiena, 2003, стр. 336).

Ответ 3

Если вы инвертируете вес на каждом ребре и сводите к минимуму, вы получаете максимальное остовное дерево? Если это работает, вы можете использовать тот же алгоритм. Конечно же, нулевые веса будут проблемой.

Ответ 4

Хотя этот поток слишком стар, у меня есть другой подход для нахождения максимального связующего дерева (MST) в графе G = (V, E)

Мы можем применить какой-то алгоритм Prim для поиска MST. Для этого я должен определить свойство Cut для максимального взвешенного ребра.

Свойство Cut: пусть говорят, что в любой точке мы имеем множество S, которое содержит вершины, находящиеся в MST (пока предположим, что оно каким-то образом рассчитано). Рассмотрим теперь множество S/V (вершины не в MST):

Претензия: край от S до S/V, который имеет максимальный вес, всегда будет в каждом MST.

Доказательство. Скажем, что в точке, когда мы добавляем вершины к нашему множеству S, максимальное взвешенное ребро от S до S/V равно e = (u, v), где u находится в S и v находится в S/V. Теперь рассмотрим MST, который не содержит e. Добавьте ребро e в MST. Он создаст цикл в оригинальном MST. Пройдите цикл и найдите вершины u 'в S и v' в S/V такие, что u '- последняя вершина в S, после которой мы вводим S/V, а v' - первая вершина в S/V на пути в цикл от u до v.

Удалите ребро e '= (u', v '), и результирующий граф все еще подключен, но вес e больше e' [поскольку e - это максимальное взвешенное ребро от S до S/V в этой точке ], поэтому это приводит к MST, который имеет сумму весов, большую, чем исходный MST. Так что это противоречие. Это означает, что ребро e должно быть в каждом MST.

Алгоритм для поиска MST:

Start from S={s}   //s is the start vertex
while S does not contain all vertices
 do 
 {
  for each vertex s in S
  add a vertex v from S/V such that weight of edge e=(s,v) is maximum 
  }
end while

Реализация: мы можем реализовать с использованием Max Heap/Priority Queue, где ключ - это максимальный вес ребра из вершины в S в вершину в S/V, а значение - сама вершина. Добавление вершины в S равно Extract_Max из кучи, и при каждом Extract_Max измените ключ вершин, смежных с только что добавленной вершиной.

Таким образом, он принимает операции m Change_Key и n операций Extract_Max.

Extract_Min и Change_Key оба могут быть реализованы в O (log n). n - число вершин.

Итак, это занимает время O (m log n). m - количество ребер в графе.

Ответ 5

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

Ответ 6

Только изменение порядка сортировки и выбор тяжелого края в разрезе вершины не гарантируют максимальный спаний леса (алгоритм Kruskal генерирует лес, а не дерево). В случае, если все ребра имеют отрицательные веса, макс. Spanning Forest, полученный от реверса крускала, все равно будет отрицательным весовым путем. Однако идеальным ответом является лес несвязанных вершин. т.е. лес | V | одиночные деревья, или | V | компоненты, имеющие общий вес 0 (не наименее отрицательный).

Ответ 7

Позвольте мне представить алгоритм улучшения:

• сначала создайте произвольное дерево (используя BFS или DFS)
• затем выберите ребро вне дерева, добавьте его в дерево, он сформирует цикл, отбросит наименьший вес в цикле.
• продолжайте делать это, все остальные ребра считаются

Таким образом, мы получим максимальное связующее дерево.

Это дерево удовлетворяет любому ребру вне дерева, если добавлено будет цикл, а край вне <= любые веса ребер в цикле

На самом деле это необходимое и достаточное условие, чтобы остовное дерево было максимальным связующим деревом.

Pf.

Необходимо: Очевидно, что это необходимо, или мы можем обменивать край, чтобы создать дерево с большей суммой весов ребер.

Достаточно: предположим, что дерево T1 удовлетворяет этому условию, а T2 - максимальное остовное дерево.

Тогда для ребер T1 ∪ T2 существуют только T1-ребра, ребра T2, ребра T1 ∩ T2, если мы добавим ребро T1 (x1, xk) в T2, мы знаем, что оно будет образовывать цикл, и мы утверждаем, что в этом цикле должно существовать одно T2-единственное ребро, которое имеет те же веса ребер, что и (x1, xk). Затем мы можем обмениваться этими ребрами, создавая дерево с еще одним ребром, общим с T2 и имеющим ту же сумму весов ребер, повторяя это, мы получим T2. поэтому T1 также является максимальным связующим деревом.

Докажите утверждение:

предположим, что это не так, в цикле мы должны иметь только T2-ребро, так как T1 является деревом. Если ни один из ребер T2 не имеет значения, равного значению (x1, xk), то каждый из ребер T2 образует цикл с деревом T1, тогда T1 имеет петлю, что приводит к противоречию.

Этот алгоритм, взятый у профессора UTD Р. Чандрасекарана, отмечает. Вы можете обратиться сюда: Одноточечные многоточечные потоки

Ответ 8

Измените вес в зарезервированном порядке (вы можете добиться этого, взяв отрицательное значение веса и добавив большое число, целью которого является обеспечение неотрицательных значений). Затем запустите алгоритм семейства на основе geedy на минимальном остовном дереве.