Définition 1
Une chaîne est une liste ordonnée de sommets
telle que chaque sommet de la liste soit adjacent au sommet suivant.
Définition
2
Une chaîne fermée est une chaîne dont
l'origine et l'extrémité sont confondues.
Défintion 3
Une chaîne fermée composée d'arêtes toutes distinctes est un
cycle.
Définition 4
Une chaîne est eulérienne si
*
elle contient toutes les arêtes du graphe
*
chaque arête n'est décrite qu'une seule
fois
Théorèmes d'Euler :
1.
Un graphe connexe admet une chaîne eulérienne
si et seulement si deux sommets et deux seulement sont de degrés
impairs.
2. Un graphe connexe admet un cycle eulérien si et
seulement tous ses sommets sont de degrés pairs.
Graphe possédant une chaîne eulérienne
- Les chaînes 2-4-5-1-4-3-1-2-3 et 2-3-1-5-4-1-2-4-3 sont eulériennes.
- Les chaînes eulériennes doivent commencer par le sommet 2 et finir par le sommet 3 ou l'inverse car ce sont les deux sommets de degré impair.
- Il n'y a pas de cycle eulérien, car tous les sommets ne sont pas de degré pair.
Graphe ayant un cycle eulérien
- Tous les sommets sont de degré 2, il y a au moins un cycle eulérien, par exemple : le cycle 1-2-3-4-5-1.
Une applet pour appliquer