Подсчитать количество MST в графе

Я думал об этой проблеме много часов, но не нашел решения

Проблема в :

Сколько MST имеет данный граф
(MST: = Минимальное связующее дерево)

граф G является неориентированным связным графом

Гарантируется, что степень вершины не превышает 3 🙂

предпочитаю решения на C / C ++ (также может понимать алгоритм, подобный коду)

и, пожалуйста, с низким заказом 🙂 (время выполнения)

ОБНОВИТЬ

прежде всего найти все МСТ 🙂
O (| E | log | E |)

другие куда хуже sad

2

Решение

Вы можете попробовать с возвратом. На каждом шаге для одной из «листовых» вершин решите, сколько «выходных» ребер использовать.

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 возможностей на выбор.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]