Discussion:Graphe hamiltonien

Mémo : citation à trouver (Calude, 41)

POur pas oublier : j'ai cité [1] pour le poids potentiel de la machine permettant de résoudre le problème sur des graphes de 200 sommets, mais il faudrait remonter aussi à la source, Christian Calude 41, pas encore trouvé la publi parmis sa biblio sur son site.

Est-ce que ce n'est d'ailleurs pas une conséquence immédiate du nombre d'échantillons d'ADN dont on doit disposer ? --MathsPoetry (d) 26 janvier 2013 à 14:44 (CET)

Ah si complètement. Un chemin correspond à une séquence ADN, on veut générer les chemins possibles donc on a besoin d'une quantité de nucléotides qui permette de générer ces séquences. Sachant que c'est un processus statistique il me semble, on compte sur l’assemblage aléatoire de séquence de bases pour générer toutes les combinaisons, il faut en prévoir assez pour qu’on soit raisonnablement sûr qu'on ait effectivement généré toutes les séquences. — TomT0m ^[bla] 26 janvier 2013 à 16:31 (CET)

On peut alors le faire apparaître dans la rédaction de l'article, tel quel on a l'impression que c'est indépendant. --MathsPoetry (d) 26 janvier 2013 à 18:19 (CET)

Pourquoi ce n'est pas satisfaisant

Il sonne un peu bizarrement ce paragraphe dans sont état actuel. On sait que le problème est NP-complet, ça rend assez improbable la résolution par un critère mathématique efficace non ? Ou alors ce théorème s'énonce simplement mais savoir si il s’applique ou pas au graphe est aussi un problème NP-complet, ça rend les approches autres qu’algorithmiques assez improbables, sauf à gagner un peu d'argent gratuit au passage ... Je le trouve pas très neutre dans sa manière de présenter les choses — TomT0m ^[bla] 7 février 2013 à 13:27 (CET)

Euh, mais pas du tout. Un problème NP-complet, c'est une notion de calculabilité. Rien n'empêche qu'un critère mathématique prenant le problème par un tout autre bout vienne résoudre le problème de façon simple. Exemple : le problème des quatre couleurs est à présent mathématiquement résolu (on a démontré que toute carte peut être coloriée avec 4 couleurs), bien que le coloriage lui-même d'une carte donnée soit un problème NP-complet.

En admettant qu'un génie trouve un critère pour dire si un graphe est hamiltonien ou non, la détermination effective des chemins en question pourra rester affreusement lente. Ou par exemple, prenons un graphe pour lequel le théorème de Bondy et Chvatal nous dise qu'il est hamiltonien : on n'a pas pour autant les chemins, il reste à allumer l'ordinateur pour les calculer. --MathsPoetry (d) 7 février 2013 à 14:11 (CET)

J'ai du faire une erreur alors, ce n’est pas le problème de décision lui même (est-ce qu’il existe un chemin) qui est NP-Complet, c'est le problème de détermination d'un chemin effectif ? cf. la def sur en: « In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete.[1] » (PS confilt édit- tu t'y reprend à chaque fois à 12 fois pour publier ??? il y a un bouton "prévisualiser" )— TomT0m ^[bla] 7 février 2013 à 14:28 (CET)

Le problème de décision est NP-complet. Ce paragraphe est un peu bizarre. En gros, les critères présentés avant sont des conditions suffisantes mais non nécessaires, il n'y a pas grand chose à ajouter je pense. Zandr4^[Kupopo ?] 7 février 2013 à 14:36 (CET)

J'ai toujours eu du mal avec ces histoires de calculabilité et de décision, malgré que dans le civil je suis informaticien et non mathématicien, et je ne peux pas te répondre. Que le problème de décision soit lui aussi NP-complet ne signifie pas pour autant que c'est indémontrable, je crois. Sinon, dès qu'on sait qu'un problème est NP-complet, on pourrait abandonner la recherche d'une démonstration... Vérifie quand même ce point auprès de spécialistes de la calculabilité, j'ai peur de dire des bêtises.

Le fait que l'on a du mal à trouver les chemins par algorithme, ou le fait que les mathématiciens coincent depuis plus d'un siècle sur ce problème, sont effectivement des signes que sa résolution est improbable à court terme, mais pas qu'elle est impossible, surtout si on se laisse quelques siècles pour chercher intensément. Regarde la problème de la carte des 4 couleurs, on y est bien arrivé, alors qu'on finissait par perdre espoir.

Je suis quelqu'un de très hésitant, peut-être parce que je cherche à être très rigoureux, et qui raisonne par approximations successives, malgré le bouton "prévisualiser" j'arrive à changer dix fois d'avis sur ce que j'écris. Désolé. --MathsPoetry (d) 7 février 2013 à 14:37 (CET)

À Zandr4, si ce paragraphe est bizarre, n'hésite pas le corriger. Je suis à l'aise avec l'aspect mathématique du truc, pas avec son aspect informatique. En tout cas, ce n'est pas parce qu'on n'a trouvé pour le moment que des conditions nécessaires qu'on ne peut pas trouver une condition nécessaire et suffisante dans le futur. Ou j'ai tort ? --MathsPoetry (d) 7 février 2013 à 14:45 (CET)

En fait ça signifie que si un critère existe dans le cas général, il ne peut pas être utilisé pour construire un algorithme efficace. En gros il est aussi difficile - dans le sens de aussi NP-complet - de déterminer si un graphe quelconque remplit ou non ce critère que de trouver un chemin. Du coup qualifier un tel critère de "simple" si est difficile de vérifier si il est rempli me semble hasardeux. Sauf à trouver un sens différent à "simple" et à "purement mathématique" mais ça n’a pas l'air simple ou objectif vu comme ça. Sinon c'est pas très grave de s'y reprendre à plusieurs fois . — TomT0m ^[bla] 7 février 2013 à 14:51 (CET)

Je peux me tromper, mais je ne crois pas que "le problème de décision est NP-complet" signifie "la vérification d'un critère est NP-complète" et encore moins "on ne peut pas trouver de critère mathématique". De mémoire, un problème NP-complet, c'est juste un problème équivalent à d'autres problèmes NP-complets en terme de temps de calcul, mais ça ne préjuge pas de l'inexistence de solution mathématique. Sinon les mathématiciens pourraient arrêter de bosser.

Si ce paragraphe est mal rédigé, n'hésitez pas à le changer. J'essayais de faire une transition "douce" entre la partie "Détermination d'un graphe hamiltonien" et la partie "Problème du chemin hamiltonien" qui expliquait pourquoi, faute de bonne solution mathématique actuelle, la voie informatique pouvait être explorée. --MathsPoetry (d) 7 février 2013 à 15:01 (CET)

«  je ne crois pas que "le problème de décision est NP-complet" signifie "la vérification d'un critère est NP-complète" »

Justement, si ! Si on avait un critère vérifiable facilement, alors le problème de décision serait facile aussi. Bien sûr, il peut exister des critères mathématiques, comme le plus simple : "un graphe est hamiltonien si et seulement si il est hamiltonien". Mais, sauf si P=NP, il ne peut pas exister de critère mathématique efficace. Zandr4^[Kupopo ?] 7 février 2013 à 15:07 (CET)

Au passage, on a aussi "un graphe est hamiltonien si et seulement si sa fermeture est hamiltonienne", qui est nécessaire et suffisant, mais ne fournit pas non plus de critère pour déterminer si un graphe donné est hamiltonien ou non (je fournis même un contre-exemple en illustration).

Comme dit, j'ai toujours eu du mal avec la théorie de la calculabilité et ce n'est pas en train de s'arranger . J'ai un peu de difficulté à m'imaginer comment on saurait d'avance qu'un critère est inefficace alors qu'on ne l'a même pas encore trouvé. Mais bon, je suis prêt à vous croire sur parole.

Ce que - je crois - tu n’as pas compris, c'est qu'une solution mathématique comme tu dis ouvrirait la voie à une solution informatique efficace. Si tester ce critère est efficace, on a une solution algorithmique efficace pour résoudre le problème ... Bref je ne crois pas que ta distinction entre solution informatique et mathématique sont très rigoureuse, les informaticiens s'appuient tout le temps sur des théorèmes pour écrire les algorithmes. En recherche opérationnelles par exemple ils ont tendance à n’écrire que les théorèmes, l’algorithme en découlant. — TomT0m ^[bla] 7 février 2013 à 15:11 (CET)

La distinction entre informatique et mathématiques est effectivement arbitraire, elle ne me servait que de support à mon discours.

Comment a-t-on déterminé que le problème de décision était NP-complet ? Certainement pas en partant d'un critère mathématique qui n'existe pas encore - plutôt en disant, si on utilise telle ou telle méthode (au hasard : en examinant tous les cas), on se ramène à un autre problème NP-complet. N'est-ce pas à dire « examiner le problème de décision avec tel critère est NP-complet », plutôt que « examiner le problème de décision avec n'importe quel critère, passé, présent ou à venir, est NP-complet » ? Désolé d'avance si je raisonne comme un noob.

Pour revenir à l'article, verriez-vous des améliorations ? --MathsPoetry (d) 7 février 2013 à 15:24 (CET)

Un problème NP c'est un problème pour lequel il existe une machine de Turing non déterministe polynomiale pour le résoudre. Donc un algorithme exponentiel si P != NP.

La définition de NP-complet implique que tous les algorithmes qui résolvent le problème sont exponentiels dans le pire des cas - toujours si P=NP. Si on dit qu'à chaque critère mathématique correspond une machine de Turing (plusieurs, mettons la plus efficace qui calcule si ce critère est rempli) ça veut donc dire que son temps d'exécution est exponentiel en fonction de la taille du graphe, sinon on a trouvé un algorithme efficace pour résoudre le problème, donc on a prouvé que P=NP .

Maintenant pour l’article j’ai pas encore tout lu, mais ce paragraphe doit être reformulé en tout cas, sans doute pour dire qu'on connait des cas particuliers pour lesquels il existe des critères efficaces pour déterminer si un graphe est hamiltoniens, et qu'on cherche toujours d'autres cas particuliers et les critères associés. Mais faudrait sourcer. — TomT0m ^[bla] 7 février 2013 à 15:49 (CET)

Ajout : il manque un lien vers correspondance de Curry-Howard pour approfondir (et justifier) le lien entre maths et algorithme. — TomT0m ^[bla] 7 février 2013 à 15:55 (CET)

Comme d'habitude avec la calculabilité, rien pigé avec ton explication (soupir). Je suis vraiment indécrottable...

Sur le principe, ce qui me gène, c'est que tu dises "on n'arrivera jamais à trouver un critère mathématique efficace", sans passer par une démonstration mathématique, ce qui me semble exceptionnellement fort et pour le moins douteux. En prenant votre langage, je soupçonne que cela suppose que P != NP, ce qui n'est pas encore démontré.

Pour les maths,

• oui, on connait des cas particuliers pour lesquels on sait que c'est hamiltonien
• on en cherche activement d'autres
• on connait aussi des cas particuliers pour lesquels on sait que ce n'est pas hamiltonien
• non, on ne connaît pas de critère général efficace
• on connaît un critère général inefficace, en temps d'ordre $O(n!)$ dans le pire des cas, consistant à essayer tous les chemins pour voir s'il y a un cycle
• inefficacité qu'on arrive à pas mal améliorer à l'aide de meilleurs algorithmes jusqu'à des temps de calcul de l'ordre $O(1,657^{n})$.

Tout ça est déjà écrit correctement. Tout ce qui est écrit est juste. On ne passe qu'à la NP-complétude qu'après les premières considérations, donc ce n'est pas illogique de ne pas utiliser la np-complétude pour influencer l'état des lieux mathématique.

Tu peux préciser ce que tu voudrais changer et comment ? --MathsPoetry (d) 7 février 2013 à 16:16 (CET)

Pour moi la distinction math et algorithmique dans l’histoire est un point de vue. Le problème de caractérisation du graphe et le problème de décision sont deux manières différentes de dire la même chose, et la NP-complétude du problème est un résultat fondamental sur la caractérisation. Et effectivement trouver un critère efficace reviendrait à démontrer que P=NP. Pour le comment faire je ne sais pas exactement, mais j’aurai tendance à parler complexité en premier pour mettre une borne sup qu’on connait sur la difficulté du problème d'entrée de jeu, de manière pédagogique bien sur. (PS, désolé pour mon explication, j’aurai surement pas du parler de machine de Turing et juste d'algorithme probablement) — TomT0m ^[bla] 7 février 2013 à 16:31 (CET)

Je viens de changer "outil purement mathématique" en "outil mathématique efficace". Après tout, examiner tous les cas est aussi une démarche mathématique, même si elle prend beaucoup de temps... Cela devrait un peu atténuer cette distinction entre "maths" et "calcul" qui est, comme tu le fais remarquer à juste titre, arbitraire.

Parler de complétude d'entrée de jeu ne va pas, pour plusieurs raisons :

• on sort d'un long examen de tous les théorèmes sur des cas particuliers que l'on connaît, il convient d'abord de faire un résumé de ce qu'ils nous apportent et de ce qu'ils nous apportent pas
• la NP-complétude n'est pas franchement pédagogique (moi, elle me fait même planer grave), c'est même plutôt un argument bulldozer
• le fait que ce soit NP-complet est effectivement un fort indicateur qu'on perd son temps à chercher, mais ça ne prouve pas que c'est impossible (sauf si on sait que P != NP, ce qu'on ne sait pas, même si tout le laisse à penser)

Enfin, on peut remarquer que l'ensemble du plan de l'article sépare clairement la partie "théorèmes" de la partie "algorithmes", même si c'est arbitraire. On retrouve cette même dichotomie dans l'article anglais, qui utilise même des pages séparées... --MathsPoetry (d) 7 février 2013 à 16:42 (CET)

Je n’aime pas trop cette démarche, elle fait une frontière arbitraire entre les maths et l'informatique. Alors que même en utilisant les théorèmes cité au dessus on peut utiliser des algorithmes pour les tester, d'ailleurs le faire à la main est fastidieux, et d'autre part il y a une marge avec "tester tous les chemins" qui est la solution triviale et la pire des solutions. Le plan actuel fait "on a des théorème gentil" puis passe à "on doit tester tous les chemins" mais "on peut quand même faire mieux". C'est du à la distinction arbitraire justement. Distinction qui est à mon humble avis plus un héritage culturel de séparation entre les discipline que quelque chose de fondamentalement lié aux graphes hamiltoniens. bref, c'est POV, sauf à faire apparaître explicitement le fait que ce sont des communautés différentes qui voient le même problème de manière un peu différente. Sous cet angle le "pourquoi c'est pas satisfaisant" te fait placer directement du point de vue des matheux fondamentalistes (la je m’adonne clairement au POV) qui voient l’utilisation de machines pour résoudre un problème comme quelque chose de fondamentalement sale. Alors que la complexité du problème est une donnée très intéressante (et qu'on peut établir sur papier) sur la caractérisation d'un programme Hamiltonnien. Et ça n’empêche pas de dire qu'on peut rechercher de meilleurs critères et de meilleurs algorithmes - c'est la même chose ! — TomT0m ^[bla] 7 février 2013 à 17:10 (CET)

De fait, historiquement, ce sont des gens différents qui ont exploré les deux voies. OK, les maths c'est de l'informatique et réciproquement, mais on a quand même d'un côté des mathématiciens qui ont travaillé sur des théorèmes et les ont publié dans des revues savantes de mathématiques, et de l'autre des informaticiens qui ont affiné des algorithmes et les ont testés. Les mathématiciens en question n'avaient d'ailleurs pas à leur disposition l'outil informatique pendant longtemps. C'est justement POV de nier cette réalité historique.

D'autre part, pédagogiquement, il n'est pas absurde de montrer comment les mathématiciens coincent, et ce que peuvent leur apporter les informaticiens.

Dans la première partie on ne raisonne même pas en général sur les graphes. On prend le point de vue très particulier du degré des sommets, et on raisonne dessus. Si ça se trouve, c'est pas la meilleure approche.

Présenter les deux voies de recherche historiques séparément ne me semble pas absurde du point de vue du plan, surtout que ça conduit dans un cas à des raisonnements, dans l'autre à des algorithmes, deux techniques de travail très différentes, même si on arrive à démontrer qu'elles sont au fond équivalentes. --MathsPoetry (d) 7 février 2013 à 17:24 (CET)

On peut faire apparaître les deux voies de recherche sans faire une séparation aussi nette. D'ailleurs ça se ressent dans la section " complexité", ou je vois « Néanmoins, si l'on assemble toutes ces conditions, le problème de savoir si les graphes planaires cubiques bipartis 3-connexes contiennent toujours un cycle hamiltonien reste ouvert » qui mériterait de figurer dans la première partie de l’article si on suis ton raisonnement non ? — TomT0m ^[bla] 7 février 2013 à 17:37 (CET)

D'une part la conjecture de Barnette est bien évoqué dans la première partie, d'autre part tu oublies la fin de la phrase disant justement que c'est un problème qui ne peut être NP-complet (et on reste donc bien dans les histoires de complexité).

C'est justement pour faire un lien que j'ai fait cette fameuse section « bizarre » sur les différentes voies explorées. Si tu vas chez les anglophones, il n'y a rien, on a l'impression que ce sont des gens qui s'ignorent totalement, tu as même un article par théorème. J'ai essayé de mettre du liant dans tout ça.

Je ne veux pas séparer, c'est juste assez naturel, à la fois pour moi (le rédacteur) et, je le pense, aussi pour le lecteur. Si l'on peut faire des ponts dans chaque partie, pourquoi pas, mais attention, si l'on veut tout dire dès le début sans suivre une progression logique, on arrive sûrement à cette espèce de bouillie non ordonnée de faits qui est malheureusement le cas de nombre d'articles de Wikipédia. Ici, au moins, on a un ordre logique, un concept à la fois, ça peut se lire comme un roman.

Ce n'est pas la seule transition que j'ai ajoutée dans l'article. Dans "Algorithmes", j'ai aussi mentionné qu'une autre approche était l'ordinateur à ADN. Et pouf, on embraie ensuite sur l'ordinateur à ADN. --MathsPoetry (d) 7 février 2013 à 17:47 (CET)

« tant qu'il reste des sommets u et v tels que deg(u)+deg(v)≥n, on ajoute l'arête {u,v} au graphe. Quand on ne peut plus en ajouter, on a obtenu ce qu'on appelle la fermeture du graphe. On applique alors le théorème suivant : » j’avais pas encore lu ça, mais ça ressemble furieusement à un algorithme ;).

Je vais tenter de proposer une modif d'organisation qui me conviendrait mieux :

1. Chapeau
2. Définition et problèmes associé:
   • Def
   • Caractérisation ou de manière équivalente le problème de décider si un graphe est ou pas hamiltonien
   • Problème de recherche d'un chemin dans un graphe
3. Les origines Historique
   • les premiers temps (comme maintenant)
   • renouveau de l'intérêt (?) du problème dans les années 60, preuve par Karp que c'est un probblème difficile - c'est un problème NP-complet connu et souvent cité, voisin du problème du voyageur de commerce et introduction des approches algorithmiques suite au développement de l’informatique. A l'occasion indiquer que la preuve de NP-complétude est cohérente avec le fait qu'une caractérisation n'ait été trouvée que pour des cas particuliers. Dire qu’une caractérisation efficace est équivalente à prouver P=NP.
   • Ordis à ADN
4. Premier problème, caractérisation et résultats:
   1. Caractérisations "mathématiques" de sous classes de graphes (testables rapidement pas une machine) mais ne permettant de caractériser que des sous classes de graphe euleriens
   2. Approches algorithmiques : complètes mais exponentielles
   3. Approches exotiques : ADN
5. Deuxième problème associé / fortement lié aux approches algorithmiques recherchant effectivement un chemin.

On garde une progression (je suis d'accord avec l'idée d'avoir un article rédigé), mais on "remonte" des choses dans l'introduction de choses (amhà) importante dans l’article comme la recherche de chemin. Et ça fait un peu disparaitre le truc un peu dérangant pour moi de présenter les approches algorithmiques comme des échecs. Un avis ? — TomT0m ^[bla] 7 février 2013 à 18:47 (CET)

Les approches par raisonnement sont tout autant des échecs que les approches algorithmiques.

Plein de trucs me gênent à fond dans ton plan. Le problème de base est que tu confonds l'article sur le graphe hamiltonien (théorie des graphes) et l'article sur le problème du chemin hamiltonien (algorithmique). Tu vois tout sous l'angle du second. C'est là très POV, là où je cherchais à ménager la chèvre et le chou. À noter que les anglophones ont deux articles séparés et donc évitent le conflit, mais c'est dommage, justement parce que l'on perd le lien entre les deux approches. Je m'attendais à ce que tôt où tard on me propose de scinder ce gros article, mais je voyais ça en trois, "Graphe hamiltonien", "Problème du chemin hamiltonien" et "Caractérisation d'un graphe hamiltonien", pas que l'histoire du problème phagocyte tout le reste.

En revanche, introduire la preuve de Karp est une excellente idée, qui va avec mes ajouts de preuves dans la partie mathématique.

D'ailleurs, Dirac c'est 1952, Karp c'est 1972.

Pour le principe même de monter dans l'introduction, OK, c'est légitime. Mais pas en voyant tout sous l'angle du problème du chemin. Laisse-moi faire un essai. --MathsPoetry (d) 7 février 2013 à 19:04 (CET)

La preuve (enfin la publi des preuves) c'est 72, je dirai comme ça que la preuve doit dater d'avant, après l'algo de prog dynamique de Karp c'est 10 ans plus tot.

Sur le plan : tout ça est intimement lié, ça a presque du sens d'avoir un article principal qui évoque et lie le tout et des articles détaillés pour compléter les parties - la définition est assez simple, les exemples sont là, la caractérisation est liée avec le problème de décision, et la résolution du problème de décision implique en pratique la recherche d'un chemin, et les applications sont à ma connaissances principalement algorithmiques ... expliquer tout ça - peut être en laissant certains détails dans les articles détaillés - dans l’article sur le graphe lui même ne me semble pas déconnant puisque TOUT ÇA concerne le graphe lui même, son étude et son histoire ! On ne perd rien des caractérisations du graphe et du point de vue de la pure théorie des graphes, on élargit juste un peu le point de vue et on explique les liens entre les approches.

Il ne s'agit évidemment pas de virer les exemple ou le reste qui sont important bien entendu. — TomT0m ^[bla] 7 février 2013 à 19:21 (CET)

"Les applications sont à ma connaissances principalement algorithmiques" là c'est toi qui est biaisé par l'informatique. D'abord pourquoi des applications ? le savoir pur est aussi important.

Concernant l'article, pas de révolution, une amélioration, si tu le veux bien .

J'ai monté des choses de la section "bizarre" vers l'introduction générale. La section bizarre devrait l'être moins, puisqu'elle se concentre à présent sur les déficiences de l'approche "théorie des graphes".

L'introduction mentionne la NP-complétude d'entrée de jeu ; à mon avis, c'est fort dommage, car celui qui ne sait pas ce que c'est va être désarçonné par le nouveau terme qui est posé là sans être défini, et celui qui le sait savait de toute façon sans doute déjà que le problème du chemin hamiltonien est dans la catégorie, donc c'est non pédagogique. Ce qui est mieux est que l'introduction annonce les deux grosses parties qui vont suivre.

NP complétude est un gros mots, "problème difficile complexe à résoudre de manière efficace avec un ordinateur (NP-complet)" l'est beaucoup moins et convient bien dans une intro ... les initiés savent ce que c'est, les autres comprennent qu’il s’est passé un truc. Si il faut être plus pédagogique "le développement de l’informatique théorique va plus tard trouver un moyen de classer les problèmes en résolvable efficacement par un ordinateur et problèmes difficiles". Ce problème s'avéra classé dans les problèmes difficiles (NP-complets). C'est simplifié mais pédagogique et sans gros mots ... c'est surement possible de faire mieux. — TomT0m ^[bla] 7 février 2013 à 20:03 (CET)

J'ai gardé les critiques et les réserves sur chaque méthode, à mon avis c'est important de bien définir le champ de ce qu'on sait faire et de ce que l'on ne sait pas faire. --MathsPoetry (d) 7 février 2013 à 19:38 (CET)

Ne te gène pas pour changer la formulation et la rendre plus pédagogique. Tant que tu ne transformes pas l'article sur les graphes hamiltoniens sur un article où tout part de, vient à et passe par la théorie de la complexité, ça me va. --MathsPoetry (d) 7 février 2013 à 20:08 (CET)

P. S. : résolvable => soluble

P.P.S. : honnêtement, ça me semble pas mal maintenant que la transition est montée dans l'introduction. Surtout, ça respecte l'équilibre entre théorie des graphes / théorie de la complexité. Le plus urgent est sans doute à présent de compléter la nouvelle section, qui est la démonstration que c'est NP-complet (probablement par réduction au Problème de couverture de sommets, si j'ai bien suivi).

Erreur sur le caractère hamiltonien des polyèdres de catalan ?

"L'hexacontaèdre trapézoïdal est le seul dual d'un solide d'Archimède dont le graphe des arêtes ne soit pas hamiltonien" me pârait faux car je suis sur que le [Dodécaèdre Rhombique] a un graphe non hamiltonien (bicoloration avec les sommets de degré 3 et de degré 6, dont les nombres sont distincts.

Je ne trouve pas cette phrase dans l'article. --Roll-Morton (discuter) 10 mars 2016 à 18:03 (CET)

Changement de nom vers "chemin hamiltonien" ?

Bonjour, la wikipedia en anglais utilise "hamiltoinian path", et je penche plutôt pour cette option aussi : pointer sur la structure plutôt que sur les objets qui ont cette structure. Qu'en pensez-vous ? A noter : graphe eulérien, même combat. --Roll-Morton (discuter) 9 mai 2016 à 16:37 (CEST)

Exemples de graphes hamiltoniens

Un truc que je ne comprends pas : Il est dit que le graphe adjoint d'un graphe hamiltonien est hamiltonien. Si on suit le lien du graphe adjoint, on a un exemple qui dit que le graphe adjoint de K5, qui est complet donc hamiltonien, est le graphe de Petersen. Si on suit le lien du graphe de Petersen, on lit que ce graphe est hypohamiltonien. Donc qui dit faux ? Ou est-ce l'exception qui confirme la règle ?

Supprimer la redirection depuis "Problème du chemin hamiltonien"

Que pensez-vous de conserver cet article de théorie des graphes mais de créer un autre article d'informatique sur "Problème du chemin hamiltonien" ? --Fschwarzentruber (discuter) 22 octobre 2018 à 13:17 (CEST)