Odniesienie do algorytmu testowania acykliczności mieszanego grafu?

16

Wykres mieszany to wykres, który może mieć zarówno skierowane, jak i nieukierowane krawędzie. Podstawowy nieukierowany wykres jest uzyskiwany przez zapomnienie orientacji skierowanych krawędzi, a w drugim kierunku orientacja mieszanego wykresu jest uzyskiwana przez przypisanie kierunku każdej nieukierunkowanej krawędzi. Zestaw krawędzi tworzy cykl na wykresie mieszanym, jeśli można go zorientować w celu utworzenia ukierunkowanego cyklu. Wykres mieszany jest acykliczny wtedy i tylko wtedy, gdy nie ma cykli.

To wszystko jest standardowe i istnieje wiele opublikowanych prac wymieniających acykliczne wykresy mieszane. Dlatego musi być znany następujący algorytm do testowania acykliczności wykresów mieszanych:

Powtórz następujące kroki:

  • Usuń każdy wierzchołek, który nie ma żadnych skierowanych krawędzi skierowanych i żadnych przypadkowych nieukierowanych krawędzi, ponieważ nie może on być częścią żadnego cyklu.
  • Jeśli jakikolwiek wierzchołek nie ma żadnych skierowanych krawędzi skierowanych, ale ma dokładnie jeden przypadek nieukierunkowanej krawędzi, wówczas każdy cykl używający nieukierunkowanej krawędzi musi nadejść na tej krawędzi. Zastąp nieukierowaną krawędź przez przychodzącą skierowaną krawędź.

Zatrzymaj, gdy nie będzie można wykonać więcej kroków. Jeśli wynikiem jest pusty wykres, oryginalny wykres musi być koniecznie acykliczny. W przeciwnym razie, zaczynając od dowolnego pozostałego wierzchołka, można cofać się przez wykres, na każdym kroku, przechodząc do tyłu przez przychodzącą krawędź lub podążając za nieukierowaną krawędzią, która nie jest używana do osiągnięcia bieżącego wierzchołka, aż do zobaczenia powtarzającego się wierzchołka. Sekwencja krawędzi następująca między pierwszym i drugim powtórzeniem tego wierzchołka (w odwrotnej kolejności) tworzy cykl na wykresie mieszanym.

Artykuł w Wikipedii na temat wykresów mieszanych wspomina o acyklicznych wykresach mieszanych, ale nie wspomina o tym, jak je przetestować, więc chciałbym dodać do tego coś o tym algorytmie, ale w tym celu potrzebuję opublikowanego odniesienia. Czy ktoś może mi powiedzieć, gdzie (lub inny algorytm do testowania acykliczności) pojawia się w literaturze?

ds.algorithms reference-request graph-theory graph-algorithms directed-acyclic-graph David Eppstein
źródło
co się stanie, gdy wierzchołek ma dwie nieukierunkowane krawędzie padające i żadną inną krawędź? Na przykład w nieukierowanym trójkącie. Mam na myśli, czy powyższe zasady dotyczą tej sprawy?
Mateus de Oliveira Oliveira
Nie możesz nic zrobić z takim wierzchołkiem, dopóki inny wierzchołek nie zastosuje reguły, która zorientuje jedną z krawędzi. Jeśli utkniesz w sytuacji, w której istnieją takie wierzchołki i nie możesz zastosować żadnych reguł, wówczas wykres zawiera cykl.
David Eppstein
Może ułatwiłoby to rozważenie tego, co dzieje się w przypadku, gdy wykres nie jest przekierowany. Jednym ze sposobów sprawdzenia, czy jest to las, jest usunięcie liści (stopień jeden wierzchołków) i izolowanych wierzchołków, aż pojawi się albo pusty wykres (to las), albo nietrywialny 2-rdzeniowy (podgraf, w którym wszystkie wierzchołki mają stopień ≥ 2, który koniecznie zawiera cykl). Algorytm mieszanego wykresu degeneruje się do tego w przypadku niekierowanym (z wyjątkiem tego, że raczej orientuje liście niż natychmiast je usuwa), podobnie jak degeneruje się do standardowego algorytmu sortowania topologicznego w ukierunkowanym przypadku.
David Eppstein,
Nie jestem pewien, czy widziałeś: na cs.stackexchange znajduje się post, który zadaje podobne pytanie ref . Odpowiadający daje algorytm do znalezienia cyklu na mieszanym wykresie przez zorientowanie nieukierunkowanych krawędzi, odrzucając wykres, jeśli nie istnieje. Jest też papier (y) w sprawie ustalenia, czy dany wykres mieszany jest silnie orientable ref ale dziwnie, nie mógł znaleźć niczego na znalezienie faktycznie podłączonych komponentów w mieszanych wykresach.
Quanquan Liu,
Dzięki - nie, nie widziałem tego. Pytanie „znajdź orientację, aby wykres zawierał cykl ukierunkowany” jest zdecydowanie takie samo, a algorytm w odpowiedzi wygląda poprawnie. Ale w przeciwieństwie do tego, który opisuję, nie jest to czas liniowy.
David Eppstein,

Odpowiedzi:

1

Znajdowanie cykli mieszanych na wykresie mieszanym jest równoznaczne ze znajdowaniem elementarnych cykli kierunkowych (o długości> = 3) na odpowiednim wykresie ukierunkowanym. Odpowiedni skierowany wykres otrzymuje się z wykresu mieszanego, zastępując każdą nieukierowaną krawędź dwoma skierowanymi krawędziami skierowanymi w przeciwnych kierunkach. Dowód: (1) Każdy elementarny cykl kierunkowy (o długości> = 3) na wykreślniku odpowiada bezpośrednio cyklowi mieszanemu na wykresie mieszanym. (2) Każdy cykl mieszany na wykresie mieszanym zawiera elementarny cykl mieszany o długości> = 3, a każdy taki cykl odpowiada bezpośrednio elementarnemu kierowanemu cyklowi (o długości> = 3) na ukierunkowanym wykresie. (1) i (2) razem potwierdzają oba kierunki wypowiedzi, qed. Szukamy więc referencji, jak obliczyć (wszystkie?) Cykle elementarne (o długości> = 3) na ukierunkowanym wykresie.

Komentarze wskazują, że cs.stackexchange zawiera kilka odpowiedzi na to pytanie, ale nie jest jasne, jak uporządkować wyniki w zwięzłą odpowiedź. Ten post wydaje się ładnie podsumować (najważniejsze?) Ważne odniesienia:

Algorytm R. Tarjana

Pierwszy algorytm, który podałem, został opublikowany przez R. Tarjana w 1973 roku.

Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017

Algorytm DB Johnsona

Algorytm DB Johnsona z 1975 r. Poprawia algorytm Tarjana dzięki jego złożoności.

Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007

W najgorszym przypadku algorytm Tarjana ma złożoność czasową O (n⋅e (c + 1)), podczas gdy algorytmowi Johnsona podobno udaje się pozostać w O ((n + e) ​​(c + 1)), gdzie n jest liczbą wierzchołki, e to liczba krawędzi, a c to liczba cykli na wykresie.

Algorytm KA Hawicka i HA Jamesa

Algorytm KA Hawicka i HA Jamesa z 2008 roku poprawia algorytm Johnsona i eliminuje jego ograniczenia.

Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf
http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf

W przeciwieństwie do algorytmu Johnsona, algorytm KA Hawicka i HA Jamesa jest w stanie obsłużyć wykresy zawierające krawędzie, które zaczynają się i kończą na tym samym wierzchołku, a także wiele krawędzi łączących te same dwa wierzchołki.

Samo badanie acykliczności wydaje się łatwe: oblicz silnie połączone elementy wykresu. Każdy (podstawowy) cykl jest całkowicie zawarty w silnie połączonym komponencie. Silnie połączony komponent zawiera elementarny cykl, jeśli nie jest to drzewo bezkierunkowe.

Zaproponowany algorytm Davida Eppsteina dodatkowo oblicza jeden cykl elementarny jako dowód, a powyższe algorytmy wyliczają wszystkie cykle elementarne. Dowolny wierzchołek lub krawędź, które nie są zawarte w cyklu elementarnym, można usunąć jako krok przetwarzania wstępnego, aby poprawić szybkość powyższych algorytmów. W tym celu można zastosować algorytm Davida Eppsteina, ale nawet jeśli jest on stosowany tylko w silnie połączonych komponentach, nie usuwa on wszystkich możliwych wierzchołków lub krawędzi, które można usunąć. Ale nawet jeśli można to rozszerzyć (obliczenie drzewa wycinanego bloku pozwala przynajmniej usunąć każdy możliwy wierzchołek, który można usunąć), nie jest jasne, czy rzeczywiście poprawiłoby to szybkość powyższych algorytmów.

Thomas Klimpel
źródło
Czy którekolwiek z tych odniesień wspominają nawet o wykresach mieszanych? Wiem o znajdowaniu cykli na ukierunkowanych wykresach. Moje pytanie dotyczyło rozszerzenia tych algorytmów na wykresy mieszane.
David Eppstein,
@DavidEppstein Znalezienie cykli mieszanych na wykresie mieszanym jest równoważne znalezieniu cykli elementarnych (o długości> = 3) na odpowiednim wykresie ukierunkowanym. Znalezienie referencji dla tego stwierdzenia może być trudne, ale udowodnienie, że to stwierdzenie jest proste. Do odpowiedzi dodałem teraz oświadczenie i jego dowód. (Dodano także uwagę bez dowodu, że obliczenie drzewa wycinanego blokowo pozwala usunąć każdy możliwy wierzchołek, który można usunąć bez wpływu na cykle elementarne.)
Thomas Klimpel
Ok, ale nadal nie są one również liniowe.
David Eppstein
@DavidEppstein Sam test acykliczności odbywa się w czasie liniowym. Ale masz rację, czas, w którym dowolny z tych algorytmów musi znaleźć pierwszy obwód elementarny (o długości> = 3), nie jest liniowy (w najgorszym przypadku). Co gorsza, większość dostępnych implementacji algorytmu Johnsona wydaje się wykorzystywać czas dłuższy niż O ((n + e) ​​(c + 1)), gdy jest stosowany do pojedynczego ukierunkowanego koła (z n wierzchołkami, e = n krawędziami, a c = 1 elementarny cykli). Mimo to miała to być poprawna odpowiedź, ponieważ artykuł Johnsona wydaje się być najczęściej cytowanym odniesieniem do „znajdowania obwodów elementarnych”.
Thomas Klimpel