Python: как найти МАКСИМАЛЬНОЕ остовное дерево графика [дубликат]

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

Хотя этот поток слишком стар, у меня есть другой подход для нахождения максимального связующего дерева (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 - количество ребер в графе.

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

Из этого сайта:

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

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

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

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

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

Это дерево удовлетворяет любому ребру вне дерева, если добавленный будет формировать цикл, а край вне & lt; = любые веса ребер в цикле

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

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. Вы можете обратиться сюда: Одноточечные многоточечные потоки