Discussion :

[vosges88]

Bonjour,

je vous signale un bug dans la procédure IsIsomorphic dans Maple 2015

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
A:={{1,2},{1,3},{1,4}};B:={{1,2},{2,3},{3,4}};
IsIsomorphic(Graph(A),Graph(B));
true

alors que A n'est pas isomorphe à B.

Il y a hélas d'autres contre-exemples comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
A := {{1, 3}, {1, 4}, {2, 3}, {2, 4}}
B := {{1, 3}, {1, 4}, {2, 3}, {3, 4}}
IsIsomorphic(Graph(A),Graph(B));
true

[vosges88]

Maple2015 répond parfois que deux graphes non isomorphes le sont. Voici deux exemples :

{{1, 4}, {2, 4}, {3, 4}}
{{1, 4}, {2, 3}, {3, 4}}
`Graph 1: an undirected unweighted graph with 4 vertices and 2 edge(s)`
`Graph 2: an undirected unweighted graph with 4 vertices and 2 edge(s)`
"========================"
{{1, 4}, {2, 3}, {2, 4}, {3, 4}}
{{1, 3}, {1, 4}, {2, 3}, {2, 4}}
`Graph 3: an undirected unweighted graph with 4 vertices and 2 edge(s)`
`Graph 4: an undirected unweighted graph with 4 vertices and 2 edge(s)`

En plus, il se trompe sur le nombre d'arêtes. Il dit <<with 2 edges>> alors qu'il y en a 3 ou même 4.

[vosges88]

Et bien, il semble que dans Maple 2016.1 ce n'est pas mieux. Même pire !!!

Il y a 5 paires de graphes à 4 sommets qui sont déclarées Isomorphes alors que ce n'est vraiment mais vraiment pas le cas !!!

Bravo MapleSoft !!

[vosges88]

En fait que ce soit Maple 2015 ou Maple 2016, il y a le même BUG. Le pire c'est que Maple donne une liste des graphes non isomorphes
et qu'il en reconnait des paires isomorphes alors qu'elles ne le sont pas du tout !

Essayez avec votre version :

with(GraphTheory):
l:=[NonIsomorphicGraphs(4,output=graphs,outputform=graph)]:
for i to nops(l) do for j from i+1 to nops(l) do
if IsIsomorphic(l[i],l[j]) then print(i,j);fi;
od;od;

Résultat :

5, 7
6, 8
9, 10
9, 11
10, 11

[vosges88]

Il y a donc aussi 3 graphes à 4 sommets qui sont identifiés alors qu'ils ne le sont pas : les 9,10 et 11 èmes graphes de la liste donnée par Maple.

Bravo, Maplesoft.

Si l'un de vous peux leur communiquer ce BUG ce serait très bien.....

[vosges88]

Bonjour,

il y a une solution pour que IsIsomorphic donne la bonne réponse :

faire : IsIsomorphic(Graph(A),Graph(B),'phi');

qui met dans phi une bijection solution entre les deux graphes (si elle existe).

J'ai écrit à Maple et ils promettent de faire les corrections.

[bendesarts]

Bonjour,

A titre d'information, c'est étrange qu'il puisse avoir des erreurs dans ces fonctions de théorie de Graphes.
En effet, Maple utilise bcp la théorie des graphes pour la mise en équation de systèmes physiques dans son module MapleSim.

A+

[vosges88]

En effet bandesarts.

Mais je suppose que la fonction IsIsomorphic n'est pas utilisée dans le système de Maple autrement que pour les théoriciens des graphes ou éventuellement pour tester si deux
relations binaires sont équivalentes. Cela peut aussi être utilisé par les biologistes ou les chimistes pour identifier deux molécules ou deux protéines.

En tout cas, j'ai écrit à Maple et ils promettent de corriger l'erreur dans une révision de Maple 2016. par contre ils ne feront rien pour les versions précédentes ce qui me semble
assez scandaleux ! Ils arrivent à la même politique employée par Microsoft ou Apple : pour corriger nos bugs...achetez les nouvelles versions.

Ce serait bien que nous manifestions notre désaccord avec cette politique commerciale.

Ce serait aussi bien de signaler que les "lanceurs d'alerte" sur leurs bugs pourraient être plus considérés en bénéficiant par exemple de leurs nouvelles versions.

[vosges88]

Bonjour,

si vous trouvez d'autres exemples de graphes pour lesquels Maple donne une mauvaise réponse sur leur isomorphisme, je vous remercie de les signaler dans cette discussion.

a+

[vosges88]

Merci à celui qui a donné 5 étoiles à cette discussion.

Mais le plus important c'est d'améliorer nos outils de travail comme Maple.

C'est pourquoi il est nécessaire de signaler les bugs et de les faire remonter aux concepteurs.

Il faut aussi que des boîtes comme Maplesoft fassent un effort de leurs côtés pour améliorer leurs produits mais aussi pour respecter les "lanceurs d'alertes" qui
leur donnent des infos ou même des tuyaux techniques. Pour ma part, j'ai fait ce travail pour Maplesoft et je suis très déçu des retours que j'ai eus de leur part !

a+