Подсчет количества МСЦ в графе

Question

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

Проблема заключается в том:

Сколько MSTS делает данный граф имеет (MST: = Минимальное Spanning Tree)

граф G неориентированный связный граф,

Гарантируется, что степень excee ни одна из вершин в DS 3 :)

предпочитают решения C/C++ (можно понять, как код сформирован алгоритм тоже)

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

UPDATE

в первую очередь найти все MSTs :) O (| E | log | E |)

другие куда хуже :(

Answer 1

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

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

O---O O O O O O---O 
     \/ \/ \/
      X  X  X 
     /\ /\ /\ 
O---O , O O , O---O , O O 

Для каждой группы взаимосвязанных 4 вершин есть 4 = 2^2 возможности выбора.