Znajdowanie bliźniaczych wierzchołków na wykresach

Niech będzie wykresem. Przez wierzchołek , określa za (otwarty) sąsiedztwie w . To znaczy, . Zdefiniuj dwa wierzchołki w aby były bliźniakami, jeżeli i mają ten sam zestaw sąsiadów, to znaczy, jeśli .$G=(V,E)$$x\in V$$N(x)$$x$$G$$N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}$$u,v$$G$$u$$v$$N(u)=N(v)$

Biorąc pod uwagę wykres na wierzchołkach i krawędziach jako dane wejściowe, jak szybko możemy znaleźć parę bliźniaków w , jeśli taka para istnieje?$G$$n$$m$$G$

Możemy sprawdzić, czy dwa podane wierzchołki są bliźniakami w czasie , porównując ich sąsiedztwa. Prostym algorytmem znajdowania bliźniaków jest zatem sprawdzenie, dla każdej pary wierzchołków, czy są bliźniakami. Zajmuje to czas (a także wyszukuje wszystkie pary bliźniaków). Czy istnieje znacznie szybszy sposób na znalezienie (jeśli istnieje) pary bliźniaków na wykresie? Czy w literaturze znane są prace dotyczące tego problemu?$O(n)$$O(n^{3})$

Bliźnięta na wykresie to tylko moduły wielkości 2. Modułowy rozkład grafu można znaleźć w czasie . Modułowe drzewo dekompozycji domyślnie reprezentuje wszystkie moduły wykresu i składa się z trzech rodzajów węzłów wewnętrznych: szeregowych, równoległych i pierwotnych, a liście składają się z poszczególnych węzłów. Zestaw co najmniej dwóch wierzchołków jest modułem wtedy i tylko wtedy, gdy jest to jakiś węzeł w drzewie lub związek jakiegoś zestawu potomków szeregu lub równoległego węzła.S ⊂ $O(n+m)$$S \subset V$

Aby więc znaleźć parę bliźniaczych węzłów, jeśli istnieją, możemy zbudować modułowe drzewo dekompozycji w czasie . Następnie spójrz na liście, jeśli rodzicem jakiegokolwiek liścia jest węzeł szeregowy lub równoległy, wówczas ten węzeł musi mieć co najmniej dwoje dzieci, które tworzą podwójną parę. Zatem całkowity czas pracy jest liniowy.$O(n+m)$

http://en.wikipedia.org/wiki/Modular_decomposition

Problem jest równoważny z ustaleniem, czy w macierzy graficznej są dwa równe rzędy. Możemy konstruować trie na wierszach macierzy graficznej. Kompleksem czasowym będzie O (n ^ 2)

EDYCJA: rozwiązania @MikleB i @Travis są bardzo sprytne. Przepraszam za odpowiedź za nadmierną liczbę zabójstw.

Wydaje się, że problem można sprowadzić do problemu mnożenia macierzy na macierzy przyległości wykresu, zastępując mnożenie EQU (to znaczy NXOR) i dodając AND. Tak więc, gdy znajduje się para bliźniąt na wykresie, to otrzymana osnowa T nie będzie macierz tożsamości, a indeksy ( i , j ) , gdzie wartość I , J , nie zero są dokładnie węzły parę bliźniaczych .$A$$AA^T$$(i,j)$$a_{i,j}$

Według mojej najlepszej wiedzy problem mnożenia macierzy można rozwiązać w czasie pomocą α ≈ 2,376 za pomocą algorytmu Coppersmith – Winograd . Jeśli potrzebne są praktyczne rozwiązania, każdy algorytm mnożenia macierzy działa dobrze, w praktyce jest miły.$O(n^\alpha)$$\alpha \approx 2.376$

Z powodu szalonego systemu na tej stronie nie mogę komentować bezpośrednio, ale mam kilka uwag na temat istniejących odpowiedzi.

Jestem całkiem pewny potrzeb rozwiązanie Hsien-Chih Changa skorygować do A A T .$A^2$$AA^T$

Obserwacja 4 maszyny jest zwrócona do przodu (kontrprzykład: [0,0,1], [0,1,0], [0,1,1] ma wyznacznik 0, ale nie ma bliźniaków). Jeśli istnieją bliźniaki, wyznacznikiem jest zero.

Ten wątek jest dość stary; wydaje się jednak, że nikt nie wybrał najbardziej eleganckiego i prostego podejścia. Leksykograficznie posortuj listę sąsiedztwa w czasie O (n + m), a następnie sprawdź duplikaty (patrz Aho, Hopcroft, Ullman, 74 '). Możesz użyć rozkładu modułowego, ale jest to całkowita przesada.

Wątek jest stary i na pytanie OP udzielono odpowiedzi, ale chciałbym dodać inny algorytm, aby znaleźć wszystkie takie pary w czasie liniowym. Nikt nie wspominał o ulepszeniu partycji !

Ten algorytm znajduje klasy równoważności fałszywych bliźniaków. Algorytm opiera się na wydajnej procedurze, która udoskonala partycję. Biorąc pod uwagę zestaw Si partycję P = {X1, ..., Xn}. refine(P, S) = {X1 ^ S, X1 - S, X2 ^ S, X2 - S, ..., Xn ^ S, Xn - S}. ^oznacza zestaw przecięcia i -ustaw różnicę. Partycja jest stabilna, jeśli nie można jej dalej udoskonalać. Ta procedura wymaga czasu O (| S |) (patrz artykuł Wikipedii na temat udoskonalania partycji), więc jest szybka.

Algorithm:

P = {V} // initial partition consists of the vertex set
for every vertex v:
    P = refine(P, N(v)) // refine with the open neighborhood of v

Całkowity czas to O (| V | + | E |). Jest to również łatwe do zaprogramowania.

Kilka uwag, które mogą pomóc

1. $a,b \in V$$a$$b$$c$$d$$c \in N(a)$$d \in N(b)$

2. $|N(a)| \neq |N(b)|$$a$$b$

3. $b \in N(a)$$a$$b$

4. Jeśli istnieją bliźniaki, wyznacznikiem macierzy przylegania jest zero.

Fantazyjny pomysł:

1. Zbuduj kompletne drzewo binarne o wysokości = | V |.
2. Następnie zacznij czytać jeden wiersz macierzy sąsiedztwa.
3. Jeśli napotkasz 0, skręć w lewo, w przeciwnym razie skręć w prawo.
4. Kiedy dotrzesz do liścia, przechowuj tam swój wierzchołek.
5. Zrób to dla wszystkich wierszy. W końcu każdy liść będzie miał sąsiadów.

Skradziony z algorytmu kompresji zainspirowanego przez Huffmana! :)