Wykrywanie cykli w macierzy sąsiedztwa

Question

Niech A będzie macierzą sąsiedztwa dla wykresu G = (V,E). A(i,j) = 1, jeśli węzły i i j są połączone z krawędzią, w innym przypadku A(i,j) = 0.

Moim celem jest zrozumienie, czy G jest acykliczne, czy nie. Cykl określa się w następujący sposób:

• i i j są podłączone: A(i,j) = 1
• j i k są podłączone: A(j,k) = 1
• k i i są podłączone: A(k,i) = 1

mam zaimplementowano rozwiązanie nawigujące w macierzy w następujący sposób:

• Rozpocznij od krawędzi (i,j)
• Wybierz zestaw O krawędzi, które są ustępującej od j, czyli wszystkie 1s w j -tego rzędu A
• Nawiguj O w modzie DFS
• Jeśli jedna z ścieżek wygenerowanych z tej nawigacji prowadzi do węzła i, wówczas wykrywany jest cykl

Oczywiście ten roztwór Jon jest bardzo wolny, ponieważ muszę ocenić wszystkie ścieżki w macierzy. Jeśli A jest bardzo duży, wymagany narzut jest bardzo duży. Zastanawiałem się, czy istnieje sposób nawigacji w macierzy sąsiedztwa, aby znaleźć cykle bez użycia drogiego algorytmu, takiego jak DFS.

Chciałbym wdrożyć moje rozwiązanie w MATLAB.

Z góry dziękuję,

Eleanore.

Answer 1

podstawie obserwacji Danil, trzeba obliczyć A^n, nieco bardziej efektywny sposób robić to jest

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

Jeśli A jest macierzą sąsiedztwa skierowanego lub nieukierunkowanego wykresu G, to macierz A^n (tj. Iloczyn macierzowy z n kopii A) ma następującą właściwość: wpis w wierszu i oraz kolumna j podaje liczbę (ukierunkowane lub niekierowane) spacery o długości n od wierzchołka i do wierzchołka j.

E.g. jeśli dla pewnej liczby całkowitej macierz A^n zawiera co najmniej jeden niezerowy wpis przekątnej, to wykres ma cykl o rozmiarze n.

Najłatwiejszym sposobem sprawdzenia niezerowych przekątnych elementów macierzy jest obliczenie macierzy trace(A) = sum(diag(A)) (w naszym przypadku elementy mocy matrycy będą zawsze nieujemne).

rozwiązanie Matlab mogą być następujące:

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

Answer 3

Podejście to wykorzystuje DFS, ale jest bardzo skuteczna, ponieważ nie powtórzyć w kolejnych węzłów DFS-tych.

podejście wysokiego szczebla:

Inicjalizacja wartości wszystkich węzłów do -1.

Wykonaj DFS z każdego nierozpoznanego węzła, ustawiając wartość tego węzła na wartość automatycznie zwiększaną, począwszy od 0.

Dla tych DFS, zaktualizuj wartość każdego węzła z previous node's value + i/n^k jeżeli węzeł jest i th dziecko z poprzedniego węzła i k jest głębokość zbadać, Pomijanie już zbadane węzły (z wyjątkiem sprawdzania większej wartości).

więc przykładem dla n = 10:

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

1 1.1 
q - o 
... 

Można również użyć i/branching factor+1 dla każdego węzła, aby zmniejszyć znaczące cyfry numerów, ale to wymaga dodatkowych obliczeń do określenia.

Tak więc powyżej zrobiliśmy DFS z i, który miał 2 dzieci j i m. m nie miał dzieci, j miał 2 dzieci, .... Potem skończyliśmy z i i uruchomiliśmy kolejny DFS z kolejnego niezbadanego węzła q.

Kiedy pojawia się większa wartość, wiadomo, że wystąpił cykl.

Złożoność:

sprawdzić każdy węzeł co najwyżej raz, a na każdym węźle zrobić n kontrole, więc złożoność jest O(n^2), która jest taka sama jak patrząc na każdego wpisu w matrycy raz (co nie może zrobić nic lepszego niż).

Uwaga:

będę też po prostu pamiętać, że adjacency list będzie prawdopodobnie szybciej niż macierz sąsiedztwa, chyba że jest to bardzo gęsty wykres.

Answer 4

To jest problem, ja również. Wyjaśnienie, pomyślałem, jest następujące:
kiedy mówimy o cyklu, domyślnie mamy na myśli ukierunkowane cykle. Matryca sąsiedztwa, którą masz, ma inne znaczenie, gdy weźmiesz pod uwagę skierowany wykres; jest to rzeczywiście skierowany cykl o długości 2. A więc rozwiązanie $ A^n $ jest w rzeczywistości dla kierowanych wykresów. W przypadku grafów niekierowanych, myślę, że poprawką byłoby po prostu rozważenie górnej trójkątnej wersji matrycy (reszta wypełniła się zero) i powtórzyć procedurę. Daj mi znać, jeśli to jest właściwa odpowiedź.

Answer 5

Natknąłem się na to pytanie, odpowiadając na to pytanie: math.stackexchange. Dla przyszłych czytelników mam wrażenie, że muszę wskazać (tak jak inni już), że odpowiedź Danila Asotsky'ego jest niepoprawna i zapewnić alternatywne podejście. Twierdzenie Danila odnosi się do tego, że wpis (i, j) A^k liczy liczbę spacerów o długości k od i do jw G.Kluczową rzeczą tutaj jest to, że dozwolone jest powtarzanie wierzchołków. Zatem nawet jeśli przekątne wpisy A^k są dodatnie, każdy krok, w którym wpis się liczy, może zawierać powtarzające się wierzchołki, a więc nie będzie liczony jako cykl.

Kontrprzykład: ścieżka o długości 4 zawierałaby 4-cykle zgodnie z odpowiedzią Danila (nie wspominając, że odpowiedź oznaczałaby P = NP, ponieważ rozwiązałaby problem z cyklem Hamiltona).

W każdym razie, tutaj jest inne podejście. Wykres jest acykliczny wtedy i tylko wtedy, gdy jest to las, tj. Ma c komponentów i dokładnie n-c krawędzi, gdzie n jest liczbą wierzchołków. Na szczęście istnieje sposób obliczania liczby komponentów przy użyciu Laplacian matrix L, który uzyskuje się przez zastąpienie wpisu (i, i) -A sumą wpisów w wierszu i A (tj. Stopień oznaczony wierzchołkiem ja). Wtedy wiadomo, że liczba składników G jest n-kategorią (L) (tj. Krotnością 0 jako wartością własną L).

Zatem G ma cykl wtedy i tylko wtedy, gdy liczba krawędzi wynosi co najmniej n- (n-ranga (L)) + 1. Z drugiej strony, dzięki ręcznemu lememu, liczba krawędzi jest dokładnie równa połowie śladu (L). A więc:

G jest acykliczny wtedy i tylko wtedy, gdy 0,5 * ślad (L) = pozycja (L). Równoważnie, G ma cykl wtedy i tylko wtedy, gdy 0,5 * ślad (L)> = pozycja (L) +1.

Answer 6

Niektóre więcej myśli o podejścia macierzy ... Przykład cytowany matryca przylegania do rozłączonego wykresie (węzły 1 & 2 są połączone, i węzły 3 & 4 są połączone, ale też para jest dołączona do inna para). Kiedy obliczysz A^2, odpowiedź (jak podano) jest macierzą tożsamości. Jednakże, ponieważ Trace (A^2) = 4, oznacza to, że istnieją 2 pętle o długości 2 (co jest poprawne). Obliczanie A^3 jest niedozwolone, dopóki te pętle nie zostaną poprawnie zidentyfikowane i usunięte z macierzy. Jest to wymagająca procedura wymagająca kilku kroków i jest szczegółowo opisana przez R.L. Normana, "Macierzowa metoda lokalizacji cykli ukierunkowanego wykresu", AIChE J, 11-3 (1965) str. 450-452. Uwaga: autor nie jest pewny, czy takie podejście gwarantuje znalezienie WSZYSTKICH cykli, UNIKALNYCH cykli i/lub cykli ELEMENTARNYCH. Moje doświadczenie sugeruje, że zdecydowanie nie identyfikuje TYLKO unikalnych cykli.

Answer 7

Jeśli dwuznak G jest reprezentowany przez jego matrycę przyległości M, wówczas M '= (I - M) będzie liczbą pojedynczą, jeśli jest w nim cykl. I: macierz tożsamości o tej samej kolejności M