Discussion :

[ColonelHati]

Bonjour à tous, mailgré mes recherches je n'ai pas réussi a trouver mon bonheur, je viens donc vous demander de l'aide

J'ai besoin de 2 algorithmes, chacun devant s'appliquer sur un graphe orienté.
Pour le premier, je dois déterminer un chemin passant une et une seule fois par chaque sommet du graphe, donc un chemin hamiltonien.
Pour le second, je dois déterminer un chemin passant une et une seule fois par chaque arête, donc un chemin eulérien.
Pourriez vous m'indiquer des algorithmes qui pourraient faire mon bonheur?

J'avais réalisé un projet de résolution du problème du voyageur de commerce gràce a des colonies de fourmis, pensez vous que je pourrais reconvertir cet algo alors que je cherche un chemin et plus un circuit, et qu'en plus le graphe est orienté?

Merci d'avance de vos réponses.

[PRomu@ld]

Pour le problème du chemin eulérien ceci devrait t'aider :

http://gilco.inpg.fr/~rapine/Graphe/...hme_euler.html

Pour le problème du chemin hamiltonien, c'est plus compliqué, c'est un problème NP-Complet, tu peux regarder ici :

http://www.enseignement.polytechniqu...spuhl/adn.html

[ColonelHati]

Merci de cette réponse

J'ai quelques questions:

- pour le chemin eulérien, mon graphe est orienté contrairement a l'exemple, celà ne posera pas de problèmes? Il me suffira de modifier la liste des voisins du sommet étudié en conséquence?

- pour le graphe hamiltonien, cet exeemple est parfait car mon projet porte justement sur du séquençage d'ADN Par contre, étant donné les conditions de construction de mon graphe, les arêtes auront toutes la même valuation, ça ne posera pas de problème?

Y aurait il d'autres méthodes pour le graphe hamiltonien, ici il s'agit d'un algorithme glouton, donc surement très gourmand en ressources...

Merci de votre aide

[PRomu@ld]

Y aurait il d'autres méthodes pour le graphe hamiltonien, ici il s'agit d'un algorithme glouton, donc surement très gourmand en ressources...

Un algorithme glouton ne veut pas dire qu'il va utiliser beaucoup de ressources. Celà veut dire qu'il va effectuer des choix qu'il considère comme étant des optimums locaux dans les étapes intermédiaires.

Par contre, étant donné les conditions de construction de mon graphe, les arêtes auront toutes la même valuation, ça ne posera pas de problème?

Je ne vois pas ce que ça peut changer.

- pour le chemin eulérien, mon graphe est orienté contrairement a l'exemple, celà ne posera pas de problèmes? Il me suffira de modifier la liste des voisins du sommet étudié en conséquence?

En fait, le chemin eulérien existe sous certaines conditions (cf euler) dans un graphe non-orienté, pour un graphe orienté ça risque poser des problèmes d'existence. Si ton orientation n'est pas utile ici, tu peux doubler les arcs (si tu as (x,y) tu crées (y,x) )

[FrancisSourd]

En fait, le chemin eulérien existe sous certaines conditions (cf euler) dans un graphe non-orienté, pour un graphe orienté ça risque poser des problèmes d'existence. Si ton orientation n'est pas utile ici, tu peux doubler les arcs (si tu as (x,y) tu crées (y,x) )

Non, il y a également une condition très simple pour savoir s'il y a un circuit eulérien dans un graphe orienté: il faut et il suffit que chaque noeud ait le même nombre d'arcs entrants que d'arcs sortants.

Lorsqu'il n'y a pas de circuit eulérien, le problème du postier chinois peut aussi vous intéresser: il faut trouver le plus court circuit qui passe par tous les arcs au moins une fois (mais on peut éventuellement passer plusieurs fois par le même arc si nécessaire).

[PRomu@ld]

Non, il y a également une condition très simple pour savoir s'il y a un circuit eulérien dans un graphe orienté: il faut et il suffit que chaque noeud ait le même nombre d'arcs entrants que d'arcs sortants.

En fait, ma référence à Euler était celle ci : "Si un graphe admet exactement 0 ou 2 sommets de degrés impairs alors il existe un chemin eulérien". Ce que tu donnes en est un cas particulier (tous les sommets sont de degrés pair).