Graphisomorphismus mit Äquivalenzbeziehung auf der Scheitelpunktmenge

Ein farbiger Graph kann als Tupel wobei ein Graph ist und die Färbung ist. Zwei farbige Graphen und gelten als isomorph, wenn ein Isomorphismus vorliegt, so dass die Färbung eingehalten wird, dh für alle .$(G,c)$$G$$c : V(G) \rightarrow \mathbb{N}$$(G,c)$$(H,d)$$\pi : V(G) \rightarrow V(H)$$c(v) = d(\pi(v))$$v \in V(G)$

Dieser Begriff erfasst den Isomorphismus farbiger Graphen in einem sehr strengen Sinne. Stellen Sie sich den Fall vor, in dem Sie zwei politische Karten derselben Region haben, die jedoch unterschiedliche Farbsätze verwenden. Wenn man fragt, ob sie auf die gleiche Weise gefärbt sind, würde man annehmen, dass dies bedeutet, ob zwischen den beiden Farbsätzen eine bijektive Zuordnung besteht, so dass die Farben beider Karten über diese Zuordnung übereinstimmen. Dieser Begriff kann formalisiert werden, indem farbige Graphen als Tupel wobei eine Äquivalenzbeziehung auf der Scheitelpunktmenge von . Wir können dann sagen, dass zwei solcher Graphen und isomorph sind, wenn es einen Isomorphismus so dass für alle Paare∼ G ( G , ∼ 1 ) ( H , ∼ 2 ) π : V ( G ) → V ( H ) v 1 , v 2 ∈ V ( G $(G,\sim)$$\sim$$G$$(G,\sim_1)$$(H,\sim_2)$$\pi : V(G) \rightarrow V(H)$$v_1,v_2 \in V(G)$ gilt

Meine Frage ist, ob dieses Konzept zuvor untersucht wurde, um kanonische Formen usw. zu finden, und wenn ja, unter welchem ​​Namen es bekannt ist?

Das von Ihnen beschriebene Problem wurde definitiv in Betracht gezogen (ich erinnere mich, dass ich es in der Graduiertenschule besprochen habe, und zu der Zeit war es bereits lange zuvor besprochen worden), obwohl ich auf keine bestimmten Referenzen in der Literatur verweisen kann. Möglicherweise, weil es wie folgt linear dem ungefärbten Graphisomorphismus entspricht (dies gilt auch für kanonische Formen). Nennen Sie das Problem, das Sie EQ-GI beschreiben.

GI ist nur der Spezialfall von EQ-GI, bei dem jeder Graph nur eine Äquivalenzklasse hat, die aus allen Eckpunkten besteht.

In der anderen Richtung, um EQ-GI auf GI zu reduzieren, sei ein Graph mit einer Äquivalenzbeziehung zu Eckpunkten, Kanten und Äquivalenzklassen. Konstruieren Sie einen Graphen dessen Scheitelpunktmenge aus den Scheitelpunkten von zusammen mit den neuen Scheitelpunkten , einem für jede Äquivalenzklasse in sowie neuen Scheitelpunkten . Verbinden Sie die in einem Pfad , verbinden Sie jedes mit und für jeden Scheitelpunkt in$(G, \sim_G)$$n$$m$$c$$G'$$G$$v_1, \dotsc, v_c$$=_G$$n+c+1$$w_0, \dotsc, w_{n+c}$$w_i$$w_0 - w_1 - w_2 - \dotsb - w_{n+c}$$v_i$$w_0$$G$ , verbinde es mit dem entsprechenden Äquivalenzklassenscheitelpunkt . Dann hat höchstens Eckpunkte und kann im wesentlichen in derselben Zeitgrenze konstruiert werden. (Es hat auch höchstens m + n + c + ( n + c + 1 ) ≤ m + 4 n + 1 ≤ O ( m + n ) Kanten - das ist O ( m )$v_i$$G'$$n + 2c + n +1 \leq O(n)$$m + n + c + (n+c+1) \leq m + 4n + 1 \leq O(m+n)$$O(m)$für verbundene Graphen - aber das ist etwas weniger relevant, da die meisten GI-Algorithmen Laufzeiten haben, die im Wesentlichen nur von abhängen .)$n$

Update : Da es in den Kommentaren einige Verwirrung gab, füge ich hier eine Skizze der Richtigkeit des obigen Arguments hinzu. Wenn und ( G 2 , ∼ 2 ) gegeben sind , seien G ' 1 und G ' 2 die wie oben konstruierten Graphen; lassen v i , 1 bezeichnen die Scheitel V i von oben in G ' 1 und v i , 2 das in G $(G_1, \sim_1)$$(G_2, \sim_2)$$G_1'$$G_2'$$v_{i,1}$$v_i$$G_1'$$v_{i,2}$ und ähnlich fürwi,1undwi,2. Wenn es einen IsomorphismusG ' 1 ≅G ' 2 gibt , muss erfür alleiwi,1anwi,2senden, da in jedem Graphenwn+cder eindeutige Scheitelpunkt ist, der der Endpunkt eines beliebigen Längenpfades ist mindestensn+c+1. Insbesonderew0,$G_2'$$w_{i,1}$$w_{i,2}$$G_1' \cong G_2'$$w_{i,1}$$w_{i,2}$$i$$w_{n+c}$$n+c+1$$w_{0,1}$Karten zu . Da die Nachbarn von w 0 , die nicht w 1 sind, genau das v i sind , muss der Isomorphismus die Menge { v 1 , 1 , … , v c , 1 } auf die Menge { v 1 , 2 , … , v c abbilden , 2 } (und insbesondere müssen sowohl ∼ 1 als auch ∼ 2 die gleiche Zahl haben, $w_{0,2}$$w_0$$w_1$$v_i$$\{v_{1,1},\dotsc,v_{c,1}\}$$\{v_{1,2},\dotsc,v_{c,2}\}$$\sim_1$$\sim_2$$c$von Äquivalenzklassen). Es ist zu beachten, dass der Isomorphismus nicht für alle i bis v i , 2 senden muss , sondern die Indizes der v 's permutieren darf, solange die entsprechenden Äquivalenzklassen aufeinander abgebildet werden können. Umgekehrt ist anhand dieser Beschreibung, wie Isomorphismen zwischen G ' 1 und G ' 2 aussehen können, leicht zu erkennen, dass wenn ( G 1 , ∼ 1 ) ≅ ( G 2 , ∼ 2$v_{i,1}$$v_{i,2}$$i$$v$$G_1'$$G_2'$$(G_1, \sim_1) \cong (G_2, \sim_2)$dann ergibt dies einen Isomorphismus .$G_1' \cong G_2'$

Ich habe Ihren letzten Kommentar in der richtigen Antwort des Joshua gelesen. Wenn Sie EQ-GI in farbiges GI umwandeln müssen (dh Sie haben Probleme mit den den Äquivalenzklassen zugewiesenen Farben), können Sie die folgende Reduzierung verwenden:

Angenommen, die Startgraphen sind , G 2 = ( V 2 , E 2 ) und es gibt q Äquivalenzklassen; dann können Sie jedem Diagramm einen "Permutator" hinzufügen, dh ein vollständiges Diagramm auf | V 1 | + 1 = | V 2 | + 1 Knoten ( K ' | V 1 | + 1 , K $G_1 = (V_1, E_1)$$G_2 = (V_2, E_2)$$q$$|V_1|+1=|V_2|+1$$K'_{|V_1|+1}$ ) und verwendeq+1Farbenc1,. . . ,cq,cq+1.$K''_{|V_2|+1}$$q+1$$c_1,...,c_q,c_{q+1}$

Sowohl in als auch in K' ' werden q Knoten unterschieden und mit c 1 , . . . , c q die verbleibenden Knoten sind mit c q + 1 gefärbt . Die Knoten von G 1 sind mit der Farbe c q + 1 gefärbt und Knoten in derselben Äquivalenzklasse sind mit der entsprechenden Farbe in K 'verbunden ; Die Knoten von G 2 sind mit der Farbe q + 1 gefärbt$K'$$K''$$q$$c_1,...,c_q$$c_{q+1}$$G_1$$c_{q+1}$$K'$$G_2$$q+1$und Knoten in derselben Äquivalenzklasse sind mit der entsprechenden Farbe in verknüpft .$K''$

Beachten Sie auch, dass Sie die Farben löschen und eine entsprechende GI-Instanz erhalten können :-)

Die Reduzierung entspricht dem Beispiel in Ihrem Kommentar