Filière : Genie industiel et Logistique Recherche Operationelle Semetre : 1

Chapitre : 7
Chemins / Circuits / Chaines / Cycles Euleriens
Methode d’EULER
Réalisé par :

LMSIYAH Mohamed CHIFA Mouad

0656837417 0625578814

ASLOUNE Yahya BAHAA Fouad

0670976715 0687215233
EL ATYQY Mohamed Raid
0707223132
Année universitaire :
2022/2023
Encadré par : AKEF Fatiha
Plan

Introduction

Problèmatique et historique I III Chemins / Circuits Euleriens

pour les graphes orientés

Chaines /Cycles Euleriens pour Exercices d’applications

II IV
les graphes non orientés

Conclusion
Introduction
Nous avons déjà traité la méthode Hamiltonienne avec Demoucron et la
multiplication Latine, qui sert à trouver un chemin ou une chaine qui passe une seule
fois par tous les sommets d'un graphe orienté ou non orienté.

Nous allons traiter dans ce septième chapitre, la méthode d’Euler tout en

commençant par une introduction pour savoir l’intérêt du théorème d'Euler et son
historique, pour se faire, on va voir les définitions des graphes connexes, graphes
eulériens, puis, on passe a énoncer les théorèmes d'Euler pour les graphes non orientés
et orientés, les algorithmes nécessaires pour trouver les chaines/cycles/chemins et
circuits eulériens s’il est possible.

La méthode d'Euler est venue après le contexte des 7 ponts de Koningsberg pour
traiter la situation de trouver le chemin ou la chaine qui passe une seule fois par tous
les arrêtes d’un graphe.
3
I. Problematique et Historique :

La ville de Königsberg (aujourd'hui

Kaliningrad) est construite autour de deux
îles sur un fleuve.

Ces deux îles sont reliées entre elles par

un pont et six autres ponts relient les rives du
fleuve aux îles comme la photo ci jointe

Au 18éme siècle un casse tête est populaire chez les habitants de cette ville :

Est-il possible de se promener dans la ville en ne passant qu’une seul fois par
chacun des sept ponts de Königsberg ?
4
 Le célèbre mathématicien Euler est le premier qui a montré que ce problème n’a pas
de solution, en utilisant pour la premier fois la notion de graphe.

Le problème se reformule ainsi en termes de graphe :

Existe-t-il un cycle qui passe exactement une fois et une seule par toutes les arrêtes
dans le graphe suivant ?

5
 Leonhard Euler
(1707-1783)

Il a été le mathématicien et le physicien

le plus grand d’Europe au 18éme siècle,
tant par la qualité que par la quantité de
ses travaux qui portaient sur toutes les
questions de mathématiques pures et
appliquées de l’époque.
Il est surtout connu par la résolution du
problème des 7 ponts de Königsberg.

6
II. Chaine / Cycle eulerien pour les graphes non orientés :
1. Notions de base :
Graphe connexe :
Si pour tout couple de sommets du graphe , il existe une chaine reliant ces deux
sommets.
A A
Exemple:
B B
C C

D D

N’est pas connexe connexe

Graphe Eulérien :
C’est un graphe que l’on peut tracer sans lever le crayon et sans jamais parcourir deux
fois par la même arrête. 7
Chaine eulérienne :
C’est une chaine qui contient chaque arrête du graphe une et une seule fois.

Cycle eulérien :
On parle d’un cycle eulérien s’il s’agit d’une chaine eulérienne qui est parfaitement
fermée.

Autrement dit, elle doit vérifier la condition suivante :

Sommet de départ = Sommet d’arrivée

NB :
Dans la méthode d’Euler , on peut passer plus qu’une fois par le même
sommet mais pas par la même arrête .

8
2. Théorème d’Euler :
Théorème
G étant un graphe non-orienté quelconque :

1er cas : Un cycle eulérien si

o G est connexe .
o Tous les sommets sont de degré pair .

2em cas : Une chaine eulérienne si

o G est connexe .
o G possède seulement 2 sommets de degré impairs .

3em cas : Graphe n’est pas eulérien si

o Il ne possède aucune chaine eulérienne.
o Il ne possède aucun cycle eulérien.

Important
9
3. Méthode pour trouver chaine/cycle eulérien pour les graphes non orienté :

Les étapes à suivre pour déterminer est ce qu’il s’agit d’une chaine/cycle eulérien
dans un graphe non orienté :

1. Vérifier la condition de connexité.

2. Tracer le tableau des degrés des sommets du graphe.
3. Appliquer le théorème d’Euler.
4. Trouver la chaine / Cycle eulérien a l’aide d’algorithme.
Important

10
Algorithme pour trouver un cycle eulérien :

Algorithme d’Euler
Considérer un cycle simple quelconque T du graphe G ;
Supprimer du graphe G toutes les arrêtes de T ;
Tant que G comporte des arrêtes, faire :
Dans le cycle T , considérer le premier sommet non isolé ;
Lui substituer un cycle simple, dont ce sommet est l’origine ;
Supprimer du graphe G toutes les arrêtes de ce dernier cycle ;
L’algorithme est fini des que G n’a plus d’arrêtes ;

Important

11
Algorithme pour trouver une chaine eulérienne :

Algorithme d’Euler

Considérer une chaine simple quelconque, T, joignant les deux sommets de degré
impair du graphe G ;
Supprimer du graphe G toutes les arêtes de T ;
Tant que G comporte des arêtes, faire :
Dans la chaine T, considérer le premier sommet non isolé ;
Lui substituer un cycle simple, dont ce sommet est l’origine ;
Supprimer du graphe G toutes les arêtes de cette dernière chaine ;
L’algorithme est fini dés que G n’a plus d’arêtes ;
La chaine T est alors eulérienne
Important

12
4. Exemples d’application : A B C
Exemple d’application 1 : Un cycle eulérien
Pour traiter ce cas on pose le suivant
comme graphe D E F

▪ La connexité : Le graphe G est connexe G H I

▪ Le tableau des degrés des sommets du graphe :

Sommet A B C D E F G H I Somme
Degré 2 4 2 4 4 4 2 4 2 28

▪ Application du théorème d’Euler :

G est non orienté, connexe et ne présente aucun sommet de degré impair,
donc d’après le théorème d’Euler le graphe G possède au moins un cycle
eulérien.
13
▪ Nombre d’arêtes : La somme des degrés des sommets de G est 28 alors il s’agit
de : 28/2 = 14 arrêtes

Tout cycle eulérien comporte lui-même 14 arêtes .

14
 Afin de réduire le nombre d'instruction qu'on va exécuter, il est préférable de prendre
dés le départ le cycle qui contient le plus grand nombre des sommets du graphe

A B C A B C

D E F D E F

G H I G H I

Le graphe G de départ ABCFIHGDA

15
 Dans le cycle A B C F I H G D A, le premier sommet A est isolé donc on passe au second
sommet , le second sommet B est non isolé on substitue ce sommet par le cycle B E D B, on
supprime du graphe G tous les arrêtes de ce dernier cycle.

A B C A B C

D D E F
E F

G I G H I
H

ABCFIHGDA ABEDBCFIHGDA

16
 Dans le cycle A B E D B C F I H G D A, le premier sommet A est isolé donc on passe au second
sommet , le second sommet B est isolé, on passe au troisième sommet , le troisième sommet E
est non isolé on substitue ce sommet par le cycle E F H E, on supprime du graphe G tous les
arrêtes de ce dernier cycle.

A B C A B C

D D E F
E F

G I G H I
H

ABEDBCFIHGDA ABEFHEDBCFIHGDA

alors le cycle eulérien est :

ABEFHEDBCFIHGDA 17
 alors le cycle eulérien est :
ABEFHEDBCFIHGDA

A 1
B 8
C

14 7 2 9

D 6 E 3
F
4 10
13 5
G 12 H 11
I

18
 Exemple d’application 2 : Une chaine eulérienne B D

On va considérer le graphe G non C G

orienté suivant:
A
▪ La connexité : Le graphe G est
connexe F
(existence d’une chaine qui relie chaque 2 sommets E
du graphe).

▪ Le tableau des degrés des sommets du graphe :

Sommet A B C D E F G Somme
Degré 2 4 5 5 4 4 2 26

19
▪ Application du théorème d’Euler :
G est non orienté, connexe il présente exactement deux sommets de degré
impaire C et D ,alors d’après le théorème d’Euler G possède au moins une
chaine eulérienne.
Toute chaine eulérienne du graphe G relie nécessairement les 2 sommets
impairs C et D.

▪ Nombre d’arêtes : La somme des degrés des sommets de G est 26 alors il s’agit de :

26/2 = 13 arêtes

Toute chaine eulérienne est alors formée de 13 arêtes

20
 Considérons la chaine C F D et on supprime tous ses arrêtes

B B
D D
G G
A C A C

F F

E E
Le graphe G de départ CFD

21
 Dans la chaine C F D, le premier sommet C est non isolé
On substitue ce sommet par le cycle C B E C, on supprime du graphe
G tous les arrêtes de ce dernier cycle

B B
D D
G G
A C A C

F F

E E

CFD CBECFD

22
 Dans la chaine C B E C F D, le premier sommet C est non isolé
On substitue ce sommet par le cycle C A B D C, on supprime du graphe G
tous les arrêtes de ce dernier cycle

B B
D D
G G
A C A C

F F

E E
CBECFD CABDCBECFD

23
 Dans la chaine C A B D C B E C F D, le premier sommet C est isolé donc on passe au second
sommet , le second sommet A est isolé, on passe au troisième sommet , le troisième sommet B
est isolé .On passe au quatrième sommet , le quatrième sommet D est non isolé on substitue ce
sommet par le cycle D G F E D, on supprime du graphe G tous les arrêtes de ce dernier cycle.

B B
D D
G G
A C A C

F F

E E

CABDCBECFD CABDGFEDCBECFD

alors la chaine eulérienne trouvée:

CABDGFEDCBECFD 24
alors la chaine eulérienne trouvée:
CABDGFEDCBECFD

B
3 D
2 9 4 G
8
A 1
C 12
12 5
10
11 7
F
6
E

25
Exemple d’application 3 : Graphe n’est pas eulérien :

Dans ce cas là, on traite le graphe du problème

des 7 ponts de Königsberg
B
▪ La connexité : Le graphe G est
connexe
A D
▪ Le tableau des degrés des sommets du graphe :

Sommet A B C D Somme
C
Degré 5 3 3 3 14

▪ Application du théorème d’Euler :

G est non orienté, connexe et présente 4 sommets de degré impair (pas
exactement ) ,or d’après le théorème d’Euler le graphe n’est pas eulérien et
n’admet ni chaine eulérienne ni cycle eulérien.
Impossible de passer une seule fois par tous les ponts sans les répéter.
26
Exemple d’application 4 : Graphe n’est pas connexe :

▪ La connexité : Le graphe G n’est pas connexe

( ex : les deux sommets A et F n’avaient aucune chaine G
qui les relie ) .
F
D
▪ Application du théorème d’Euler :
G est non orienté, n’est pas connexe donc
d’après le théorème d’Euler. A
le graphe G n’est pas eulérien et n’admet ni C
chaine eulérienne ni cycle eulérien.

27
III. Principe Chemins / Circuit Euleriens :
1. Notions de base :
1.1. Degré d’un sommet selon Euler :
le degré d’un sommet A est la différence entre le nombre des arcs afférentes à A (qui
arrivent à A) et le nombre des arcs efférentes de A (qui partent de A) .

Exemple :
A B
Sommet A B C D
Arcs sortants 1 1 3 0
Arcs entrants 1 2 0 2
Degré du sommet 0 1 -3 2
C D

28
1.2. Graphe orienté simplement connexe :
Un graphe orienté est simplement connexe si pour chaque deux sommets A et B, il
existe au moins un chemin dans un seul sens entre A et B.
Astuce .
un graphe présente un chemin un graphe est simplement
passant par tous les sommets. connexe
Exemple : Important

A B E G

C D F
Ce graphe orienté est simplement Ce graphe orienté n’est pas simplement
connexe car tous les sommets sont liés par connexe car il n’y a pas de chemin entre
au moins un chemin dans un seul sens. les deux sommets E et F. 29
2. Enoncé du théorème d’Euler :
Théorème
G étant un graphe orienté quelconque :

1er cas : Un circuit eulérien si

o G est simplement connexe .
o Tous les sommets sont de degré nul .

2em cas : Un chemin eulérien si

o G est simplement connexe .
o G possède exactement 2 sommets de degré non nul, l’un de degré
-1 et l’autre de degré 1 .
3em cas : Graphe n’est pas eulérien si
o Il ne possède aucun chemin eulérien.
o Il ne possède aucun circuit eulérien.
Important
30
3. Méthode pour trouver chemin/circuit eulérien pour les graphes orienté :

Les étapes à suivre pour déterminer est ce qu’il s’agit d’un chemin/circuit eulérien
dans un graphe orienté :

1. Vérifier la condition de connexité.

2. Tracer le tableau des degrés des sommets du graphe.
3. Appliquer le théorème d’Euler.
4. Trouver le chemin/circuit eulérien a l’aide d’algorithme.
Important

31
Algorithme pour trouver un circuit eulérien :

Algorithme d’Euler
Considérer un circuit simple quelconque T du graphe G ;
Supprimer du graphe G tous les arcs de T ;
Tant que G comporte des arcs, faire :
Dans le cycle T , considérer le premier sommet non isolé ;
Lui substituer un circuit simple, dont ce sommet est l’origine ;
Supprimer du graphe G tous les arcs de ce dernier circuit ;
L’algorithme est fini des que G n’a plus d’arcs ;

Important

32
Algorithme pour trouver un chemin eulérien :

Algorithme d’Euler
Considérer un chemin simple quelconque T, du sommet de degré -1
vers le sommet de degré 1 du graphe G ;
Supprimer du graphe G tous les arcs de T ;
Tant que G comporte des arcs, faire :
Dans le cycle T , considérer le premier sommet non isolé ;
Lui substituer un circuit simple, dont ce sommet est
l’origine ;
Supprimer du graphe G tous les arcs de ce dernier circuit ;
L’algorithme est fini des que G n’a plus d’arcs ;

Important

33
4. Exemples d’application :
Exemple d’application 1 : Un circuit eulérien
G est orienté et simplement connexe car le chemin A B C D A E passe au moins
une fois par chaque sommet du graphe, et ne présente aucun sommet de degré
non nul.
Sommet A B C D E
Degré 0 0 0 0 0

A B

E C

Donc G possède au moins un circuit eulérien (d’après le 1er cas du théorème 34

d’Euler).
 Considérons le circuit A E A et on supprime tous
ses arcs

A B A B

E C E C

D D

Le graphe G de départ AEA

35
 Dans le circuit A E A, le premier sommet A est non isolé
On substitue ce sommet par le circuit A B C A, on supprime du graphe
G tous les arcs de ce dernier circuit

A B A B

E C E C

D D

AEA ABCAEA

36
 Dans le circuit A B C A E A, le premier sommet A est non isolé
On substitue ce sommet par le circuit A C D A, on supprime du graphe
G tous les arcs de ce dernier circuit

A B A B

E C E C

D D

ABCAEA ACDABCAEA

37
 Dans le circuit A C D A B C A E A, le premier sommet A est isolé donc on passe au
second sommet , le second sommet C est non isolé, on substitue ce sommet par le
circuit C B E C, on supprime du graphe G tous les arcs de ce dernier circuit.

A B A B

E C E C

D D
ACDABCAEA ACBECDABCAEA

38
 Dans le circuit A C B E C D A B C A E A, le premier sommet A est isolé donc on passe au
second sommet , le second sommet C est isolé, on passe au troisième sommet , le troisième
sommet B est non isolé on substitue ce sommet par le circuit B D B, on supprime du graphe
G tous les arcs de ce dernier circuit.

A B A B

E C E C

D D
ACBECDABCAEA ACBDBECDABCAEA

alors le circuit eulérien trouvé:

ACBDBECDABCAEA 39
alors le circuit eulérien trouvé:
ACBDBECDABCAEA

9
A B
5
1 4 2
8 11
3 10

6
E C
7

40
Exemple d’application 2 : Un chemin eulérien

G est orienté et simplement connexe car le chemin A B C D A E passe au moins une

fois par chaque sommet du graphe et présente exactement deux sommets de
degré non nul, l’un de degré -1 et l’autre de degré 1.

Sommet A B C D E
Degré 0 0 1 -1 0

A B

E C

D
alors G possède un chemin eulérien (d’après le 2éme cas du théorème d’Euler),
41
du sommet D (de degré -1) vers le sommet C (de degré 1).
 Considérons le chemin D E C et on supprime tous
ses arcs

A B A B

E C E C

D D

Le graphe G de départ DEC

42
 Dans le chemin D E C, le premier sommet D est non isolé
On substitue ce sommet par le circuit D B C D, on supprime du graphe
G tous les arcs de ce dernier circuit

A B A B

E C E C

D D

DEC DBCDEC

43
 Dans le chemin D B C D E C, le premier sommet D est non isolé
On substitue ce sommet par le circuit D A B D, on supprime du graphe
G tous les arcs de ce dernier circuit

A B A B

E C E C

D D

DBCDEC DABDBCDEC

44
Dans le chemin D A B D B C D E C, le premier sommet D est isolé donc on passe au
second sommet, le second sommet A est non isolé, on substitue ce sommet par le
circuit A E C A, on supprime du graphe G tous les arcs de ce dernier circuit

A B A B

E C E C

D D

DABDBCDEC DAECA BDBCDEC

45
Dans le chemin D A E C A B D B C D E C, le premier sommet D est isolé donc on passe au
second sommet, le second sommet A est non isolé, on substitue ce sommet par le
circuit A C B E A, on supprime du graphe G tous les arcs de ce dernier circuit

A B A B

E C E C

D D

DAECA BDBCDEC DACBEAECA BDBCDEC

alors le chemin eulérien trouvé:

DACBEAECA BDBCDEC 46
alors le chemin eulérien trouvé:
DACBEAECA BDBCDEC

9
A B
8 2
4 12
11
5 6 10 3

7
E C
15
1 13

14

47
 Exemple d’application 3 :

G est orienté et simplement connexe car le chemin A B C D B E passe au moins

une fois par chaque sommet du graphe, et présente exactement deux sommets de
degré non nul mais ces degrés ne sont pas -1 et 1.
Sommet A B C D E
Degré -2 0 -2 0 0

A B

E C

Alors G ne possède ni chemin eulérien ni circuit eulérien (d’après le 3ème cas du théorème d’Euler). 48
IV. Exercice d’application :
1. Graphe non orienté:
A B C D
Exercice 1 :

On considère le graphe G ci-dessus

1. Graphe G est-il connexe ? E F G H

2. Compléter le tableau suivant :

Sommet A B C D E F G H I J
Degré I J

3. Déterminer s’il s’agit d’une chaine eulérienne

ou une d’un cycle eulérien .
4. Trouvons chaine7cycle eulérien s’il existe.

49
Solution d’exercice 1 :

1. Graphe est connexe (pour tout couple de

sommets du graphe , il existe une chaine A B C D
reliant ces deux sommets)

2. Le tableau des degrés des sommets de

graphe : E F G H

Sommet A B C D E F G H I J
Degré 2 4 4 2 4 4 4 4 4 2 I J

3. Le graphe est connexe et les degrés sont paires ,alors d’après

le théorème d'Euler on a un cycle eulérien

50
4. Trouvons chaine/cycle eulérien.
Considérons le cycle A B C D H J I E A et on supprime tous ses arrêtes

A B C D A B C D

E F G H E F G H

I J I J

Le graphe G de départ ABCDHJIEA

51
 Dans le cycle A B C D H J I E A, le premier sommet A est isolé donc on passe au second
sommet , le second sommet B est non isolé on substitue ce sommet par le cycle B E F B, on
supprime du graphe G tous les arrêtes de ce dernier cycle.

A B C D A B C D

E F G H E F G H

I J I J

ABCDHJIEA ABEFBCDHJIEA

52
 Dans le cycle A B E F B C D H J I E A, le premier sommet A est isolé donc on passe au second
sommet , le second sommet B est isolé, on passe au troisième sommet , le troisième sommet E
est isolé ,on passe au quatrième sommet F on substitue ce sommet par le cycle F I G F, on
supprime du graphe G tous les arrêtes de ce dernier cycle.

A B C D A B C D

E F G H E F G H

I J I J

ABEFBCDHJIEA ABEFIGFBCDHJIEA

53
 Dans le cycle A B E F I G F B C D H J I E A, le premier sommet A est isolé donc on passe au
second sommet , le second sommet B est isolé, on passe au troisième sommet , le troisième
sommet E est isolé, le quatrième sommet est isolé ,le cinquième sommet I est isolé ,on passe
au sixième sommet G et on substitue ce sommet par le cycle G C H G, on supprime du graphe G
tous les arrêtes de ce dernier cycle.

A B C D A B C D

E F G H E F G H

I J I J

ABEFIGFBCDHJIEA ABEFIGCHGFBCHJIEA

54
Alors le cycle eulérien trouver est :
ABEFIGCHGFBCHJIEA

1 11 12
A B C D
13
17 2 10 6 7
3 F 9 G H
E 8
5
4 14
16 15
I J

55
Exercice 2 :

B
On considère le graphe G ci-dessus
C
1. Graphe G est-il connexe ? A
2. Compléter le tableau suivant :

Sommet A B C D E F
Degré D
F
3. Déterminer s’il s’agit d’une chaine eulérienne E
ou une d’un cycle eulérien .
4. Trouvons chaine7cycle eulérien s’il existe.

56
Solution d’exercice 2 :
B
1. Graphe est connexe (pour tout couple de
sommets du graphe , il existe une chaine
C
A
reliant ces deux sommets)

2. Le tableau des degrés des sommets de

graphe :
D
F
Sommet A B C D E F
E
Degré 3 4 4 3 4 4

3. Le graphe est connexe et les degrés sont impaires ,alors

d’après le théorème d'Euler on a une chaine eulérienne

57
4. Trouvons la chaine eulérienne.

Considérons la chaine A B F E C D et on supprime tous ses arrêtes

B B
C C
A A

D D
F F
E E

Le graphe G de départ ABFECD

58
 Dans la chaine A B F E C D, le premier sommet A est non isolé on substitue ce sommet par
le cycle A E D B C F A, on supprime du graphe G tous les arrêtes de ce dernier cycle.

B B
C C
A A

D D
F F
E E

ABFECD AEDBCFABFECD

59
Alors la chaine eulérienne trouver est :
AEDBCFABFECD

4 B
7
C
8 A
5 1
11
3
6
D 10
F
2 E 9

60
2. Graphe orienté:
Exercice 1 :

On considère le graphe G ci-dessus

A
1. Graphe G est-il simplement connexe ? Justifier
votre réponse
2. Compléter le tableau suivant :
Sommet A B C D B C
Degré

3. Est-ce que le graphe G est eulérien ?

D

61
Solution d’exercice 1 :

A
1. Graphe est simplement connexe (quelque
soit X et Y ,deux sommets du graphe ,il existe
au moins un chemin dans un seul entre X et Y)

2. Le tableau des degrés des sommets de B C

graphe :

Sommet A B C D
Degré 0 0 0 0 D

3. Le graphe est simplement connexe et les degrés sont nuls

,alors d’après le théorème d'Euler on a un circuit eulérien.

62
 Considérons le circuit B A C D B et on supprime tous ses arcs

A A

B C B C

D D

Le graphe G de départ BACDB

63
 Dans le circuit B A C D B, le premier sommet B est non isolé
On substitue ce sommet par le circuit B D C A B, on supprime du
graphe G tous les arcs de ce dernier circuit

A A

B C B C

D D

BACDB BDCABACDB

64
 Dans le circuit B D CA B A C D B, le premier sommet B est non isolé
On substitue ce sommet par le circuit B C B, on supprime du graphe G
tous les arcs de ce dernier circuit

A A

B C B C

D D

BDCABACDB BCBDCABACDB

65
Dans le circuit B C B D C A B A C D B, le premier sommet B est isolé donc on passe
au second sommet , le second sommet C est non isolé, on substitue ce sommet
par le circuit C A C, on supprime du graphe G tous les arcs de ce dernier circuit.

A A

B C B C

D D

BCBDCABACDB BCACBDCABACDB

66
Dans le circuit B C A C B D C A B A C D B, le premier sommet B est isolé donc on passe au
second sommet , le second sommet C est non isolé, on substitue ce sommet par le
circuit C D C, on supprime du graphe G tous les arcs de ce dernier circuit.

A A

B C B C

D D

BCACBDCABACDB BCDCACBDCABACDB

67
Alors le circuit eulérien trouver est :
BCDCACBDCABACDB

10 A 12
4
9 5
11
1
B C
6
7 14 13
8 2
3
D

68
Exercice 2 :

On considère le graphe G ci-dessus

1. Graphe G est-il simplement connexe ? Justifier

votre réponse A B
2. Compléter le tableau suivant :

Sommet A B C D E F
Degré E
3. Est-ce que le graphe G est eulérien ?
D F C

69
Solution d’exercice 2 :

1. Graphe est simplement connexe (un chemin

reliant tous les points du graphe)
A B

2. Le tableau des degrés des sommets de

graphe :
E
Sommet A B C D E F
Degré 0 0 0 1 -1 0 D F C

3. Le graphe est simplement connexe et on a deux sommets de degrés non nuls

,alors d’après le théorème d'Euler on a un chemin eulérien.

70
 Considérons le chemin E F D et on supprime tous ses arcs

A B A B

E E

D F C D C
F

Le graphe G de départ EFD

71
 Dans le chemin E F D, le premier sommet E est non isolé
On substitue ce sommet par le circuit E D A E, on supprime du graphe G tous
les arcs de ce dernier circuit

A B A B

E E

D F C D C
F

EFD EDAEFD

72
Dans le chemin E D A E F D, le premier sommet E est isolé donc on passe au second
sommet, le second sommet D est isolé, le troisième sommet A est non isole on
substitue ce sommet par le circuit A B C F A , on supprime du graphe G tous les arcs
de ce dernier circuit

A B A B

E E

D F C D C
F

EDAEFD EDABCFAEFD

73
Alors le circuit eulérien trouver est :
EDABCFAEFD

3
A B

2 7
6 4
E
1 8
D 9 F 5 C

74
Conclusion :
• Initiée par Euler, avec le célèbre problème des 7 ponts de Königsberg, les applications
de la théorie des graphes et de la recherche opérationnelle sont aujourd'hui immenses
tant au plan civil que militaire : aide à la décision, stratégie, optimisation (plus court
chemin, GPS, coût minimal), réseaux de transports : chemins de fer, métropolitain,
lignes aériennes, électricité, gaz, oléoducs (transport de l'énergie), Internet (réseau de
l'information), ports et aéroports, ordonnancement des tâches, etc

• Nous avons traité dans ce chapitre et qui résout le problème « passer par tous les
arrêtes (ou arcs) d’un graphe une et une seule fois » et si possible « revenir au point de
départ ».

• Le huitième chapitre va s'intéresser aux réseaux de transport, et plus particulièrement

à la recherche d'un flot maximum y circulant.

75
 Filière : Genie industiel et Logistique Recherche Operationelle Semetre : 1

Chapitre : 7
Chemins / Circuits / Chaines / Cycles Euleriens
Methode d’EULER
Réalisé par :

LMSIYAH Mohamed CHIFA Mouad

0656837417 0625578814

ASLOUNE Yahya BAHAA Fouad

0670976715 0687215233
EL ATYQY Mohamed Raid
0707223132
Année universitaire :
2022/2023
Encadré par : AKEF Fatiha