Самый маленький набор наименьших колец

Question

У меня есть невзвешенный неориентированный подключенный граф. Как правило, это химическое соединение с большим количеством циклов бок о бок. Проблема распространена в этой области и называется, как говорится в названии. Хорошим алгоритмом является Хортон. Однако по-видимому, я не вижу точной информации об алгоритме, шаг за шагом.

Очевидно, моя проблема в этом, Algorithm for finding minimal cycles in a graph, но, к сожалению, ссылка на сайт отключена. Я нашел только код python алгоритма Figueras, но Figuearas не работает в каждом случае. Иногда он не находит всех колец. Проблема похожа на эту проблему: Find all chordless cycles in an undirected graph, я пробовал, но не работал для более сложных графиков, подобных моим. Я нашел 4-5 источников необходимой информации, но алгоритм полностью не объяснен.

Я, кажется, не нашел алгоритма для SSSR, хотя это кажется общей проблемой, главным образом в области химии.

Answer 1

Алгоритм Хортона довольно прост. Я опишу его для вашего случая использования.

1. Для каждой вершины V, вычислить поиск в ширину дерева с корнем в ст. Для каждого ребра Wx таким образом, что V, W, X попарно различны и таким образом, что наименьший общий предок ш и х равно v , добавьте цикл, состоящий из пути от v до w, края wx и пути от x назад до v.

2. Отсортируйте эти циклы по размеру, не уменьшая и учитывайте их по порядку. Если текущий цикл может быть выражен как «исключающий ИЛИ» циклов, рассмотренных до него, то он не является частью базы.

Тест на этапе 2 является наиболее сложной частью этого алгоритма. То, что вам нужно сделать, в основном, заключается в том, чтобы записать принятый цикл и цикл-кандидат как матрицу инцидентов 0-1, строки которой индексируются по циклу и столбцы которых индексируются по краю, а затем запускают гауссовское исключение на эту матрицу, чтобы увидеть, делает всю нулевую строку (если это так, отбросьте цикл кандидата).

С некоторыми усилиями можно экономить время на повторное удаление принятых циклов каждый раз, но это оптимизация.

Например, если мы имеем график

a---b 
| /| 
|/| 
|/ | 
c---d 

тогда мы имеем матрицу, как

 ab ac bc bd cd 
abca 1 1 1 0 0 
bcdb 0 0 1 1 1 
abdca 1 1 0 1 1 

где я обманываю немного, потому что abdca не на самом деле один из циклов, генерируемых в Этап 1.

Ликвидация осуществляется следующим образом:

ab ac bc bd cd 
1 1 1 0 0 
0 0 1 1 1 
1 1 0 1 1 

row[2] ^= row[0]; 

ab ac bc bd cd 
1 1 1 0 0 
0 0 1 1 1 
0 0 1 1 1 

row[2] ^= row[1]; 

ab ac bc bd cd 
1 1 1 0 0 
0 0 1 1 1 
0 0 0 0 0 

так, что множество циклов зависит (не держите последнюю строку).