Isomorphisme Des Graphes

c'est un sacré problème.

En général, l'idée de base est de simplifier le graphe en une forme canonique, puis d'effectuer la comparaison des formes canoniques. Les arbres transversaux sont générés avec cet objectif, mais les arbres transversaux ne sont pas uniques, vous devez donc avoir une façon canonique de les créer.

après que vous avez des formes canoniques, vous pouvez effectuer la comparaison isomorphisme (relativement) facile, mais ce n'est que le début, puisque les graphiques non-isomorphiques peuvent avoir la même STP. (par exemple, pensez à un arbre couvrant T et un seul ajout d'un bord à elle pour créer T'. Ces deux graphiques ne sont pas isomorphe, mais ils ont le même arbre couvrant).

D'autres techniques consistent à comparer des descripteurs (par exemple le nombre de noeuds, le nombre d'arêtes), qui peuvent produire des faux positifs en général.

je vous suggère de commencer avec la page wiki sur le isomorphisme du graphique problème. J'ai aussi un livre à suggérer: "La Théorie Des Graphes et de ses applications". C'est un tome, mais ça vaut chaque page.

a partir de votre corollaire, chaque distribution spatiale possible des vertex d'un graphe donné est un isomorphe. Donc deux graphes isomorphes ont la même topologie et ils sont, en fin de compte, le même graphe, du point de vue topologique. Une autre question Est, par exemple, de trouver ces structures isomorphe bénéficiant de propriétés particulières (par exemple avec des bords non de passage, s'il existe), et cela dépend des propriétés que vous vouloir.

un des meilleurs algorithmes pour trouver des isomorphismes de graphe est VF2.

j'ai écrit un aperçu général de la FV2 appliquée à la chimie - où il est largement utilisé. Le poste de touche sur les différences entre VF2 et Ullmann. Il y a aussi un à partir de zéro de la mise en œuvre de VF2 écrit en Java qui pourrait être utile.

un problème très similaire - automorphisme graphique - peut être résolu par coquine, qui est disponible en code source. Ceci trouve toutes les symétries d'un graphe. Si vous avez deux graphes, rejoignez-les en un et n'importe quel isomorphisme peut être découvert comme un automorphisme de la jointure.

Disclaimer: je suis l'un des co-auteurs de coquine.

il y a des algorithmes pour faire cela -- cependant, je n'ai pas encore eu de raison de les étudier sérieusement. Je crois que Donald Knuth est soit en train d'écrire ou a écrit sur ce sujet dans sa série Art of Computing au cours de sa deuxième passe à (re)les écrire.

pour ce qui est d'un moyen simple de faire quelque chose qui pourrait fonctionner dans la pratique sur de petits graphes, je recommanderais de compter les degrés, puis pour chaque vertex, noter aussi l'ensemble des degrés pour les Vertex qui sont adjacents. Ce sera puis vous donner un ensemble d'isomorphismes potentiels du sommet pour chaque point. Ensuite, il suffit d'essayer tous ceux (via la force brute, mais en choisissant les vertex dans l'ordre croissant des ensembles d'isomorphisme potentiel du sommet) à partir de cet ensemble restreint. Intuitivement, la plupart de l'isomorphisme de graphe peut être pratiquement calculé de cette façon, bien qu'il y aurait clairement des cas dégénérés qui pourraient prendre beaucoup de temps.

je suis récemment tombé sur le document suivant : http://arxiv.org/abs/0711.2010 Cet article propose "un algorithme de temps Polynomial pour L'isomorphisme de graphe"

Mon projet - Griso - à sf.net: http://sourceforge.net/projects/griso/ avec cette description:

Griso est un utilitaire de test d'isomorphisme de graphique écrit en C++. Il est basé sur ma propre POLYNOMIAL-TIME (dans ce point le sel du projet) algorithme. Voir l'exemple d'entrée/sortie de Griso sur http://funkybee.narod.ru/graphs.htm page.

• nauty et des Traces

nauty et Traces sont des programmes de calcul de groupes d'automorphisme de graphiques et digraphes [*]. Ils peuvent également produire une étiquette canonique. Ils sont écrits dans un sous-ensemble portable de C, et fonctionnent sur un nombre considérable de systèmes différents.

• AutGroupGraph commande RAISIN du paquet de GAP.
• bonheur: un autre programme de symétrie et d'étiquetage canonique.
• conauto: un paquet d'ismorphisme graphique.

pour ce qui est de l'heuristique: j'ai fantasmé sur un algorithme D'Ullmann modifié, où vous n'utilisez pas seulement la première recherche de largeur, mais mélangez-le avec la première recherche de profondeur, vous utilisez d'abord la première recherche de largeur de manière intensive, que vous fixez une limite pour l'analyse de largeur et aller plus profond après avoir vérifié quelques voisins, et vous abaissez le breadh chaque étape à un certain montant. C'est pratiquement comme ça que je trouve mon chemin sur une carte: d'abord me localiser avec de la largeur d'abord chercher, puis rechercher la route avec première recherche de profondeur-en grande partie, et c'est la meilleure évolution de mon cerveau n'a jamais inventé. :) Sur le long terme une certaine intelligence peut être ajoutée pour augmenter la largeur de la première recherche compte de voisins aux sommets critiques - par exemple là où il y a un grand nombre de sommets voisins avec le même nombre de bord. Comme vérifier votre itinéraire réel parfois avec la voiture (sans gps).

j'ai découvert que l'algorithme appartient à la catégorie des algorithmes K-dimension Weisfeiler-Lehman, et il échoue avec les graphes réguliers. Pour plus d'ici:

http://dabacon.org/pontiff/?p=4148

message Original suit:

j'ai travaillé sur le problème pour trouver des graphiques isomorphiques dans une base de données de graphiques (contenant des compositions chimiques).

en bref, l'algorithme crée un hachage d'un graphique en utilisant l'itération de puissance méthode. Il pourrait y avoir des fausses collisions positives de hachage, mais la probabilité de cela est extrêmement faible (je n'ai pas eu de telles collisions avec des dizaines de milliers de graphiques).

La façon dont fonctionne l'algorithme est ceci:

N (où N est le rayon de la courbe) itérations. À chaque itération et pour chaque nœud:

• trier les hachages (de l'étape précédente) des voisins du noeud
• hachez le concaténé trié hachages
• remplacer le hash du noeud par le hash nouvellement calculé

sur la première étape, le hachage d'un noeud est affecté par ses voisins directs. Sur la deuxième étape, le hachage d'un noeud est affecté par le voisinage 2-sauts loin de lui. Sur la nième étape, le hachage d'un noeud sera affecté par le N-houblon du voisinage autour de lui. Il vous suffit donc de continuer à exécuter Powerhash avec N = graph_radius steps. En fin de compte, le hachage du noeud du centre du graphique aura été affecté par tout le graphe.

pour produire le hachage final, trier les hachures de noeud de l'étape finale et les concaténer ensemble. Après cela, vous pouvez comparer les hachages de trouver si deux graphes sont isomorphe. Si vous avez des étiquettes, ajoutez-les (à la première étape) dans les hachures internes que vous calculez pour chaque noeud.

Il n'y a plus de fond ici:

https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF

vous pouvez trouver le le code source ici:

https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py