Recherche de la plus courte chaine eulérienne

[LB2]

Bonjour,

Pour un graphe connexe G, dans le cas où il admet une chaine eulérienne (par théorème, si et seulement si le nombre de sommets de G de degré impair vaut 0 ou 2), je cherche un algorithme pour déterminer la(ou une) plus courte chaine eulérienne.

On connait l'algorithme de Dijkstra pour chercher le plus court chemin entre deux sommets fixés. Mais qu'en est-il pour mon problème?

Cordialement

[pascal16]

Tu as peut-être un problème à résoudre, mais l'énoncé que tu propose ne semble pas être le bon.

chaîne eulérienne -> toutes les arêtes sont parcourus -> la somme des poids est toujours la même -> toutes les chaînes sont de même longueur -> n'importe quelle chaîne eulérienne convient.

[LB2]

J'ai oublié de préciser qu'il s'agit d'un graphe non orienté et pondéré : chaque arête a un poids différent.

[pascal16]

si tu passes par toutes les arêtes une seule fois, le poids total est toujours le même

C'est dans le cas où il 'y a pas de chaîne eulérienne qu'on peut parcourir toutes les arêtes au moins une fois en cherchant le poids minimal.

[LB2]

Mais oui!! Merci beaucoup de ta réponse!