Einfache Möglichkeit, festzustellen, ob ein bestimmter Graph ein Untergraph eines anderen Graphen ist?

Question

Ich suche nach einem Algorithmus, um zu überprüfen, ob ein bestimmter Graph ein Untergraph eines anderen gegebenen Graphen ist.

Ich habe nur wenige Bedingungen, um dieses NP-Vollständigkeitsproblem etwas praktikabler zu machen.

• Die Diagramme haben ca. <20 Eckpunkte.
• Die Grafiken sind DAG.
• Alle Scheitelpunkte sind nicht eindeutig beschriftet, und die entsprechenden Scheitelpunkte im Hauptdiagramm und im Untergraphen sollten dieselbe Beschriftung haben.Ich weiß nicht, ob ich die richtigen Terminologien verwende (da ich keinen Graphentheoriekurs belegt habe ...).Es wird etwa so aussehen:

Der Liniengraph A--B ist ein Teilgraph von A--B--A, aber A--A ist kein Teilgraph von A--B--A.

Alle Vorschläge sind in Ordnung.Das ist übrigens keine Hausaufgabenfrage.:D

Answer 1

Wenn die Etiketten eindeutig sind, für ein Größengraphen N, es gibt O(N^2) Die Kanten unter der Annahme, dass zwischen jedem Eckpaar keine Selbstschleifen oder mehrere Kanten vorhanden sind. Lassen Sie uns verwenden E Für die Anzahl der Kanten.

Wenn Sie die festgelegten Kanten im übergeordneten Diagramm hasht, können Sie die Kanten des Untergraphen durchlaufen und prüfen, ob sich jeder in der Hash -Tabelle befindet (und in der richtigen Menge, falls gewünscht). Sie tun dies also einmal für jede Kante, daher, O(E).

Nennen wir die Grafik G (mit N Scheitelpunkte) und das mögliche Untergraphen G_1 (mit M Eckpunkte), und Sie möchten finden G_1 is in G.

Da die Etiketten nicht einzigartig sind, können Sie mit dynamischer Programmierung die Unterprobleme stattdessen als solche erstellen - anstatt zu haben, anstatt zu haben O(2^N) Unterprobleme, eine für jeden Untergraphen, Sie haben O(M 2^N) Unterprobleme - eine für jeden Scheitelpunkt in G_1 (mit M Eckpunkte) mit jedem der möglichen Untergraphen.

G_1 is in G = isSubgraph( 0, empty bitmask)

und die Staaten sind als solche eingerichtet:

isSubgraph( index, bitmask ) =
   for all vertex in G
       if G[vertex] is not used (check bitmask)
          and G[vertex]'s label is equal to G_1[index]'s label
          and isSubgraph( index + 1, (add vertex to bitmask) )
               return true
   return false

Da der Basisfall ist index = M, und Sie können angesichts der Bitmaske (und eines impliziten Label-Mapping) nach der Gleichstellung der Kanten überprüfen. Alternativ können Sie auch die Überprüfung innerhalb der IF -Anweisung durchführen. Überprüfen Sie einfach das angegebene aktuelle index, der aktuelle Untergraphen G_1[0..index] ist gleich G[bitmask] (mit der gleichen impliziten Etikettenzuordnung) vor der Wiederholung.

Zum N = 20, Dies sollte schnell genug sein.

(Fügen Sie Ihr Memo hinzu, oder Sie können dies mit Bottoms Up DP umschreiben).

Answer 2

Ok, ich muss die offensichtliche Frage stellen. 1. Sie haben zwanzig Eckpunkte. Gehen Sie zuerst jede Grafik in der Tiefe, alphabetische Ordnung zwischen Geschwistern, um Saiten zu bekommen. 2. Ein Diagramm ist ein Untergraphen eines anderen IFF Eine Zeichenfolge in einer anderen.

Was versteckt sich also in der Problemspezifikation noch, um dies unmöglich zu machen?

Answer 3

Sie können dies als Ausrichtungsproblem betrachten.Grundsätzlich möchten Sie eine injektive Zuordnung erstellen A das jeden Scheitelpunkt in V_1 einem Scheitelpunkt in V_2 zuordnet.Eine Ausrichtungskarte A kann wie folgt gewertet werden:

s(a) = \sum_{(v,w) \in E_1} \sigma(v, w, a(v), a(w)),

wobei \sigma(v, w, a(v), a(w)) = 1, wenn (a(v), a(w)) \in E_2, sonst ist es 0.

Ich denke, dass dies in Form eines ganzzahligen linearen Programms formuliert werden kann.