Isomorphisme de graphe et groupe d'automorphisme

Une approche courante pour décider si deux graphes donnés sont isomorphes consiste à calculer l'étiquette dite canonique (alternativement, graphe canonique) de chaque graphe et à vérifier s'ils correspondent ou non.

Des outils tels que Nauty calculent le graphe canonique via des arbres de recherche qui sont élagués à l'aide de quelques idées intelligentes qui reposent, entre autres, sur des automorphismes de graphe. Pour cette raison, Nauty permet de calculer un générateur du groupe d'automorphisme de graphe. Cependant, pour autant que j'ai compris l'idée derrière Nauty, le calcul du graphe canonique ne nécessite pas de calculer un générateur du groupe d'automorphisme du graphe en général.

Ma question est donc la suivante: existe-t-il une relation formelle de complexité théorique entre GI et le calcul d'un groupe électrogène du groupe d'automorphismes de graphes?

Merci beaucoup.

Comme le suggèrent les commentaires, il peut y avoir confusion sur ce que vous appelez "IG". Mais l'idée ici est correcte. Il est équivalent en temps polynomial de trouver des générateurs d'un groupe d'automorphisme comme c'est de trouver un isomorphisme entre deux groupes. L'idée est "classique" dans la mesure où elle apparaît dans les premiers travaux tels que l'isomorphisme du groupe de Luks en valence bornée est en temps polynomial, et même là, je pense que l'idée était considérée comme "bien connue".

Prétendre. Laisser$G$ et $H$être des graphiques connectés . alors$G\cong H$ si et seulement si chaque groupe électrogène $S$ de $\mathrm{Aut}(G\sqcup H)$ contient un élément $g\in S$ tel que $G^g=H$.

Remarque L' important ici est que chaque groupe électrogène échange les graphiques, sinon vous calculez parfois des générateurs qui ne résolvent pas le problème. Ainsi, par exemple, l'isomorphisme de deux groupes ne produit pas si facilement de cette manière. En effet, tous les groupes électrogènes de$\mathrm{Aut}(G\times H)$ échangera $G$ et $H$ quand $G\cong H$. ils peuvent plutôt passer à des copies diagonales. Cette situation peut être corrigée, mais elle nécessite un argument plus solide. Donc, l'approche ici n'est pas celle qui s'applique à toutes les catégories.

Preuve. Pour l'inverse si chaque (ou même si un) groupe électrogène de$\mathrm{Aut}(G\sqcup H)$ échanges $G$ et $H$ puis $G\cong H$ par la restriction de cette fonction à $G$. Il s'agit donc uniquement de la direction avant. (Mais je mentionne cela parce que la preuve est par contraposition, donc il peut sembler que je suis sur le point d'aller dans la même direction.)

Supposer $\mathrm{Aut}(G\sqcup H)$ est généré par un ensemble $S$ dont tous les éléments envoient $G$ à $G$, et $H$ à $H$, (note par hypothèse de connectivité si un sommet de $G$ est envoyé à un sommet de $H$ puis le graphique entier $G$ est envoyé à $H$ et donc par trou de pigeon un sommet $H$ sera envoyé à $G$ et donc $|G|=|H|$et nous aurons échangé les deux graphiques). Depuis$S$ envoie $G$ à $G$, puis chaque composition de fonctions $S$ envoie $G$ à $G$, tout comme les inverses de ces fonctions. Donc, chaque mot$S$ envoie $G$ à $G$ (et aussi $H$ à $H$). Donc, aucun élément de$\mathrm{Aut}(G\sqcup H)$ échanges $G$ et $H$.

Enfin si $G\cong H$ puis un isomorphisme $\phi:G\to H$ offre un automorphisme $\phi\sqcup \phi^{-1}$ de $G\sqcup H$. L'absence d'éléments dans$\mathrm{Aut}(G\sqcup H)$ échanger $G$ et $H$ implique $G\not\cong H$. Le résultat suit. $\Box$

Mais maintenant, le point à préciser est que le passage de la décision ( ?) À la recherche (Donnez-moi ou un certificat que ) doit encore être argumenté ( et peut être). D'un isomorphisme aux générateurs d'automorphismes est également un autre argument (individualiser les graphiques et répéter le test d'isomorphisme). Donc, tout compte fait, vous avez quelques pages d'argument pour faire ces équivalences. Aucun ne montrera cependant un étiquetage canonique. C'est beaucoup plus difficile (NP-hard si je me souviens bien). Même si NAutY et Traces traitent rapidement de nombreux exemples.$G\cong H$$\phi:G\to H$$G\not\cong H$