Эффективный алгоритм поиска петель в графах

Мне нужно изучить сопротивление основного кластера проникающей сети проводников. Отдельные провода промаркированы от 1 до n. Я представляю сеть графом G(V,E) и нахожу ее матрицу смежности A, где A_ij = 1, если провода i и j соприкасаются, иначе 0.

Мой вопрос следующий: учитывая, что мне нужно реализовать Законы Кирхгофа в основном перколяционном кластере , мне нужен алгоритм, который возвращает все, в идеале, наименьшие циклы в кластере. Знаете ли вы об алгоритме (мой сейчас используется грубая сила и неэффективен), который находит все циклы внутри графа из его матрицы смежности?


graph algorithm adjacency-matrix
person Mathusalem    schedule 16.10.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

В общем, может быть экспоненциально много простых циклов (циклов), поэтому, поскольку вам нужны только «самые маленькие», звучит так, как будто вы не хотите их всех. Если вы хотите написать уравнения, соответствующие второму закону Кирхгофа для всех возможных циклов, то достаточно использовать только уравнение для каждого цикла в на основе цикла. Существует алгоритм полиномиального времени для нахождения базиса цикла, который использует наименьшее общее количество ребер (базис минимального цикла). Однако вместо реализации этого алгоритма может быть достаточно переключиться с дуговых переменных xuv на разности узловых переменных yv - yu ( зафиксируйте одну переменную узла для каждого подключенного компонента равной нулю).

person David Eisenstat    schedule 16.10.2014
comment
Спасибо за Ваш ответ. Я действительно почти ничего не понимаю в теории графов. Это немного «шокировано», так как я предполагаю, что это понятия из линейной алгебры, применяемые к теории графов, хотя сначала я действительно не понимаю, что представляет собой векторное пространство. Думаю, я прочитаю статью в вики. - person Mathusalem; 17.10.2014