Finden von Doppelscheitelpunkten in Diagrammen

Sei ein Graph. Für eine Ecke definieren die (offene) Nachbarschaft zu in . Das heißt, . Definieren Sie zwei Eckpunkte in als Zwillinge, wenn und dieselbe Menge von Nachbarn haben, d. H. Wenn .x ∈ V N ( x ) x G N ( x ) = { y ∈ $G=(V,E)$$x\in V$$N(x)$$x$$G$u , v $N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}$$u,v$$G$v N ( u ) = N ( v $u$$v$$N(u)=N(v)$

Wie schnell können wir ein Paar von Zwillingen in , wenn ein Graph an Ecken und Kanten als Eingabe gegeben ist , wenn ein solches Paar existiert?n m $G$$n$$m$$G$

Wir können überprüfen, ob zwei gegebene Eckpunkte in -Zeit Zwillinge sind , indem wir ihre Nachbarschaften vergleichen. Ein einfacher Algorithmus zum Auffinden von Zwillingen besteht darin, für jedes Paar von Scheitelpunkten zu prüfen, ob es sich um Zwillinge handelt. Dies dauert (und findet auch alle Paare von Zwillingen). Gibt es eine wesentlich schnellere Möglichkeit, ein Paar Zwillinge in der Grafik zu finden (sofern vorhanden)? Gibt es in der Literatur bekannte Arbeiten, die sich mit diesem Problem befassen?O ( n 3$O(n)$$O(n^{3})$

Zwillinge in einem Graphen sind nur Module der Größe 2. Die modulare Zerlegung eines Graphen kann in Zeit gefunden werden. Der modulare Dekompositionsbaum stellt implizit alle Module des Graphen dar und besteht aus drei Arten von internen Knoten: Reihen-, Parallel- und Primärknoten, und die Blätter bestehen aus den einzelnen Knoten. Eine Menge von mindestens zwei Knoten ist ein Modul, wenn und nur wenn es sich um einen Knoten im Baum oder um die Vereinigung einer Menge von untergeordneten Knoten einer Reihe oder eines parallelen Knotens handelt.S ≤ $O(n+m)$$S \subset V$

Um ein Paar von Zwillingsknoten zu finden, falls vorhanden, können wir den modularen Zerlegungsbaum in -Zeit konstruieren . Schauen Sie sich dann die Blätter an. Wenn das übergeordnete Element eines Blattes ein Reihen- oder Parallelknoten ist, muss dieser Knoten mindestens zwei untergeordnete Elemente haben, die ein Doppelpaar bilden. Die Gesamtlaufzeit ist also linear.$O(n+m)$

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

Das Problem ist gleichbedeutend mit der Bestimmung, ob in der Diagrammmatrix zwei gleiche Zeilen vorhanden sind. Wir können Trie auf Zeilen der Graphmatrix konstruieren. Zeit compleixty wird O (n ^ 2)

EDIT: Die Lösungen von @MikleB und @Travis sind sehr clever. Entschuldigung für die übertriebene Antwort.

Es scheint, dass das Problem auf das Matrixmultiplikationsproblem der Adjazenzmatrix reduziert werden kann des Graphen durch Ersetzen der Multiplikation mit EQU (dh NXOR) und Addition mit AND. Befindet sich also ein Zwillingspaar im Graphen, dann ist die resultierende Matrix A A T nicht die Identitätsmatrix, und die Indizes ( i , j ), bei denen der Wert a i , j nicht Null ist, sind genau die Zwillingspaarknoten .$A$$AA^T$$(i,j)$$a_{i,j}$

Nach meinem besten Wissen kann das Matrixmultiplikationsproblem mit α ≈ 2.376 durch den Coppersmith-Winograd-Algorithmus in -Zeit gelöst werden . Wenn praktische Lösungen benötigt werden, sind alle in der Praxis gut funktionierenden Matrixmultiplikationsalgorithmen hilfreich.$O(n^\alpha)$$\alpha \approx 2.376$

Wegen des verrückten Systems auf dieser Seite kann ich nicht direkt kommentieren, aber ich habe ein paar Beobachtungen zu vorhandenen Antworten.

Ich bin mir ziemlich sicher, dass Hsien-Chih Changs Lösung zu A A T korrigieren muss .$A^2$$AA^T$

Die Beobachtung von TheMachineCharmer 4 ist von hinten nach vorne (Gegenbeispiel: [0,0,1], [0,1,0], [0,1,1] hat Determinante 0, aber keine Zwillinge). Wenn Zwillinge existieren, ist die Determinante Null.

Dieser Thread ist ziemlich alt; Niemand scheint jedoch auf die eleganteste und einfachste Herangehensweise gekommen zu sein. Sortieren Sie die Adjazenzliste lexikographisch nach O (n + m) und suchen Sie dann nach Duplikaten (siehe Aho, Hopcroft, Ullman, 74 '). Sie können die modulare Zerlegung verwenden, dies ist jedoch ein totaler Overkill.

Dieser Thread ist alt und die Frage von OP wurde beantwortet, aber ich möchte einen weiteren Algorithmus hinzufügen, um alle diese Paare in linearer Zeit zu finden. Niemand erwähnte die Verfeinerung der Partition !

Dieser Algorithmus ermittelt die Äquivalenzklassen falscher Zwillinge. Der Algorithmus basiert auf einer effizienten Prozedur, die eine Partition verfeinert. Gegeben ein Set Sund eine Partition P = {X1, ..., Xn}. refine(P, S) = {X1 ^ S, X1 - S, X2 ^ S, X2 - S, ..., Xn ^ S, Xn - S}. ^bezeichnet den eingestellten Schnittpunkt und die -eingestellte Differenz. Eine Partition ist stabil, wenn sie nicht weiter verfeinert werden kann. Diese Prozedur benötigt Zeit O (| S |) (siehe Wikipedia-Artikel zur Partitionsverfeinerung), daher ist sie schnell.

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

Die Gesamtzeit beträgt O (| V | + | E |). Dies ist ebenfalls einfach zu programmieren.

Einige Beobachtungen, die helfen könnten

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

2. $|N(a)| \neq |N(b)|$ then $a$ and $b$ can't be twins.

3. If $b \in N(a)$ then $a$ and $b$ can't be twins. This works only if you are looking for non-adjacent twins.

4. If twins exist then determinant of the adjacency matrix is zero.

Fancy idea:

1. Build a complete binary tree with height = |V|.
2. Then start reading one row of adjacency matrix.
3. If you encounter 0 take left otherwise take right.
4. When you reach a leaf store your vertex there.
5. Do this for all the rows. So, in the end each leaf will have neighbors.

Stolen from Inspired by Huffman compression algorithm! :)