Finden von Doppelscheitelpunkten in Diagrammen

22

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 VG=(V,E)xVN(x)xGu , v GN(x)={yV|{x,y}E}u,vGv N ( u ) = N ( v )uvN(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 GGnmG

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(n3)

gphilip
quelle
Sie können die Nachbarschaften durchlaufen und sie einer Hashtabelle hinzufügen. Siehe auch
Radu GRIGore
1
Dies ist Übung 2.17 hier books.google.co.uk/…
Radu GRIGore
Jemand mit Bearbeitungsbefugnissen sollte die Definition von Zwillingen korrigieren. (Siehe die Kommentare zur Antwort von TheMachineCharmer oder die Definition in dem Buch, das ich verlinkt habe.)
Radu GRIGore

Antworten:

21

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 VO(n+m)SV

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

Travis Service
quelle
Vielen Dank, dass Sie mich auch mit Modular Decomposition bekannt gemacht haben!
gphilip
12

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)

MikleB
quelle
6
Die gleiche Idee auf Nachbarschaftslisten ergibt . O(m+n)
Radu GRIGore
Jetzt mache ich eine Fliege
fertig
2
Dies kann etwas verallgemeinert werden. Wenn wir das Problem wie folgt umformulieren "Gegeben (wobei ) Finde unterschiedliches , so dass " dann für ganz geordnetes Ein Ansatz besteht darin, für jedes auszuwerten , sie zu sortieren und die sortierte Liste auf Duplikate zu überprüfen. Der Versuch ist effektiv radix Art. f ( x ) : = N ( x ) x 1 x 2 f ( x 1 ) = f ( x 2 ) Y f ( x ) x Xf:X->Y.f(x): =N(x)x1x2f(x1)=f(x2)Y.f(x)xX
Peter Taylor
8

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 .EINEINEINT(ich,j)einich,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α)α2,376

Hsien-Chih Chang 張顯 張顯
quelle
Super das funktioniert! : Ich denke, es wird ausreichen, nur die obere Hälfte der zu bewerten . was denkst du? EIN2
Pratik Deoghare
1
@TheMachineCharmer: Danke :) Ja, wenn das Diagramm ungerichtet ist.
Hsien-Chih Chang 張顯 張顯
Ja. Genau! :)
Pratik Deoghare
5

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 .EIN2EINEINT

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.

Peter Taylor
quelle
Ich sehe kein Problem mit . Beispiele? Übrigens ist das System auf dieser Seite NICHT verrückt! :)EIN2
Pratik Deoghare
würde für ungerichtete Graphen funktionieren (für die A == A T ist ), im Allgemeinen jedoch nicht für gerichtete Graphen. Das UND über XNOR muss zwei Zeilen von A vergleichen, und die Matrixmultiplikation verarbeitet eine Zeile aus der ersten Matrix mit einer Spalte aus der zweiten. EIN2EINEINT
Peter Taylor
System ist vielleicht nicht verrückt, aber vielleicht nicht intuitiv für das erste Mal Poster. Sie können antworten, aber keinen Kommentar abgeben ... aber Ihre Kommentare waren meiner Meinung nach nett genug, um die Veröffentlichung zu rechtfertigen. Sobald Sie mehr Ansehen aufgebaut haben, wird das System Ihrer Meinung nach ziemlich süchtig machen.
Hardmath
3
Antworten zu können, aber nicht zu kommentieren, ist verrückt. Neue Benutzer müssen sich entscheiden, ob sie nicht hilfreich sein oder am falschen Ort antworten möchten.
Peter Taylor
3

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.

Nathan Lindzey
quelle
2

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.

Saadtaame
quelle
1

Einige Beobachtungen, die helfen könnten

  1. ein,bVeinbcdcN(ein)dN(b).

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

  3. If bN(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! :)

Pratik Deoghare
quelle
2
The 3rd point is true only if we look for non-adjacent twins. In the usual notion of twins, a and b are allowed to be adjacent.
Mathieu Chapelle
1
Peter Taylor, Mathieu Chapelle: Danke! Ich habe die Antwort bearbeitet, um die Änderungen widerzuspiegeln. @Serge Gaspers: Ich denke in diesem Fall muss die Bedingung seinN(ein)-b=N(b)-ein.
Pratik Deoghare