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).

[FrancisSourd]

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).

Tu donnes effectivement le théorème pour un chemin eulérien dans un graphe non orienté. Pour qu'il y ait un circuit il faut (et il suffit) qu'il n'y ait aucun degré impair. La distinction entre les arcs entrants et sortants est spécifique au cas orienté.

S'il y a un circuit eulérien dans le graphe orienté, le même circuit reste eulérien dans la version non orientée (et ce circuit est également un chemin particulier).

Ce que je dis peut donc être vu comme un cas particulier de la condition nécessaire. Mais ce n'est pas un cas particulier si on regarde la condition suffisante: s'il n'y a pas de circuit eulérien dans le graphe orienté, cela ne veut pas dire qu'il n'y a pas de chemin eulérien dans le graphe support non orienté du graphe orienté.

[N_I_C_S]

Salut,

Je vais peut-être paraître naïf mais le calcul matriciel pour trouver un chemin hamiltonien de manière exhaustive (performant pour un "petit" graphe) peut être suffisant :

- présenter le graphe sous forme de matrice carrée d'ordre (nb sommets) : ( sommets (depart) * sommets (arrivee) )

- mettre "AB" sur (A depart-B arrivée) si arc (A, B) orienté

- monter la matrice à la puissance (nb sommets - 1). multiplication : concatenation des arcs. multiplication par une case vide -> case vide

- tester les "cases" restantes : si elles contiennent tous les sommets, ce sont des chemins hamiltoniens

[olibara]

Bonsoir

Pour ma part je cherche des algorithme ou methodes permettant de résoudre le postier Chinois

On poursuit le sujet ici ?
Ou on ouvre un autre sujet ?

Merci de vos conseils

[djanos]

Salut,

Je vais peut-être paraître naïf mais le calcul matriciel pour trouver un chemin hamiltonien de manière exhaustive (performant pour un "petit" graphe) peut être suffisant :

- présenter le graphe sous forme de matrice carrée d'ordre (nb sommets) : ( sommets (depart) * sommets (arrivee) )

- mettre "AB" sur (A depart-B arrivée) si arc (A, B) orienté

- monter la matrice à la puissance (nb sommets - 1). multiplication : concatenation des arcs. multiplication par une case vide -> case vide

- tester les "cases" restantes : si elles contiennent tous les sommets, ce sont des chemins hamiltoniens

Je cherche actuellement un chemin hémiltoniens dans un graphe.
J'ai donc essayer cette méthode mais je ne comprend pas les dernière étape nécessaire pour obtenir une matrice ne contenant que des chemins hémiltonien : j'ai bien monter la matrice à la puissance sommet-1 mais je ne comprend pas les étapes "multiplication : concatenation des arcs" et "multiplication par une case vide -> case vide"
Si quelqu'un pouvais m'expliquer..