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

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

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)

ne doit pas être confondu

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)

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)

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)

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)

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)

Soit $G=(\{1,2,3\},\{(1,2),(1,3),(2,3)\})$ (le triangle) et $H=(\{1,2,3\},\emptyset )$ (le graphe à 3 sommets non connectés), alors on prend $V_{0}=\{1,2,3\}$ et $E_{0}=\emptyset$ et $f$ l'identité. J'ai l'impression que cela vérifie la définition (qui dit $E_{0}\subseteq V_{0}\times V_{0}\cap E_{G}$ et non $E_{0}=V_{0}\times V_{0}\cap E_{G}$). --GuiGeek (discuter) 15 mars 2019 à 22:43 (CET)

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)