Discussion:Problème de l'isomorphisme de graphes

Dernier commentaire : il y a 7 ans par Fschwarzentruber dans le sujet Application à la chimie
Autres discussions [liste]
  • Admissibilité
  • Neutralité
  • Droit d'auteur
  • Article de qualité
  • Bon article
  • Lumière sur
  • À faire
  • Archives
  • Commons

Application à la chimie modifier

Je ne connais pas l'application à la chimie du problème de l'isomorphisme de graphes. Mais j'ai l'impression, vu la référence ajoutée, dont le titre contient "subgraph", qu'il s'agit du problème de l'isomorphisme de sous-graphes. J'ai ajouté un article sur le problème de l'isomorphisme de sous-graphes. Bonne journée à vous. --Fschwarzentruber (discuter) 28 septembre 2016 à 10:58 (CEST)Répondre

C'est moi qui a ajouté la référence après un googling où je n'avais trouvé que cela. Il me semble que, au niveau des applications, il faut éviter la tétrapilectomie et que montrer que l'isomorphisme de [sous]-graphes s'applique me parait amplement suffisant. Certes ces problèmes n'ont pas même complexité, mais cela intéresse plus les informatciens théoriciens que les chimistes. En revanche, dans l'introduction la mise en garde se justifie amplement. --Pierre de Lyon (discuter) 28 septembre 2016 à 15:52 (CEST)Répondre


L'article que j'ai mis en référence traite de "Maximum common subgraph isomorphism algorithms" autrement dit du problème de l'isomorphisme de sous-graphes communs maximums, qui me parait encore un autre problème. Pas vrai? --Pierre de Lyon (discuter) 28 septembre 2016 à 16:09 (CEST)Répondre
Oui ː) Ca semble correspondre au problème de décision suivant.

- entrée ː deux graphes G et H, un entier k. - sortie ː oui, s'il existe G' sous-graphe de G, H' sous-graphe de H tel que G' a plus de k sommets et G' isomorphe à H'. Peut-être mettre une section "Variantes" ? --Fschwarzentruber (discuter) 28 septembre 2016 à 17:47 (CEST)Répondre

Revenir à la page « Problème de l'isomorphisme de graphes ».