Je voudrais savoir s'il existe un résultat déjà publié à ce sujet:
Nous prenons tous les chemins différents possibles entre chaque paire de nœuds de deux graphiques réguliers connectés (avec le degré disons et le nombre de nœuds ) et notons leurs longueurs. Bien sûr, ce nombre de chemins distincts est exponentiel. Ma question est, si nous trions les longueurs et les comparons (les listes obtenues par les deux graphiques) et qu'elles sont exactement les mêmes, pouvons-nous dire que les deux graphiques sont isomorphes?n
Bien sûr, même si c'est un résultat, nous ne pouvons pas l'utiliser pour répondre à l'isomorphisme graphique, car le nombre de chemins distincts est exponentiel, comme dit
Par chemins distincts , je me réfère à des chemins ayant au moins un nœud différent, évidemment.
Merci à priori pour votre aide.
Réponses:
Je crois que la réponse à votre question est "non" car une condition équivalente impliquerait une solution temporelle polynomiale à l'IG.
Pour , la matrice d'adjacence du graphe G , notez que le nombre de chemins de i à j de longueur k est ( A k ) i , j (avec répétition des sommets et arêtes autorisée). Pour deux graphes G 1 et G 2 (avec les matrices d'adjacence A 1 et A 2 ) et k ≥ 1 , si vous avez trié les éléments de A k 1 et A k 2 alors pourA G i j k (Ak)i,j G1 G2 A1 A2 k≥1 Ak1 Ak2 pour être isomorphe à G 2 , il est nécessaire que les listes soient identiques pour tout k .G1 G2 k
Je pense que votre conjecture équivaut à:
Si les listes triées d'éléments de et A d 2 sont identiques pour k = 1 à n - 1 (limite supérieure sur le chemin le plus long avec des sommets non répétitifs) alors G 1 et G 2 sont isomorphes.Ak1 Ad2 k=1 n−1 G1 G2
Donc, pour résoudre GI, il suffit d'effectuer multiplications de n × n matrices (et un peu de temps supplémentaire pour trier et comparer n 2 éléments). Cela prendrait moins de n 4 fois.n−1 n×n n2 n4
J'admets deux failles possibles dans mon argument. Premièrement, il est tout à fait possible que GI ait un algorithme de temps polynomial et que nous venons de le découvrir ensemble, tout à l'heure (hourra, nous sommes célèbres!). Je trouve cela très improbable. Deuxièmement (et beaucoup plus probable), ce que j'ai proposé n'est pas réellement équivalent à votre conjecture.
Pensée finale. Avez-vous essayé cela pour tous, disons, des graphiques 3-réguliers pour la taille 8 ou plus? Je penserais que si votre conjecture est fausse, il devrait y avoir un contre-exemple dans les graphes 3 réguliers de taille assez petite.
la source
Puisque vous ne comparez que les longueurs des chemins (et en attendant en oubliant à quelle paire de nœuds ils correspondent si je vous ai bien compris), je pense que des graphiques très similaires devraient fournir un contre-exemple: au final vous ne faites que compter le nombre de chemins d'une longueur fixe et indépendamment des sommets qu'ils relient. Par exemple, je pense que ces graphiques sont un contre-exemple: http://www.mathe2.uni-bayreuth.de/markus/REGGRAPHS/GIF/06_3_3-2.gif et http://www.mathe2.uni-bayreuth.de/ markus / REGGRAPHS / GIF / 06_3_3-1.gif
Si je ne me trompe pas (compter les chemins est fastidieux), ils ont tous les deux 9 chemins de longueur 1, 18 chemins de longueur 2, 48 chemins de longueur 3, 30 chemins de longueur 4 et 36 chemins de longueur 5
la source
la source