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.
- 1 arête est reliée au sommet A : le degré de A est donc impair.
- 3 arêtes sont reliées au sommet B : le degré de B est donc impair.
- 4 arêtes sont reliées au sommet C (une boucle compte pour 2 arêtes) : le degré de C est donc pair.
- 2 arêtes sont reliées au sommet D : le degré de D est donc pair.
On en déduit que deux sommets (A et B) sont de degré impair et deux sommets (C et D) sont de degré pair.
Le graphe est donc connexe et admet exactement deux sommets d'ordre impair. On peut conclure :
Le graphe G 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 ?
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.
- 2 arêtes sont reliées au sommet E : le degré de E est donc pair.
On en déduit que tous les sommets sont de degré pair.
Le graphe G est connexe et ne possède pas de sommets de degré impair, il admet donc un cycle eulérien qui est aussi une chaîne eulérienne.
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.
- 4 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.
- 3 arêtes sont reliées au sommet C : le degré de C est donc impair.
- 3 arêtes sont reliées au sommet D : le degré de D est donc impair.
- 2 arêtes sont reliées au sommet E : le degré de E est donc pair.
On en déduit que les sommets C et D 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 ?
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.
- 4 arêtes sont reliées au sommet E : le degré de E est donc pair.
On en déduit que tous les sommets sont de degré pair.
Le graphe G est connexe et ne possède pas de sommets de degré impair, il admet donc un cycle eulérien qui est aussi une chaîne eulérienne.
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.
- 3 arêtes sont reliées au sommet A : le degré de A est donc impair.
- 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.
- 3 arêtes sont reliées au sommet D : le degré de D est donc impair.
- 2 arêtes sont reliées au sommet E : le degré de E est donc pair.
- 2 arêtes sont reliées au sommet F : le degré de F est donc pair.
On en déduit que deux sommets sont de degré impair.
Le graphe G est connexe et possède exactement 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 ?
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.
- 3 arêtes sont reliées au sommet B : le degré de B est donc impair.
- 3 arêtes sont reliées au sommet C : le degré de C est donc impair.
- 3 arêtes sont reliées au sommet D : le degré de D est donc impair.
- 3 arêtes sont reliées au sommet E : le degré de E est donc impair.
- 4 arêtes sont reliées au sommet F : le degré de F est donc pair.
On en déduit que quatre sommets sont de degré impair.
Le graphe G est connexe et possède quatre sommets de degré impair, il n'admet donc pas de chaîne eulérienne ni de cycle eulérien.
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.
- 1 arête est reliée au sommet A : le degré de A est donc impair.
- 3 arêtes sont reliées au sommet B : le degré de B est donc impair.
- 2 arêtes sont reliées au sommet C : le degré de C est donc pair.
- 3 arêtes sont reliées au sommet D : le degré de D est donc impair.
- 1 arête est reliée au sommet E : le degré de E est donc impair.
On en déduit que quatre sommets sont de degré impair.
Le graphe G est connexe et possède quatre sommets de degré impair, il n'admet donc pas de chaîne eulérienne ni de cycle eulérien.