Nom du probleme de graphe (exploration urbaine)

Voilà, en regardant les ressources proposées par l'equipe prologin, je suis tombé sur ce probleme de graphe. La première partie consiste à trouver la plus grande composante connexe du graphe (ça c'est bon) La deuxième me parait plus compliqué: on veut trouver le trajet le plus court qui permet de visiter tous les noeuds de cette composante (on a le droit de passer plusieurs fois par une arrete ou un noeud)

Avant même de le résoudre, j'aimerais savoir si ce probleme a un nom dans la littérature.

Si j'ai bien compris, ce que l'on cherche n'est ni: - une recherche du plus court chemin (car on veut un chemin qui passe par tous les noeuds) - un chemin hamiltonien (car on peut passer plusieurs fois par le même noeud) - un chemin eulérien (car on est pas obligé de passer par toutes les arrètes)

Pour moi, le plus proche serait un probleme de chemin Eulerien en remplaçant chaque arrete {AB} par 2 arrètes dirigées (AB) (BA); mais ce n'est toujours pas ça parce que je n'ai pas besoin de passer par toutes ces arretes.

Help please !

Je crois que c'est un problème difficile (au sens de NP-complet) qui s'appelle salesman problem, et que je sache il n'y a pas d'algorithmes "efficaces". Je ne sais pas si ton problèmes correspond exactement à celui mentionné dans la page wikipédia, mais il y a beaucoup de variantes de ce problème, et ça me paraît un bon début pour cherche dans la litérature. La différence avec le salesman problem est que dans ce dernier, on doit revenir au début, mais ce n'est pas grave, tu peux modifier ton graphe de la façon suivante pour t'y ramener:

• tu ajoutes un nœud E à ton graphe
• tu relies ce nœud à tous les autres nœuds de ton graphe, toujours avec un poids M
• tu choisis M très grand devant tous les autres poids d'arêtes de ton graphe.

C'est une solution assez bourrine, surtout pour le choix du M, mais tant que les autres poids son assez faible ça devrait passer. Il doit sans doute exister de meilleures façon de convertir ton problème en (une variante du) salesman problem qui existent déjà dans la litérature (tu peux aussi faire un tour de stack overflow, j'ai trouvé pas mal de posts là-bas sur cette question)