On considère le graphe G suivant :
G admet-il une chaîne eulérienne ou un cycle eulérien ?
D'après le théorème d'Euler, on sait qu'un graphe connexe admet :
- Une chaîne eulérienne si et seulement s'il possède 0 ou 2 sommets de degré impair.
- Un cycle eulérien si et seulement s'il ne possède aucun sommet de degré impair.
Afin de déterminer si le graphe G admet une chaîne ou un cycle eulérien, il faut donc étudier la connexité de G dans un premier temps et le nombre de sommets de degré impair dans un second temps.
Étude de la connexité de G
Un graphe est dit connexe si, pour tout couple de sommets, il existe une chaîne reliant ces deux sommets. On remarque que c'est bien le cas.
Le graphe G est donc connexe.
Étude du nombre de sommets de degré impair de G
Le degré d'un sommet désigne le nombre d'arêtes connectées à ce sommet.
- 2 arêtes sont reliées au sommet A : le degré de A est donc pair.
- 2 arêtes sont reliées au sommet B : le degré de B est donc pair.
- 2 arêtes sont reliées au sommet C : le degré de C est donc pair.
- 2 arêtes sont reliées au sommet D : le degré de D est donc pair.
- 3 arêtes sont reliées au sommet E : le degré de E est donc impair.
- 1 arête est reliée au sommet F : le degré de F est donc impair.
On en déduit que deux sommets sont de degré impair.
Le graphe G est connexe et possède deux sommets de degré impair, il admet donc une chaîne eulérienne mais pas de cycle eulérien.
On considère le graphe G suivant :
G admet-il une chaîne eulérienne ou un cycle eulérien ?
On considère le graphe G suivant :
G admet-il une chaîne eulérienne ou un cycle eulérien ?
On considère le graphe G suivant :
G admet-il une chaîne eulérienne ou un cycle eulérien ?
On considère le graphe G suivant :
G admet-il une chaîne eulérienne ou un cycle eulérien ?
On considère le graphe G suivant :
G admet-il une chaîne eulérienne ou un cycle eulérien ?