Riff News

Voir chaîne hamiltonienne.

chaîne eulérienne

20/06/09 - Cette définition a été signalée comme potentiellement incorrecte ou imprécise. Merci de nous faire part de vos observations.

Dans un graphe, chaîne simple passant par toutes les arêtes d'un graphe. Une chaîne eulérienne n'existe que si

• le graphe est connexe
• il a exactement deux sommets de degré impair.

Comparer avec chaîne hamiltonienne.

chaîne hamiltonienne

Dans un graphe, chaîne simple passant par tous les sommets d'un graphe une et une seule fois. Une chaîne hamiltonienne n'existe que si le graphe est connexe.

Comparer avec chaîne eulérienne. Voir traveling salesman.