Подсчитать количество MST в графе
Я думал об этой проблеме много часов, но не нашел решения
Проблема в :
Сколько MST имеет данный граф
(MST: = Минимальное связующее дерево)
граф G является неориентированным связным графом
Гарантируется, что степень вершины не превышает 3 🙂
предпочитаю решения на C / C ++ (также может понимать алгоритм, подобный коду)
и, пожалуйста, с низким заказом 🙂 (время выполнения)
ОБНОВИТЬ
прежде всего найти все МСТ 🙂
O (| E | log | E |)
другие куда хуже sad
Решение
Вы можете попробовать с возвратом. На каждом шаге для одной из «листовых» вершин решите, сколько «выходных» ребер использовать.
function add_some_vertex_edges(leaves, edge):
if |leaves| == |V|:
num_of_MSTs += 1
return
v = leaves.pop() # takes one vertex and removes it from leaves
let v_edge be set of incident edges to v that are not already in edges and that don't make cycle if added to edges
for each combination of edges from v_edge:
add_edges(leaves + incident_vertices, edges + edge_combination)
add_some_vertex_edges({v}, {})
Так как степень вершин <= 3, для каждого листа используется одно ребро, чтобы «ввести» его, и из-за этого | v_edge | <= 2, и из-за этого дерево поиска является узким.
Наихудшее время выполнения — O (2 ^ n), но, вероятно, в практических случаях это быстро. Есть примеры с наихудшим числом MST. Пример, который я могу придумать, — это две параллельные линии вершин и связи между ними.
O---O---O---O---O---O---O---O---O---
\ / \ / \ / \ / \ /
X X X X X ...
/ \ / \ / \ / \ / \
O---O---O---O---O---O---O---O---O---
В этом примере есть ровно 2 ^ (n / 2) MST. Чтобы вычислить это, возьмите 2 крайние левые вершины. Они могут быть связаны с остальной частью графика 4 способами.
O---O O O O O O---O
\ / \ / \ /
X X X
/ \ / \ / \
O---O , O O , O---O , O O
Для каждой группы 4 соединенных вершин есть 4 = 2 ^ 2 возможностей на выбор.
Другие решения
Других решений пока нет …