Korzystanie z silnie połączonych komponentów Algo as Cycle Detection

Question

Rozumiem, że jeśli zbiór wierzchołków jest częścią silnie połączonych komponentów, wówczas wszystkie te wierzchołki w komponencie mogą się nawzajem stykać; cykl.

Teraz chciałbym użyć tego faktu i twierdzić, że jeśli wykres G = (V, E) ma cykl, to ten cykl MUSI BYĆ wewnątrz scc.

Innymi słowy, wszystkie cykle muszą należeć do scc (moje roszczenie).

Nie mogę myśleć o jakimkolwiek kontrprzykładu do mojego twierdzenia, więc chciałbym wiedzieć, czy są jakieś cykle na wykresie, które nie są częścią SC.
Lub Czy moje roszczenie jest prawidłowe?

Answer 1

Niech e = (u, v) jest krawędzią w pytaniu. Zauważmy, że jest to cykl w G zawierający e if i tylko , jeśli jesteś podłączony do v w G {e}. Nasz algorytm po prostu uruchamia DFS z u na G {e}, i wyprowadza yes jeśli v jest osiągalny z u i nie ma inaczej. Algorytm ten działa w czasie liniowym, ponieważ DFS działa w czasie liniowym (a my wykonujemy tylko część algorytmu DFS znajdowania komponentu zawierającego u). Ten algorytm jest wyraźnie poprawny. Jeśli u jest połączone z v w G {e} za pomocą ścieżki p, możemy dodać krawędź e do p, aby utworzyć cykl. W przeciwnym razie usunięcie e z G rozłącza u i v.

Answer 2

To prawda. Jeśli zbiór wierzchołków jest w cyklu, to wszystkie są osiągalne od siebie (przechodząc przez cykl), więc z definicji są SCC.

Mimo, że nie jest to dokładnie to problem programowania :)