Découverte Personnelle :

Bonjour,

Voilà l'algorithme écrit en maple :

p:=nextprime(10000); # va permettre de garder une taille raisonnable pour la signature
U:=[]; # va récupérer la signature
n:=10; #nombre de sommets
A:=array(1..n); # le graphe y sera stocké
B:=array(1..n); # pour stockage temporaire de données.
for i from 1 to n do A[i]:={}; 
   for j from 1 to n/2 do A[i]:=A[i] union {rand(1..n)()}; od: 
   A[i]:=A[i] minus {i}: 
od: # tirage aléatoire d'un graphe 
for ii from 1 to n do 
   r:=1; 
   for i from 1 to n do r:=r*nops(A[i]) mod p; od: 
   U:=[op(U),r]; 
   for i from 1 to n do B[i]:={}; 
      for j in A[i] do B[i]:=(B[i] union A[j]) minus (B[i] intersect A[j]);od: 
      B[i]:=B[i] minus {i}; 
   od:
   for i from 1 to n do A[i]:=B[i]; od:
od: #on récupère dans U la signature, du graphe.

Il me permet de trouver une signature caractéristique dans tous les cas que j'ai testé, c'est à dire que je n'ai pas réussi à trouver 2 graphes non isomorphes de même signature.

Sachant que par ce procédé deux graphes isomorphes ont même signature.

Qu'en pensez-vous ?

Bonne journée.

J'en pense que vous devriez d'abord nous expliquer ce qu'est un problème NP-complet.

Décider si 2 graphes sont isomorphes, est un problème NP, pour lequel on ne sait pas s'il est NP-complet, cette signature tendrait à montrer qu'il n'est pas NP-complet.

Citation wiki :

Le problème qui consiste, étant donné deux graphes à savoir si ils sont isomorphes, est un problème algorithmique classique. Il est notamment connu en théorie de la complexité pour être l'un des seuls problèmes de la classe NP pour lequel on ne connait ni d'algorithme en temps polynomial, ni de preuve qu'il est NP-complet.

J'avais initialement posté dans un forum de math (mathématiques.net), mais impossible d'accédé au forum.

Donc je me suis rabattu sur ce forum, pour connaître l'avis de personne connaissant la question.

Recopier wiki n'est pas nous expliquer ce qu'est un problème NP-complet !

Au cas où tu ne l'aurais pas remarqué, j'ai donné une citation wiki, qui montre que le problème que je traite n'est pas prouvé NP-complet, ni polynomial d'ailleurs, et l'algo que je donne tendrait à montrer que c'est un problème polynomial.

Bref parler de problème NP-complet ici c'est juste hors sujet.

Mon pauvre !

Relisez-vous donc et après expliquez cette contradiction avec votre propre texte :

"Bref parler de problème NP-complet ici c'est juste hors sujet. "

Elle est quand même bien bonne, celle là !

C'est justement TOUT le problème !

Quoi qu'il en soit, vous ignorez tout de la théorie des graphes, de la théorie de la complexité de Kolmogorov comme de la Relativité etc.

Allez, rêvez bien ...

Crois ce que tu veux cela m'est égale, je n'ai rien à te prouver.

Maintenant si quelqu'un de plus compétant que toi sur la question pouvait se prononcer sur l'algorithme proposé cela me serait d'une grande utilité.

Tu ne serais pas Lorrain79 ?

"je n'ai rien à te prouver."

Alors ça, c'est vrai !

Je me demande seulement si vous savez ce qu'est une preuve !!!

De plus, je suis sûr que vous ignorez ce que sont des graphes isomorphes.

Enfin, étant donnés deux graphes générés au hasard, la probabilité pour qu'ils soient isomorphes est pratiquement nulle même s'ils ont un même nombre d'arêtes !

Amusez-vous bien.

Moi, c'est fait !

Et maintenant, vous pourrez, en pure perte, raconter toutes vos inepties.