Effizienter Graphisomorphismus für ähnliche Graphabfragen

Angesichts des Graphen G1, G2 und G3 wollen wir den Isomorphismustest F zwischen G1 und G2 sowie zwischen G1 und G3 durchführen. Wenn G2 und G3 sehr ähnlich sind, so dass G3 durch Löschen eines Knotens und Einfügen eines Knotens aus G2 gebildet wird und wir das Ergebnis von F (G1, G2) haben, können wir F (G1, G3) berechnen, ohne es von Grund auf neu zu berechnen durch die Erweiterung bestehender Methoden auf dem neuesten Stand der Technik?

Wenn beispielsweise G2 durch die Knoten 2,3,4,5 und G3 durch die Knoten 3,4,5,6 gebildet wird, können wir das Ergebnis von F (G1, G2) verwenden, um F (G1, G3) effizienter?

Dies ist eine einfache Polynomzeitverkürzung, um zu zeigen, dass das Problem GI vollständig ist : Selbst wenn Sie wissen, dass $G_1, G_2$ isomorph sind, prüfen Sie, ob $G_3$ , das aus dem Löschen und Hinzufügen eines Knotens durch $G_2$ ist, isomorph zu $G_1$ ist so hart wie der Graphisomorphismus selbst (im schlimmsten Fall).

Bei zwei Graphen $G = (V, E), G'= (V', E')$ bauen

$G_1 = ( V \cup V' \cup \{u\},\; E \cup E' \cup \{ (v_i,u) \mid v_i \in V \})$

dh die Vereinigung der beiden Graphen plus einen zusätzlichen Knoten $u$ mit allen Eckpunkten von $V$

wähle $G_2 = G_1$ ; und eindeutig sind sie isomorph.

Nun bauen $G_3$ Löschen von $u$ und Hinzufügen $u'$ verbunden zu allen Eckpunkten $V'$ :

$G_3 = ( V \cup V' \cup \{u'\},\; E \cup E' \cup \{ (v_i',u') \mid v_i' \in V'\} )$

$G_1, G_3$ sind isomorph, wenn$G, G'$ isomorph sind.