Berechnen Sie die relationale Zusammensetzung in

7

Definitionen: Sei eine DAG ohne Selbstschleifen, und und sind Graphen.G=(V,E)XGYG

Input: . Ausgabe: Die relationale Zusammensetzung relationale Zusammensetzung in .X,Y XYO(|E||V|)

  • Fall 1:. Zwei for-Schleifen über und : Runtime .|E||V|E(X)E(Y)O(|E|2)O(|E||V|)
  • Fall 2:|V||E|
    1. Zeichnen Sie den Graphen : . Wir nennen Kanten von schwarz und von rot.(V(G),E(X)E(Y))(O(|V|)+O(|2E|)))E(X)E(Y)
    2. Sortieren Sie es topologisch (Kahn: ). Die erste Ebene sei , und die Kanten wechseln von einer Ebene zu einer höheren Ebene.O(|V|)+O(|E|)0
    3. Zeichnen Sie dieses Diagramm zweimal.
    4. Entfernen Sie in der ersten Kopie jede rote Kante, die auf einer geraden Ebene beginnt, und jede schwarze Kante, die auf einer ungeraden Ebene beginnt: .O(E)
    5. Entfernen Sie in der zweiten Kopie alle "schwarzen geraden" und "roten ungeraden": .O(E)
    6. Für das erste Exemplar:
      • für alle Knoten auf Ebeneu2i
      • für alle Knoten auf Ebenev2i+1
      • Berichtskante (Laufzeit ).(u,v)O(V2)O(EV)
    7. Für die zweite Kopie: Gleiches gilt für " ".2i+1
    8. Vereinigen Sie die gemeldeten Knoten und werfen Sie Duplikate aus (ich hoffe, die Diagrammdarstellung erlaubt dies).O(V2)<=O(EV)

Könnten einige von Ihnen bitte meinen Algorithmus überprüfen und prüfen, ob

  • das ist richtig
  • es ist inO(|E||V|)

Wenn es korrekt ist, "existiert" mein Algorithmus bereits? Wenn nicht, könnten Sie eine Alternative anbieten? Ich werde die erste Antwort akzeptieren, aber positiv bewerten, wenn noch mehr Leute so freundlich sind, dies zu überprüfen.

BEARBEITEN: Schritt 6 Scheint manchmal in . Ich wünschte, das wäre nicht wahr. Hat jemand einen funktionierenden Algorithmus?O(E2)

Johannes
quelle

Antworten:

4

Das Problem ist in Schritt 6 (nach meinem Verständnis).

Im Wesentlichen sollten Sie nach Sequenzen ob und . Die topologische Sortierung ist korrekt, da in solchen Sequenzen die beiden Kanten nacheinander kommen müssen.(u,w)(w,v)(u,w)E(X)(w,v)E(Y)

Eine Kante ist schwarz, wenn sie zu . Eine Kante ist rot, wenn sie zu . Eine Kante kann in diesem Fall zwei Farben haben. (u,w)E(X)(w,v)E(Y)

Ein Knoten prüft jeden Nachbarn [st ist schwarz], wenn für einen seiner Nachbarn einen roten Rand . In diesem Fall:uw(u,w)w(w,v)uVdeg(u).wN(x)deg(w)=O(E2)

Soweit ich verstanden habe: Sie haben einige nicht benötigte Kanten gefiltert (Schritt 4,5) - es kann jedoch einen schlimmsten Fall geben, der zu einer höheren Komplexität als . O(E2)

AJed
quelle
Danke, du hast recht! Ich kann nicht alle Knotenpaare melden, ich muss den Kanten folgen. Hmm ja ich denke das kann zu . Ich denke, mein Algorithmus kann es nicht :(O(E2)
Johannes
Beantwortet das Ihre Frage?
AJed
Na ja, mehr oder weniger. Ich wünschte, jemand würde eine Alternative für Schritt 6 finden, aber Sie werden akzeptiert.
Johannes
6

Satz 2.29 auf Seite 60 der Parsing-Theorie von Sippu und Soisalon-Soininen gibt einen Algorithmus zur Berechnung (unter anderem Operationen auf Beziehungen) der Zusammensetzung zweier Beziehungen an. Der Algorithmus läuft in der Zeit , wobei die Zeit ist, die benötigt wird, um Vereinigungs- oder Zuweisungsoperationen an Scheitelpunktsätzen durchzuführen. Das Ergebnis dieser Operation ist eine Menge von Scheitelpunkten pro Scheitelpunkt, die seine Nachbarn darstellen. Dieser Algorithmus arbeitet mit beliebigen Graphen, nicht nur mit azyklischen.O(t(|V|+|E|))t

Alex ten Brink
quelle
Sieht gut aus, obwohl ich keinen Zugang zu diesem Buch habe, auch nicht von der Universität :(
Johannes
@Johannes, probieren Sie die Bibliothek Ihrer Universität aus - ich habe auch keinen Zugriff auf das Buch und habe es auch aus der Bibliothek meiner Universität erhalten.
Alex Ten Brink