Jak wykryć, czy złamanie krawędzi spowoduje rozłączenie wykresu?

Question

Mam wykres, który zaczyna się od pojedynczego węzła głównego. Węzły są dodawane jeden po drugim do wykresu. W czasie tworzenia węzła muszą być połączone z węzłem głównym lub innym węzłem za pomocą pojedynczej krawędzi. Krawędzie można również tworzyć i usuwać (jeden po drugim, między dowolnymi dwoma węzłami). Węzły można usuwać pojedynczo. Tworzenie węzłów i krawędzi, operacje usuwania mogą się zdarzyć w dowolnej kolejności.

OK, więc oto moje pytanie: Kiedy krawędź jest usuwana, czy możliwe jest określenie w stałym czasie (tj. Z algorytmem O (1)), czy w ten sposób podzieli się wykres na dwie rozłączne podgrafy? Jeśli tak, to po której stronie brzegu będzie węzeł główny?

Jestem skłonny utrzymać, w rozsądnych granicach, wszelkie dodatkowe struktury danych, które mogą ułatwić wyprowadzenie tych informacji.

Być może nie jest to możliwe w O (1), jeśli tak, wszelkie wskazówki do literatury zostaną docenione.

Edytuj: Wykres jest skierowanym wykresem.

Edycja 2: OK, może mogę ograniczyć skrzynkę do usunięcia krawędzi z węzła głównego . [Edit 3: not, actually] Również, żaden brzeg nie trafi do węzła głównego.

Answer 1

Czy to jest skierowany wykres? Poniższe zakłada nieukierunkowane.

To, czego szukasz, to czy dana krawędź to Bridge na wykresie. Wierzę, że można to znaleźć za pomocą traversal szukając cykli zawierających tę krawędź i byłoby O (| V | + | E |).

O (1) to zbyt wiele, aby zapytać.

Być może okaże się, że szukanie w celu utrzymania dwóch połączonych komponentów na dynamicznych wykresach może być dla Ciebie przydatne.

Eppstein i wsp mają papieru na to: http://www.ics.uci.edu/~eppstein/pubs/EppGalIta-TR-93-20.pdf

który może utrzymać dwa, połączone części brzegowe, w postaci wykresu, gdzie n węzły krawędziowe mogą insercje i delecje. Ma czas O (sqrt (n)) na aktualizację i czas O (log n) na zapytanie.

Za każdym razem, gdy usuniesz, możesz wysłać zapytanie do O (logn), aby ustalić, czy zmieniła się liczba połączonych komponentów z 2 krawędziami. Przypuszczam, że może również powiedzieć, który komponent znajduje się w danym węźle.

Ten artykuł jest bardziej ogólny i dotyczy innych problemów z grafiką, a nie tylko elementów połączonych z dwoma krawędziami.

Proponuję szukać mostów i dynamicznej łączności 2-krawędziowej, aby zacząć.

Nadzieję, że pomaga.

Answer 2

Aby przyspieszyć działanie niewiele ponad oczywiste rozwiązanie O (| V | + | E |), można zachować drzewo opinające, które jest dość łatwe do zaktualizowania w trakcie zmiany wykresu.

Jeśli usunięta zostanie krawędź , a nie w drzewie opinającym, wykres nie zostanie rozłączony i nie będzie wykonywany żaden proces. Jeśli krawędź w drzewie opinającym zostanie usunięta, musisz spróbować znaleźć nową ścieżkę między tymi dwoma wierzchołkami (jeśli ją znajdziesz, użyj jej do zaktualizowania drzewa opinającego, w przeciwnym razie wykres zostanie rozłączony).

A więc, najlepszy przypadek O (1), najgorszy przypadek O (| V | + | E |), ale i tak dość łatwy do wdrożenia.

Answer 3

jak powiedział wcześniej Moron, w rzeczywistości szukasz mostu na swoim wykresie.

Teraz most jest krawędzią, która ma opisany atrybut, a także pochodzi i kończy się na Wyciąć Vertexes. Cut vertex jest dokładnie tym, czym jest Bridge, ale w edycji wierzchołka (węzła).

Tak więc jedynym sposobem (choć dość pochylam hipotezę wstępnej struktury danych), mogę myśleć o tym, aby uzyskać złożoność O (1), jeśli najpierw sprawdzi się każdy węzeł na wykresie, czy jest to Cut Vertex a następnie po prostu w stałym czasie sprawdzanie, czy krawędź, którą chcesz usunąć, jest dołączona do jednego z tych dwóch.

Ustalenie, czy węzeł na wykresie to Cut Vertex, przyjmuje O (m + n), gdzie m = liczba krawędzi i n = liczba węzłów.

Cheers