Une question triviardu.
Par Arthur Milchior le mercredi 1 avril 2009, 00:01 - Recherche - Lien permanent
Ce billet fait suite à C'est joli un graphe hamiltonien, non?. Si vous voulez voir l'avancement, la dernière version est ici, appuyez sur le graphe, puis sur la touches page down/Pg.Suiv de votre clavier. Mais ce n'est pas le sujet.
Je ne comprend pas mon professeur, il a un don. Il est capable de mélanger des questions d'une facilité déconcertante et des questions qui peuvent à priori prendre des années de calculs. Voici un exemple qui n'amusera que les matheux.
Soit G un graphe avec 64 noeuds[1], combien y a t-il de circuit hamiltonien, et ont-ils tous le même nombre d'arête?
Si vous avez éclaté de rire, bravo, j'attends au moins la moitié de la réponse en commentaire (si vous avez les deux moitié, merci de m'expliquer comment faire).
Si la question vous laisse de marbre, voici une petite explication de texte. Si on connait le nombre de circuit, on sait si il y en a au moins un. Or en général sur un graphe, savoir si il existe au moins un circuit hamiltonien est NP-complet[2]. Donc en général, connaitre le nombre de circuit Hamiltonien appartient à #P. Mais par définition un circuit hamiltonien passe une fois et une seule par chaque nœud et boucle. Il y a donc autant d'arête que de nœuds, soit 64.
Donc, combien il y en a: j'en sais rien, je peux pas tous vous les donner, ni les compter dans un temps humain (IE, pas des millions d'année), mais je peux vous assurer qu'ils ont tous le même nombre d'arête.
PS: je vous rassure, ceci n'a rien à voir avec mon spectacle. N'ayez pas peur.
Notes
[1] pour la description exacte, voir le billet précédant, C'est joli un graphe hamiltonien, non?
[2] IE très très dur à trouver
Commentaires
J'ai compris pour le nombre d'arêtes: les circuits hamiltoniens d'un graphe à 64 noeuds ont tous le même nombre d'arêtes (64).
Concernant le nombre de circuit hamiltonien, le professeur s'attend certainement à une fourchette. On sait déjà que certains graphes n'en ont pas, donc la fourchette basse est zéro. La fourchette haute n'est-elle pas indiquée dans hal.archives-ouvertes.fr/...
Mais, bon, moi, cela fait 25 ans que je n'ai pas trop travaillé les circuits du voyageur de commerce...
Sinon, vous avez toujours la solution
www.nojhan.net/geekscotte...
:)
Je ne connaissais pas ce document, il semble effectivement pouvoir aider.
Le professeur n'a posé aucune question très précise.
Le nom du cours est "calcul scientifique par la pratique", donc je pense qu'il voulait qu'on trouve un moyen d'implémenter le calcul du nombre de circuit, vu que le graphe a une description très précise et très régulière. (Je vous renvoie au lien du début d'article pour voir la description)
Merci pour le lien