Énumérer tous les graphiques non isomorphes d'une certaine taille

30

Je voudrais énumérer tous les graphiques non dirigés de taille , mais je n'ai besoin que d'une instance de chaque classe d'isomorphisme . En d'autres termes, je veux énumérer tous les graphes non isomorphes (non dirigés) sur sommets. Comment puis-je faire ceci?nn

Plus précisément, je veux un algorithme qui va générer une séquence de graphes non orientés , avec la propriété suivante: pour chaque graphe non orienté sur sommets, il existe un indice tel que est isomorphe à . J'aimerais que l'algorithme soit aussi efficace que possible; en d'autres termes, la métrique qui m'intéresse est le temps d'exécution pour générer et parcourir cette liste de graphiques. Un objectif secondaire est que ce serait bien si l'algorithme n'est pas trop complexe à implémenter. G n i G G iG1,G2,,GkgnjegGje

Notez que j'ai besoin d'avoir au moins un graphique de chaque classe d'isomorphisme, mais c'est OK si l'algorithme produit plus d'une instance. En particulier, c'est OK si la séquence de sortie comprend deux graphiques isomorphes, si cela aide à trouver plus facilement un tel algorithme ou permet des algorithmes plus efficaces, tant qu'il couvre tous les graphiques possibles.

Mon application est la suivante: j'ai un programme que je souhaite tester sur tous les graphes de taille . Je sais que si deux graphiques sont isomorphes, mon programme se comportera de la même façon sur les deux (il sera soit correct sur les deux, soit incorrect sur les deux), il suffit donc d'énumérer au moins un représentant de chaque classe d'isomorphisme, puis de tester le programme sur ces entrées. Dans mon application, est assez petit.nnn

Quelques algorithmes candidats que j'ai envisagés:

  • Je pourrais énumérer toutes les matrices d'adjacence possibles, c'est-à-dire toutes les matrices symétriques 0 ou 1 qui ont tous les 0 sur les diagonales. Cependant, cela nécessite l'énumération de matrices . Beaucoup de ces matrices représenteront des graphes isomorphes, donc cela semble gaspiller beaucoup d'efforts.2 n ( n - 1 ) / 2n×n2n(n-1)/2

  • Je pourrais énumérer toutes les matrices d'adjacence possibles, et pour chacune, tester si elle est isomorphe à l'un des graphiques que j'ai précédemment produits; s'il n'est pas isomorphe à quoi que ce soit de sortie avant, sortez-le. Cela raccourcirait considérablement la liste de sortie, mais cela nécessite toujours au moins étapes de calcul (même si nous supposons que la vérification de l'isomorphisme du graphique est super rapide), donc ce n'est pas beaucoup mieux en ma métrique.2n(n-1)/2

  • Il est possible d'énumérer un sous-ensemble de matrices d'adjacence. En particulier, si est un graphe sur sommets , sans perte de généralité je peux supposer que les sommets sont disposés de telle sorte que . En d'autres termes, chaque graphique est isomorphe à un où les sommets sont disposés par ordre de degré non décroissant. Il suffit donc d'énumérer uniquement les matrices d'adjacence qui ont cette propriété. Je ne sais pas exactement combien il y a de telles matrices d'adjacence, mais elles sont beaucoup moins de , et elles peuvent être énumérées avec beaucoup moins degnV={v1,,vn}degv1degv2degvn2n(n1)/22n(n1)/2étapes de calcul. Cependant, cela laisse encore beaucoup de redondance: de nombreuses classes d'isomorphisme seront encore couvertes plusieurs fois, donc je doute que ce soit optimal.

Pouvons-nous faire mieux? Si je comprends bien, il y a environclasses d'équivalence des graphes non isomorphes. Pouvons-nous trouver un algorithme dont le temps d'exécution est meilleur que les algorithmes ci-dessus? Jusqu'où pouvons-nous nous rapprocher duborne inférieure? Je m'intéresse principalement à la tractabilité pour les petits (disons, ou environ; assez petit pour que l'on puisse vraisemblablement exécuter un tel algorithme jusqu'à son terme), pas tellement à propos des asymptotiques pour les grands .2n(n-1)/2/n!2n(n-1)/2/n!nn=5n=8n

Connexe: Construire des matrices binaires inéquivalentes (bien que malheureusement on ne semble pas avoir reçu de réponse valide).

DW
la source
1
Afaik, même le nombre de graphiques de taille jusqu'à l'isomorphisme est inconnu, donc je pense qu'il est peu probable qu'il existe un algorithme (sans force brute). En ce qui concerne vos algorithmes candidats, gardez à l'esprit que nous ne connaissons pas d'algorithme en temps polynomial pour vérifier l'isomorphisme du graphe (afaik), donc tout algorithme censé s'exécuter dans O ( | sortie | ) devrait éviter d'avoir à vérifier l'isomorphisme ( souvent / bêtement). (Aussi, | sortie | = Ω ( n | classes | ) .)nO(|sortie|)|sortie|=Ω(n|Des classes|)
Raphael
@Raphael, (1) Je sais que nous ne connaissons pas le nombre exact de graphiques de taille jusqu'à l'isomorphisme, mais ce problème ne nécessite pas nécessairement de le savoir (par exemple, parce que je suis d'accord avec les répétitions). Je ne sais pas pourquoi cela impliquerait qu'il est peu probable qu'il existe un meilleur algorithme que celui que j'ai donné. (2) Oui, je sais qu'il n'y a pas d'algorithme à temps polynomial connu pour l'isomorphisme des graphes, mais nous parlerons ici de valeurs de n comme n = 6 , donc les algorithmes existants seront probablement rapides - et de toute façon, je n'ai mentionné que cet algorithme candidat pour le rejeter, il est donc théorique de toute façon. nnn=6
DW
Pour au plus 6, je crois qu'après avoir choisi le nombre de sommets et le nombre d'arêtes, et ordonné les labels de sommet de façon non décroissante par degré comme vous le suggérez, alors il y aura très peu de classes d'isomorphisme possibles. À ce stade, il pourrait devenir possible de trier les cas restants par un contrôle d'isomorphisme par force brute en utilisant par exemple NAUTY ou BLISS. n
Simon

Réponses:

19

La façon la plus simple d'énumérer tous les graphiques non isomorphes pour les petits nombres de sommets est probablement de les télécharger à partir de la collection de Brendan McKay . L'algorithme d'énumération est décrit dans l'article de McKay [1] et fonctionne en étendant les non-isomorphes de taille n-1 de toutes les manières possibles et en vérifiant si le nouveau sommet était canonique. Il est implémenté comme gengdans le vérificateur d'isomorphisme de graph de McKay nauty.

[1]: BD McKay, Applications d'une technique de dénombrement étiqueté , Congressus Numerantium, 40 (1983) 207-221.

David Eisenstat
la source
J'ai un problème. Je prends un graphe de taille n-1et je le prolonge d'un sommet de toutes les manières possibles, comme vous l'avez dit. Ensuite, je vérifie si le sommet a une étiquette canonique, disons 1(sommet canonique?!). Cependant, que se passe-t-il si le graphique est uniquement isomorphe à la forme canonique et que le sommet a une étiquette différente? J'ai essayé de vérifier les automorphismes pour voir si le sommet avec l'étiquette 1est dans la même orbite, mais je me retrouve ensuite avec le graphique deux fois dans ma liste. Le papier ne m'aide pas vraiment. De plus, le code source de geng est illisible en raison de toutes ces optimisations binaires et à peine de commentaires.
Alex
1
@Alex Vous voulez certainement la version de la vérification qui détermine si le nouveau sommet est dans la même orbite que 1. Pourriez-vous donner un exemple où cela produit deux graphiques isomorphes? Ce serait peut-être mieux comme nouvelle question.
David Eisenstat
D'accord, merci beaucoup! Je suppose que dans ce cas, "s'étendant de toutes les manières possibles" doit en quelque sorte considérer les automorphismes du graphique avec des n-1sommets? par exemple n = 3 et mon graphique précédent était P2. Ensuite, les deux cas où je joindrai le troisième sommet à l'un des sommets précédents aboutiront bien sûr au même graphe P3. Pourriez-vous expliquer rapidement comment "étendre de toutes les manières possibles" ou devrais-je poser cette question comme une autre question? (De plus, je suis parfois confus quant à ce qui se passe, car mon programme doit trouver des non-isomorphismes d'un type spécial de graphique, ce qui rend les choses un peu plus compliquées)
Alex
@Alex Oui, il semble que l'extension elle-même doit être canonique. Vaut probablement une nouvelle question, car je ne me souviens pas comment cela fonctionne du haut de ma tête.
David Eisenstat
1
Page d' accueil Nauty
Guy Coder
4

Je propose une amélioration de votre troisième idée: remplir la matrice d'adjacence ligne par ligne, en gardant une trace des sommets qui sont équivalents en ce qui concerne leur degré et leur adjacence aux sommets précédemment remplis. Ainsi, initialement, les classes d'équivalence seront composées de tous les nœuds de même degré.
Lorsqu'un sommet nouvellement rempli est adjacent à seulement certains des nœuds équivalents, tout choix conduit à des représentants des mêmes classes d'isomrphisme. Nous considérons donc uniquement l'affectation, où le sommet actuellement rempli est adjacent aux sommets équivalents avec le nombre le plus élevé (et divisons la classe d'équivalence en deux pour le processus restant).

n<6
(1,2)(3,4)n=6

Une implémentation naïve de cet algorithme aboutira à des impasses, où il se trouvera que la matrice d'adjacence ne peut pas être remplie en fonction de l'ensemble de degrés donné et des affectations précédentes. Cela peut valoir la peine de détecter / filtrer ces derniers tôt. Quelques idées:

  • Si la somme des degrés est impaire, ils ne formeront jamais de graphique
  • Remplissez les entrées pour les sommets qui doivent être connectés à tous / aucun des sommets restants immédiatement.
FrankW
la source
3

Ces documents pourraient être intéressants.

"Sur la représentation succincte des graphiques", Gyorgy Turan, Discrete Applied Mathematics, Volume 8, numéro 3, juillet 1984, pp. 289-294 http://www.sciencedirect.com/science/article/pii/0166218X84901264

"Représentation succincte des graphiques généraux non étiquetés", Moni Naor, Discrete Applied Mathematics, Volume 28, numéro 3, septembre 1990, pp. 303-307 http://www.sciencedirect.com/science/article/pii/0166218X9090011Z

Ils présentent des fonctions de codage et de décodage pour coder un graphe étiqueté par un sommet de sorte que deux de ces graphes correspondent au même mot de code si et seulement si l'un résulte de la permutation des étiquettes de vertex de l'autre.

De plus, il est prouvé que les fonctions d'encodage et de décodage sont efficaces.

Le premier article traite des graphes planaires. Dans le deuxième article, la restriction de planarité est supprimée.

EDIT: Ce document pourrait également être pertinent:

Graph Isomorphism in Quasi-Polynomial Time, Laszlo Babai, University of Chicago, Preprint on arXiv, 9 décembre 2015 http://arxiv.org/pdf/1512.03547v1.pdf

L'annonce par Babai de son résultat a fait l'actualité: https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem

Mais je me trompe peut-être pour confondre la question des PO avec ces trois documents? L'OP souhaite énumérer les graphes non isomorphes, mais il peut être utile d'avoir des méthodes efficaces pour déterminer quand deux graphes SONT isomorphes?

Simon
la source
J'apprécie cette pensée, mais je crains de ne pas demander comment déterminer si deux graphiques sont isomorphes. Je me demande vraiment comment énumérer les graphes non isomorphes. Décrire des algorithmes pour tester si deux graphiques sont isomorphes ne m'aide pas vraiment, je le crains - merci d'avoir essayé, cependant!
DW
Turan et Naor (dans les articles que je mentionne ci-dessus) construisent des fonctions du type que vous décrivez, c'est-à-dire qui mappent un graphe en un représentant canonique de la classe d'équivalence à laquelle ce graphe appartient. Si vous pouviez énumérer ces représentants canoniques, il semblerait que cela résoudrait votre problème.
Simon
Babai a rétracté la revendication de l'exécution quasi-polynomiale . Apparemment, il y avait une erreur dans l'analyse.
Raphael
1

Un article du début des années 90 traite exactement de cette question:

Algorithmes efficaces pour répertorier les graphiques non étiquetés par Leslie Goldberg.

L'approche garantit que exactement un représentant de chaque classe d'isomorphisme est énuméré et qu'il n'y a qu'un retard polynomial entre la génération de deux graphiques suivants.

n

Pascal Welke
la source