it-swarm-ru.tech

Как найти максимальное связующее дерево?

Работает ли на нем противоположность алгоритма Крускала для минимального связующего дерева? Я имею в виду, выбирая максимальный вес (Edge) каждого шага?

Любая другая идея, чтобы найти максимальное связующее дерево?

50
user467871

да, это так,

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

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

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

С этого сайта:

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

36
Tony The Lion

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

6
duffymo

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

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

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

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

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

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

Алгоритм поиска МСТ:

 Начать с S = {s} // s - это начальная вершина 
, В то время как S не содержит всех вершин 
 Сделать 
 {
 Для каждой вершина s в S 
 добавляет вершину v из S/V так, чтобы вес Edge e = (s, v) был максимальным 
} 
 конец, в то время как 

Реализация: мы можем реализовать, используя 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 - количество ребер в графе.

4
Imran

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

1
Shen Yang

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

1
Sojourner

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

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

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


Это дерево удовлетворяет любому ребру за пределами дерева, если добавленное будет формировать цикл, а ребро вне <= любых весов ребра в цикле

Фактически, это необходимое и достаточное условие для того, чтобы остовное дерево было максимальным остовным деревом.

Коэффициент мощности.

Необходимо: очевидно, что это необходимо, или мы могли бы поменять местами Edge, чтобы сделать дерево с большей суммой весов Edge.

Достаточно: предположим, что дерево 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 приводит к противоречию.

enter image description here


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

1
XueYu