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

Question

Пусть A является матрицей смежности для графика G = (V,E). A(i,j) = 1, если узлы i и j связаны с ребром, A(i,j) = 0 в противном случае.

Моей целью является понимание того, является ли G ациклическим или нет. Цикл определяется следующим образом:

• i и j связаны: A(i,j) = 1
• j и k связаны: A(j,k) = 1
• k и i связаны: A(k,i) = 1

У меня реализовано решение, которое перемещает матрицу следующим образом:

• Старт от края (i,j)
• Выберите набор O ребер, которые исходящих из j, то есть, все 1s в j -м ряду A
• Navigate O в моде ДФС
• Если один из путей, созданных в результате этой навигации, приводит к узлу i, то обнаружен цикл

Очевидно, что этот раствор ион очень медленный, так как я должен оценить все пути в матрице. Если A очень большой, требуемые накладные расходы очень велики. Мне было интересно, есть ли способ навигации по матрице смежности, чтобы найти циклы без использования дорогостоящего алгоритма, такого как DFS.

Я хотел бы реализовать свое решение в MATLAB.

Заранее благодарен,

Элеонора.

Answer 1

Основываясь на наблюдении Danil, необходимо вычислить A^n, чуть более эффективный способ сделать так

n = size(A,1); 
An = A; 
for ii = 2:n 
    An = An * A; % do not re-compute A^n from skratch 
    if trace(An) ~= 0 
     fprintf(1, 'got cycles\n'); 
    end 
end 

Answer 2

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

E.g. если для некоторой целочисленной 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 

Answer 3

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

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

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

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

Для этих ДФС-х годов, обновлять значение каждого узла с 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 для каждого узла, чтобы уменьшить значащие цифры числа, но это требует дополнительных вычислений для определения.

Итак, мы сделали DFS от i, в котором было 2 детей j и m. m не было детей, j имел 2 детей, .... Затем мы закончили с i и начали еще одну DFS с следующего неисследованного узла q.

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

Сложность:

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

Примечание:

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

Answer 4

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

Answer 5

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

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

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

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

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

Answer 6

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

Answer 7

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