Graphisomorphismus mit Äquivalenzbeziehung auf der Scheitelpunktmenge

9

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)Gc:V(G)N(G,c)(H,d)π:V(G)V(H)c(v)=d(π(v))vV(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 PaareG ( G , 1 ) ( H , 2 ) π : V ( G ) V ( H ) v 1 , v 2V ( G )(G,)G(G,1)(H,2)π:V(G)V(H)v1,v2V(G) gilt

v11v2 iff π(v1)2π(v2)

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

John D.
quelle
3
Bitte verwenden Sie die Notation " " nur für die Gleichheitsrelation! =
David Richerby

Antworten:

9

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,G)nmcGGv1,,vc=Gn+c+1w0,,wn+cwiw0w1w2wn+cviw0G , 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 )viGn+2c+n+1O(n)m+n+c+(n+c+1)m+4n+1O(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 '(G1,1)(G2,2)G1G2vi,1viG1vi,2 und ähnlich fürwi,1undwi,2. Wenn es einen IsomorphismusG ' 1G ' 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,1G2wi,1wi,2G1G2wi,1wi,2iwn+cn+c+1w0,1Karten 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, cw0,2w0w1vi{v1,1,,vc,1}{v1,2,,vc,2}12cvon Ä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 )vi,1vi,2ivG1G2(G1,1)(G2,2)dann ergibt dies einen Isomorphismus .G1G2

Joshua Grochow
quelle
Soweit ich weiß, gibt es ein grundlegendes Problem bei Ihrer Reduzierung. Grundsätzlich erzwingen Sie eine eindeutige invariante Eigenschaft für die Scheitelpunkte jeder Äquivalenzklasse. In diesem Fall haben Sie die Exzentrizität eines Scheitelpunkts als invariante Eigenschaft ausgewählt. Für einen Graphen sei f eine Färbung. Nehmen wir an, = f ist die durch f induzierte Äquivalenzbeziehung , dh u = f v, wenn f ( u ) = f ( v ) . Gf=ffu=fvf(u)=f(v)
John D.
Erwägen Sie nun, den EQ-GI auf den farbigen GI zu reduzieren. Durch Ihr Argument für eine Eingabe sollte es ausreichen, G , H zu übergeben und Färbungen c 1 , c 2 zu wählen , die = 1 , = 2 induzieren . Das Problem hierbei ist, dass ( G , c ) ( H , d ) impliziert ( G , = c )(G,=1),(H,=2)G,Hc1,c2=1,=2(G,c)(H,d) aber die andere Richtung ist nicht unbedingt wahr, da wir die Entsprechung zwischen den beiden Mengen von Äquivalenzklassen a priori nicht kennen. (G,=c)(H,=d)
John D.
Anders ausgedrückt, ich sehe nicht ein, wie es für eine bloße Graphentransformation möglich wäre, den EQ-GI aufgrund der komplexeren Einschränkungen überhaupt auf einen farbigen GI zu reduzieren. Es ist jedoch klar, dass Ihre Konstruktion dazu beitragen würde, den farbigen GI auf GI zu reduzieren.
John D.
@ user17410 EQ-GI ist GI gefärbt. "Nennen Sie das Problem, das Sie EQ-GI beschreiben." Es ist sicherlich möglich, dass eine Graphtransformation EQ-GI zu GI reduziert: Tatsächlich kann dies für jedes Isomorphismusproblem bei relationalen Strukturen zu GI durchgeführt werden. Joshuas Reduktion sieht für mich richtig aus; Ich hatte mir einen etwas einfacheren ausgedacht, der eher mehr Eckpunkte hinzufügt.
David Richerby
1
Ihr Korrektheitsargument hat mich überzeugt. Ich bin zu schnell zu Schlussfolgerungen gesprungen, bevor ich mir die Zeit genommen habe, Ihre Reduktion zu analysieren. Ich entschuldige mich.
John D.
3

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 ' 'G1=(V1,E1)G2=(V2,E2)q|V1|+1=|V2|+1K|V1|+1 ) und verwendeq+1Farbenc1,. . . ,cq,cq+1.K|V2|+1q+1c1,...,cq,cq+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ärbtKKqc1,...,cqcq+1G1cq+1KG2q+1und 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 :-)

enter image description here
Die Reduzierung entspricht dem Beispiel in Ihrem Kommentar

Marzio De Biasi
quelle
Das sieht vielversprechend aus. Ich werde die Richtigkeit später überprüfen.
John D.
@ user17410: ok, lassen Sie mich wissen, wenn Sie weitere Erläuterungen benötigen
Marzio De Biasi