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

Да.

Один из методов вычисления остовного дерева максимального веса сети 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.

Из Maximum Spanning Tree в Wolfram MathWorld:

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

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

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

Мы можем применить какой-то алгоритм Прима для поиска 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 - количество ребер в графе.

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

• сначала построить произвольное дерево (используя 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 Р. Чандрасекарана. Вы можете обратиться сюда: Многотерминальные потоки одного товара

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

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

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