Discussion:Problème de l'isomorphisme de sous-graphes

Dernier commentaire : il y a 5 ans par Fschwarzentruber dans le sujet ne doit pas être confondu
Autres discussions [liste]
  • Admissibilité
  • Neutralité
  • Droit d'auteur
  • Article de qualité
  • Bon article
  • Lumière sur
  • À faire
  • Archives
  • Commons

Il est NP-complet car c'est par exemple une généralisation du problème de la clique

modifier

Le fait qu'il généralise un problème NP-complet montre qu'il est complet, mais pas qu'il est NP. N'étant pas spécialiste du sujet, il y a peut-être quelque chose qui m'échappe. --Pierre de Lyon (discuter) 28 septembre 2016 à 16:03 (CEST)̈ ː Ca montre qu'il est NP-dur. Pour montrer l'appartenance à NP, il faut donner un algorithme non-déterministe en temps polynomial qui le décide. Je peux clarifier l'article. --Fschwarzentruber (discuter) 28 septembre 2016 à 16:10 (CEST)Répondre

ne doit pas être confondu

modifier

Certes isomorphisme de graphes et isomorphisme de sous-graphes ne sont pas la même chose, mais si G et H ont le même nombre de sommets, alors on retombe assez simplement dans le cas de l'isomorphisme de graphes. --Pierre de Lyon (discuter) 28 septembre 2016 à 16:18 (CEST)Répondre

Du coup, isomorphisme de sous-graphes est plus général que isomorphisme de graphes. Il y a un plongement (réduction "triviale") de isomorphisme de graphes dans isomorphisme de sous-graphes. Peut-être que c'est intéressant de le mentionner, plutôt que de dire juste "ne doit pas être confondu", non ?--Fschwarzentruber (discuter) 28 septembre 2016 à 17:50 (CEST)Répondre

Je ne suis pas tout-à-faire d'accord avec la formulation. Il faut, me semble-t-il, parler de la démonstration préalable de l'égalité du nombre de sommets qui se fait en temps linéaire. --Pierre de Lyon (discuter) 29 septembre 2016 à 08:40 (CEST)Répondre
Je ne comprends pas pourquoi donner en entrée à un algorithme décidant l'isomorphisme de sous-graphe un couple (G,H) nous dit si les deux graphes sont isomorphes. Même avec la restriction sur le nombre de noeuds, j'ai l'impression que cela ne marche pas. La définition actuelle considère que le graphe à 3 sommets et aucune arête est un sous-graphe du triangle. Je pense qu'il faut donner en entrée à un algorithme décidant l'isomorphisme de sous-graphe (G,H) puis (H,G) et que la réponse à la question de l'isomorphisme de graphe est la conjonction des deux réponses. --GuiGeek (discuter) 15 mars 2019 à 19:03 (CET)Répondre
Le graphe à 3 sommets non connectés (pas d'arêtes) N'EST PAS un sous-graphe du triangle. La définition demande qu'il y a une arête dans H SI, ET SEULEMENT SI il y a une arête dans G avec le nommage des sommets donnée par f (cf. section "Définition"). --Fschwarzentruber (discuter) 15 mars 2019 à 19:28 (CET)Répondre
Soit   (le triangle) et   (le graphe à 3 sommets non connectés), alors on prend   et   et   l'identité. J'ai l'impression que cela vérifie la définition (qui dit   et non  ). --GuiGeek (discuter) 15 mars 2019 à 22:43 (CET)Répondre
Merci pour la discussion et l'intérêt que vous portez à l'article. Vous avez raison... mais, sauf erreur de ma part, c'est la définition de wikipedia qui est fausse ! Voici un article de Ullman : https://www.cs.bgu.ac.il/~dinitz/Course/SS-12/Ullman_Algorithm.pdf La définition est donnée p. 32, juste avant la section 2. --Fschwarzentruber (discuter) 16 mars 2019 à 22:37 (CET)Répondre
Revenir à la page « Problème de l'isomorphisme de sous-graphes ».