Isomorphisme graphique avec relation d'équivalence sur l'ensemble de sommets

9

Un graphique coloré peut être décrit comme un tuple (G,c)G est un graphique et c:V(G)N est la coloration. On dit que deux graphes colorés (G,c) et (H,d) sont isomorphes s'il existe un isomorphisme π:V(G)V(H) tel que la coloration est respectée, c.-à-d. c(v)=d(π(v)) pour toutvV(G) .

Cette notion capture l'isomorphisme des graphes colorés dans un sens très strict. Prenons le cas où vous avez deux cartes politiques de la même région mais qui utilisent des jeux de couleurs différents. Si l'on demande s'ils sont colorés de la même manière, on supposerait que cela signifie s'il existe une correspondance bijective entre les deux jeux de couleurs de sorte que les couleurs des deux cartes coïncident via cette correspondance. Cette notion peut être formalisée par la description des graphiques colorés comme tuple (G,) est une relation d'équivalence sur l'ensemble des sommets du G . On peut alors dire deux de ces graphes (G,1) et (H,2) sont isomorphes s'il existe un isomorphismeπ:V(G)V(H) tel que pour toutes les pairesv1,v2V(G) il est vrai que

v11v2 iff π(v1)2π(v2)

Ma question est de savoir si ce concept a été étudié précédemment par la recherche de formes canoniques, etc. et si oui sous quel nom il est connu?

John D.
la source
3
Veuillez ne pas utiliser la notation " " pour autre chose que la relation d'égalité! =
David Richerby

Réponses:

9

Le problème que vous décrivez a certainement été pris en compte (je me souviens en avoir discuté à l'école, et à l'époque il avait déjà été discuté bien avant), bien que je ne puisse citer aucune référence particulière dans la littérature. Peut-être parce qu'il est linéairement équivalent à l'isomorphisme du graphique non coloré, comme suit (cela est vrai même pour les formes canoniques). Appelez le problème que vous décrivez EQ-GI.

GI est juste le cas particulier de EQ-GI où chaque graphique a une seule classe d'équivalence composée de tous les sommets.

Dans l'autre sens, pour réduire EQ-GI à GI, soit un graphe avec une relation d'équivalence avec n sommets, m arêtes et c classes d'équivalence. Construire un graphe G dont l'ensemble des sommets se compose des sommets de G , ainsi que de nouveaux sommets v 1 , , v c , un pour chaque classe d'équivalence dans = G , ainsi que n + c + 1 nouveaux sommets w 0 , ,(G,G)nmcGGv1,,vc=Gn+c+1 . Reliez les w i dans un chemin w 0 - w 1 - w 2 - - w n + c , connectez chaque v i à w 0 , et pour chaque sommet de G , connectez-le au sommet de classe d'équivalence correspondant v i . Alors G a au plus n + 2 c + n + 1 O ( n )w0,,wn+cwiw0w1w2wn+cviw0Gvjegn+2c+n+1O(n)sommets et peuvent être construits essentiellement dans le même temps. (Il a également au plus arêtes - qui est O ( m ) pour les graphiques connectés - mais c'est un peu moins pertinent car la plupart des algorithmes GI ont des temps d'exécution qui ne dépendent essentiellement que de n .)m+n+c+(n+c+1)m+4n+1O(m+n)O(m)n

Mise à jour : Puisqu'il y avait une certaine confusion dans les commentaires, j'ajoute ici un croquis de l'exactitude de l'argument ci-dessus. Étant donné et ( G 2 , 2 ) , soit G ' 1 et G ' 2 les graphiques construits comme ci-dessus; soit v i , 1 désigne le sommet v i d'en haut dans G 1 , et v i , 2 celui de G (G1,1)(g2,2)g1g2vje,1vjeg1vje,2 , et de même pourwi,1etwi,2. S'il y a un isomorphismeG ' 1G ' 2 , il doit envoyerwi,1àwi,2pour touti, car dans chaque graphiquewn+cest le sommet unique qui est le point final de tout chemin de longueur au moinsn+c+1. En particulier,w0,1g2wje,1wje,2g1g2wje,1wje,2jewn+cn+c+1w0,1correspond à . Comme les voisins de w 0 qui ne sont pas w 1 sont exactement les v i , l'isomorphisme doit mapper l'ensemble { v 1 , 1 , , v c , 1 } à l'ensemble { v 1 , 2 , , v c , 2 } (et en particulier les deux ~ 1 et ~ 2 doivent avoir le même nombre, cw0,2w0w1vi{v1,1,,vc,1}{v1,2,,vc,2}12c, des classes d'équivalence). Notez que l'isomorphisme n'a pas besoin d'envoyer à v i , 2 pour tous les i , mais est autorisé à permuter les indices des v tant que les classes d'équivalence correspondantes peuvent être mappées les unes aux autres. Inversement, sur la base de cette description de l' apparence des isomorphismes entre G 1 et G 2 , il est facile de voir que si ( G 1 , 1 ) ( G 2 , 2 )vi,1vi,2ivG1G2(G1,1)(G2,2)cela donne alors un isomorphisme .G1G2

Joshua Grochow
la source
Autant que je sache, votre réduction pose un problème fondamental. Vous appliquez essentiellement une propriété invariante unique sur l'ensemble des sommets de chaque classe d'équivalence. Dans ce cas, vous avez choisi l'excentricité d'un sommet comme propriété invariante. Pour un graphe soit f une coloration. Disons que = f est la relation d'équivalence induite par f , c'est-à-dire u = f v si f ( u ) = f ( v ) . Gf=ffu=fvf(u)=f(v)
John D.
Maintenant, envisagez de réduire l'EQ-GI en GI coloré. Par votre argument pour une entrée il devrait suffire de passer G , H et de choisir les colorations c 1 , c 2 qui induisent = 1 , = 2 . Le problème ici est que ( G , c ) ( H , d ) implique ( G , = c )(G,=1),(H,=2)G,Hc1,c2=1,=2(G,c)(H,d) mais l'autre sens n'est pas nécessairement vrai car on ne connaît pas a priori la correspondance entre les deux ensembles de classes d'équivalence. (G,=c)(H,=d)
John D.
Autrement dit, je ne vois pas comment il serait possible pour une simple transformation de graphique de réduire l'EQ-GI en GI coloré en raison des contraintes plus complexes. Il est clair cependant que votre construction fonctionnerait pour réduire le GI coloré au GI.
John D.
@ user17410 EQ-GI est de couleur GI. "Appelez le problème que vous décrivez EQ-GI." Il est certainement possible pour une transformation de graphe de réduire l'EQ-GI en GI: en fait, cela peut être fait pour tout problème d'isomorphisme sur les structures relationnelles en GI. La réduction de Joshua me semble correcte; J'avais pensé à un peu plus simple qui ajoute un peu plus de sommets.
David Richerby
1
Votre argument de justesse m'a convaincu. J'ai sauté aux conclusions pour jeûner avant de prendre le temps d'analyser votre réduction, je m'excuse.
John D.
3

J'ai lu votre dernier commentaire dans la bonne réponse de Joshua; si vous devez transformer EQ-GI en GI coloré (c'est-à-dire que vous avez des problèmes avec les couleurs affectées aux classes d'équivalence), vous pouvez utiliser la réduction suivante:

Supposons que les graphes de départ soient , G 2 = ( V 2 , E 2 ) et qu'il existe q classes d'équivalence; alors vous pouvez ajouter à chaque graphique un "permutateur", c'est-à-dire un graphique complet sur | V 1 | + 1 = | V 2 | + 1 nœuds ( K | V 1 | + 1 , K G1=(V1,E1)G2=(V2,E2)q|V1|+1=|V2|+1K|V1|+1 ) etutilisationq+1couleursc1,. . . ,cq,cq+1.K|V2|+1q+1c1,...,cq,cq+1

Dans les deux et K " , q noeuds sont distingués et colorés avec c 1 , . . . , c q les nœuds restants sont colorés avec c q + 1 . Les nœuds de G 1 sont colorés avec la couleur c q + 1 et les nœuds de la même classe d'équivalence sont liés à la couleur correspondante en K ' ; les nœuds de G 2 sont colorés avec la couleur q + 1KKqc1,...,cqcq+1G1cq+1KG2q+1et les nœuds de la même classe d'équivalence sont liés à la couleur correspondante en .K

Notez également que vous pouvez supprimer les couleurs et obtenir une instance GI équivalente :-)

entrez la description de l'image ici
La réduction correspondant à l'exemple de votre commentaire

Marzio De Biasi
la source
Cela semble prometteur. Je vérifierai l'exactitude plus tard.
John D.
@ user17410: ok, faites-moi savoir si vous avez besoin de plus de clarifications
Marzio De Biasi