Обнаружение циклов в матрице смежности

Я столкнулся с этим вопросом, когда отвечал на эту математику.stackexchange вопрос. Для будущих читателей я считаю необходимым указать (как это уже сделали другие), что ответ Данила Асоцкого неверен, и предложить альтернативный подход. Теорема Данила состоит в том,что (i, j) запись A^k подсчитывает количество ходов длины k от i до j В G. ключевым моментом здесь является то, что ход разрешается повторять вершины. Так что даже если диагональная запись A^k равна положительно, каждая прогулка, которую считает запись, может содержать повторяющиеся вершины, и поэтому не будет считаться циклом.

Контрпример: путь длиной 4 будет содержать 4-цикл в соответствии с ответом Данила (не говоря уже о том, что ответ будет означать P=NP, потому что он решит проблему цикла Гамильтона).

В любом случае, вот еще один подход. Граф ацикличен тогда и только тогда, когда он является лесом, т. е. он имеет c компонентов и ровно n-C ребер, где n-число вершин. К счастью, существует способ вычисления числа компонент с помощью Лапласианской матрицы L, которая получается путем замены (i,i) записи-A суммой записей в строке i из A (т. е. степенью вершины, помеченной i). Тогда известно, что число компонент G равно N-рангу (L) (то есть кратности 0 как собственного значения L).

Таким образом, G имеет цикл тогда и только тогда, когда число ребер по крайней мере n-(n-ранг(L))+1. С другой стороны, согласно лемме рукопожатия, число ребра-это ровно половина следа (L). Итак:

G является ациклическим тогда и только тогда, когда 0.5*trace(L)=rank(L). Эквивалентно, G имеет цикл тогда и только тогда, когда 0.5*trace(L) >= rank(L)+1.

Если A-матрица смежности направленного или неориентированного графа G, то матрица A^n (т. е. матричное произведение n копий графа A) обладает следующим свойством: запись в строке i и столбце j дает число (направленных или неориентированных) блужданий длины n от вершины i до вершины j. {[4]]} Например, если для некоторого целого числа n матрица A^n содержит хотя бы одну ненулевую диагональную запись, то граф имеет цикл размера n.

Наиболее простым способом проверки ненулевых диагональных элементов матрицы является вычислите матрицу trace(A) = sum(diag(A)) (в нашем случае элементы мощности матрицы всегда будут неотрицательными).

Решение Matlab может быть следующим:

for n=2:size(A,1)
   if trace(A^n) ~= 0
      fprintf('Graph contain cycle of size %d', n)
      break;
   end
end

Этот подход использует DFS, но очень эффективен, потому что мы не повторяем узлы в последующих DFS.

Подход высокого уровня:

Инициализируйте значения всех узлов в -1.

Сделайте DFS из каждого неисследованного узла, установив значение этого узла в значение автоинкрементного значения, начиная с 0.

Для этих DFS обновите значение каждого узла с помощью previous node's value + i/n^k, где этот узел является i - м потомком предыдущего узла и k - глубина исследованные, пропуская уже исследованные узлы (за исключением проверки на большее значение).

Итак, пример для n = 10:

   0.1   0.11   0.111
   j   - k    - p
0 /    \ 0.12
i \ 0.2  l
    m

1   1.1
q - o
...

Можно также использовать i/branching factor+1 для каждого узла, чтобы уменьшить значащие цифры чисел, но это требует дополнительных вычислений для определения.

Итак, выше мы сделали ДФС из i, у которого было 2 ребенка j и m. m не имел детей, j имел 2 детей, .... Затем мы закончили с i и начали другой DFS от следующего неисследованный узел q. Всякий раз, когда вы сталкиваетесь с большим значением, вы знаете, что произошел цикл.

Сложность:

Вы проверяете каждый узел не более одного раза, и на каждом узле вы делаете n проверок, поэтому сложность равна O(n^2), что то же самое, что смотреть на каждую запись в матрице один раз (что вы не можете сделать намного лучше).

Примечание:

Я также просто отмечу, что список смежности , вероятно, будет быстрее, чем смежность матрица, если только это не очень плотный граф.

Это проблема, которую я также нашел. Объяснение, подумал я, заключается в следующем:
когда мы говорим о цикле, неявно мы подразумеваем направленные циклы. Матрица смежности, которую вы имеете, имеет другое значение, когда вы рассматриваете направленный граф; это действительно направленный цикл длины 2. Таким образом, решение $A^n$ на самом деле для ориентированных графов. Для неориентированных графиков, я думаю, исправление будет состоять в том, чтобы просто рассмотреть верхнюю треугольную версию матрицы (остальные заполнены нулем) и повторить процедура. Дайте мне знать, если это правильный ответ.

Если орграф G представлен его матрицей смежности M, то M'=(I-M) будет сингулярным, если в нем есть цикл. I: матрица идентичности того же порядка M

Еще несколько мыслей о матричном подходе... Приведенным примером является матрица смежности для несвязанного графа (узлы 1 и 2 соединены, а узлы 3 и 4 соединены, но ни одна пара не соединена с другой парой). Когда вы вычисляете a^2, Ответ (как указано) - это матрица идентичности. Однако, поскольку Trace (A^2) = 4, это означает, что существует 2 петли длиной 2 (что правильно). Вычисление A^3 не разрешается до тех пор, пока эти петли не будут должным образом идентифицированы и удалены из матрица. Это сложная процедура, требующая нескольких шагов, и подробно описана Р. Л. Норманом, "матричный метод для определения местоположения циклов направленного графа", AIChE J, 11-3 (1965) PP.450-452. Обратите внимание: автору неясно, гарантированно ли этот подход находит все циклы, уникальные циклы и/или элементарные циклы. Мой опыт подсказывает, что он определенно не идентифицирует только уникальные циклы.