Filière: Génie Informatique Année universitaire : 2023/2024

Semestre : 3 Travaux dirigés N° 01 Module: Théorie des Graphe,

Cryptographie et Python
(Corrigé)
Enseignant : Sidati KHABID Matière : Théorie des Graphe et
Cryptographie

Exercice N° 1
Le degré de chacun des sommets du graphe :
Sommet A B C D E F G H I
Degré 4 6 4 2 4 4 6 4 2

Exercice N° 2
1. Représentons cette situation par un graphe d'ordre 6 dans lequel chaque arête
reliant i et j signifie que i espionne j et que j espionne i :

2. Ce graphe n’est pas complet car deux espions d’un même pays ne s’espionnent pas,
donc les sommets correspondants ne sont pas adjacents.
En revanche ce graphe est connexe car entre tout couple de points, il existe au
moins une chaîne.
3. Les sommets sont tous de degré 4 car chaque espion en espionne quatre autres,
6×4
Donc d’après le lemme des poignées de main le nombre des arrêts est : = 12
2

Exercice N° 3
a) Si le graphe simple contient 4 sommets, chacun de ceux-ci est de degré au maximum
égal à 3, d’où une somme totale des degrés égale au plus à 12. Puisque cette somme

P A G E |1
Filière: Génie Informatique Année universitaire : 2023/2024
Semestre : 3 Travaux dirigés N° 01 Module: Théorie des Graphe,
Cryptographie et Python
(Corrigé)
Enseignant : Sidati KHABID Matière : Théorie des Graphe et
Cryptographie

est égale au double du nombre d’arêtes, ce nombre d’arêtes ne peut excéder 6, donc
ne peut pas être égal à 7.
b) Si le graphe simple contient 5 sommets, chacun de ceux-ci est de degré au maximum
égal à 4, d’où une somme totale des degrés égale au plus à 20. Puisque cette somme
est égale au double du nombre d’arêtes, ce nombre d’arêtes ne peut excéder 10,
donc ne peut pas être égal à 11.
c) Si le graphe simple contient 10 sommets, chacun de ceux-ci est de degré au
maximum égal à 9, d’où une somme totale des degrés égale au plus à 90. Puisque
cette somme est égale au double du nombre d’arêtes, ce nombre d’arêtes ne peut
excéder 45, donc ne peut pas être égal à 46.

Exercice N° 4

1. Représentons cette situation par un graphe d'ordre 10 dans lequel une arête entre
les sommets i et j signifie qu'il y a une relation d'amitié entre i et j.

2. Ce graphe n’est pas complet car, par exemple, 1 et 2 ne sont pas adjacents. Il n’est
pas connexe car il n’existe pas de chaînes reliant 3 et 4. En revanche, il admet deux
sous graphes connexes (1, 2, 3, 6, 7, 8) (4, 5, 10) et un point isolé 9

P A G E |2
Filière: Génie Informatique Année universitaire : 2023/2024
Semestre : 3 Travaux dirigés N° 01 Module: Théorie des Graphe,
Cryptographie et Python
(Corrigé)
Enseignant : Sidati KHABID Matière : Théorie des Graphe et
Cryptographie

3. Si l'adage "les amis de nos amis sont nos amis" était vérifié la composante connexe
(1, 2, 3, 6, 7, 8) serait complète

Exercice N° 5
Considérons le graphe simple dont les sommets représentent les 15 ordinateurs ;
les arêtes représentent les liaisons entre ces ordinateurs. Si chaque appareil est relié à
exactement 3 ordinateurs du réseau, les sommets du graphe sont tous de degré impair.
D’après le résultat de cours, un tel graphe doit posséder un nombre pair de sommets, le
réseau est donc impossible.

Exercice N° 6
La figure ci-dessous montre deux graphes 3-réguliers (on dit aussi cubiques), ayant
respectivement 4 et 6 sommets. En effet, on constate aisément qu’il n’existe pas de
graphes cubiques ayant un nombre impair de sommets : le nombre d’arêtes d’un graphe
cubique à n sommets est 3n/2, qui n’est entier que lorsque n est pair.

Exercice N° 7
Tracer les figures « sans lever » le crayon revient à exhiber une chaine eulérienne.

Or ceci n’est possible que si et seulement si le nombre de sommets de degré impair

est égal à 0 (on aura affaire à un cycle eulérien, donc le retour se fera sur le sommet de

P A G E |3
Filière: Génie Informatique Année universitaire : 2023/2024
Semestre : 3 Travaux dirigés N° 01 Module: Théorie des Graphe,
Cryptographie et Python
(Corrigé)
Enseignant : Sidati KHABID Matière : Théorie des Graphe et
Cryptographie

départ) ou à 2. Pour le premier graphe, c’est impossible, tous les sommets étant de degrés
impairs. Pour les trois autres graphes, c’est possible.

En ce qui concerne le 3ème graphe, tous les sommets étant de degré pair, on a même
l’existence d’un cycle eulérien.

Exercice N° 8
En numérotant les pièces et en matérialisant les portes par des arêtes, on traduit la
situation par le graphe ci-dessous :

Se promener dans la maison en passant par chacune des ouvertures revient à

chercher l’existence d’une chaîne eulérienne

Seuls deux sommets étant de degrés impairs (1 et 2), les autres étant de degré pair, il
est possible de trouver une chaîne eulérienne associée à ce graphe.

Pour la deuxième situation, il est nécessaire de créer un 6éme sommet nommé «

extérieur » (E)

P A G E |4
Filière: Génie Informatique Année universitaire : 2023/2024
Semestre : 3 Travaux dirigés N° 01 Module: Théorie des Graphe,
Cryptographie et Python
(Corrigé)
Enseignant : Sidati KHABID Matière : Théorie des Graphe et
Cryptographie

Il existe maintenant quatre sommets de degré impairs (1,2,4 et E) , les autres étant
de degré pair, il est impossible de trouver une chaîne eulérienne associée à ce graphe.

Exercice N° 9
Trouver des itinéraires qui permettent de parcourir une seule fois chaque route
revient à trouver une chaîne eulérienne (voire un cycle) associée à ce graphe.

Tous les sommets étant de degré pair, le théorème d’Euler assurer l’existence d’un
cycle eulérien (donc d’une chaîne eulérienne)

a) E-C-D-A-C-B-E est un exemple

b) il n’existe pas de chaîne eulérienne partant de C et en terminant à D

Exercice N° 10
Numérotons les sommets. Soit M la matrice d'adjacence.

P A G E |5
Filière: Génie Informatique Année universitaire : 2023/2024
Semestre : 3 Travaux dirigés N° 01 Module: Théorie des Graphe,
Cryptographie et Python
(Corrigé)
Enseignant : Sidati KHABID Matière : Théorie des Graphe et
Cryptographie

01 1
On a 𝑀 = [11 1]
11 0
0 1 1 0 1 1 2 2 1
2
Et 𝑀 = 𝑀 × 𝑀 = [1 1 1] × [ 1 1 1] = [ 2 3 2]
1 1 0 1 1 0 1 2 2
2 2 1 2 2 1 9 12 8
Donc 𝑀4 = 𝑀2 × 𝑀2 = [2 3 2] × [2 =
3 2] [12 17 12]
1 2 2 1 2 2 8 12 9
Et comme 𝑇𝑟𝑎𝑐𝑒(𝑀4 ) = 9 + 17 + 9 = 35, il y a 35 circuits de longeur 4 dans G.
Exercice N° 11
Numérotons les sommets. Soit M la matrice d'adjacence.

0 1 1 0
On a 𝑀 = [1 0 1 1]
1 1 0 1
0 1 1 0
0 1 1 0 0 1 1 0 2 1 1 2
Et 𝑀 2 = [1 0 1 1] × [1 0 1 1] = [ 1 3 2 1]
1 1 0 1 1 1 0 1 1 2 3 1
0 1 1 0 0 1 1 0 2 1 1 2

P A G E |6
Filière: Génie Informatique Année universitaire : 2023/2024
Semestre : 3 Travaux dirigés N° 01 Module: Théorie des Graphe,
Cryptographie et Python
(Corrigé)
Enseignant : Sidati KHABID Matière : Théorie des Graphe et
Cryptographie

2 1 1 2 2 1 1 2 10 9 9 10
D’où 𝑀4 = 𝑀2 × 𝑀2 = [1 3 2 1] × [1 3 2 1] = [ 9 15 14 9 ]
1 2 3 1 1 2 3 1 9 14 15 9
2 1 1 2 2 1 1 2 10 9 9 10
10 9 9 10 0 1 1 0 18 29 29 18
Donc 𝑀5 = 𝑀4 × 𝑀 = [ 9 15 14 9 ] × [1 0 1 1] = [29 32 33 29]
9 14 15 9 1 1 0 1 29 33 32 29
10 9 9 10 0 1 1 0 18 29 29 18
Il y a donc 18 chaînes de longueur 5 de x à y
Exercice N° 12
Trouver la matrice des distances pour les graphes simples suivants :

a) D5 :
0 ∞ ∞ ∞ ∞
∞ 0 ∞ ∞ ∞
𝐷= ∞ ∞ 0 ∞ ∞
∞ ∞ ∞ 0 ∞
[∞ ∞ ∞ ∞ 0]
b) K5 :
0 1 1 1 1
1 0 1 1 1
𝐷= 1 1 0 1 1
1 1 1 0 1
[1 1 1 1 0]

c) C5 :
0 1 2 2 1
1 0 1 2 2
𝐷= 2 1 0 1 2
2 2 1 0 1
[1 2 2 1 0]

P A G E |7
Filière: Génie Informatique Année universitaire : 2023/2024
Semestre : 3 Travaux dirigés N° 01 Module: Théorie des Graphe,
Cryptographie et Python
(Corrigé)
Enseignant : Sidati KHABID Matière : Théorie des Graphe et
Cryptographie

d) R5 :
0 1 1 1 1 1
1 0 1 2 2 1
𝐷= 1 1 0 1 2 2
1 2 1 0 1 2
1 2 2 1 0 1
[1 1 2 2 1 0]

E5 :

0 1 1 1 1 1
1 0 2 2 2 2
𝐷= 1 2 0 2 2 2
1 2 2 0 2 2
1 2 2 2 0 2
[1 2 2 2 2 0]

Exercice N° 13
Appliquons l'algorithme de Moore pour trouver la distance entre u et v dans le
graphe orienté suivant :

Donc d(u,v)=4

P A G E |8
Filière: Génie Informatique Année universitaire : 2023/2024
Semestre : 3 Travaux dirigés N° 01 Module: Théorie des Graphe,
Cryptographie et Python
(Corrigé)
Enseignant : Sidati KHABID Matière : Théorie des Graphe et
Cryptographie

Exercice N° 14
A l'aide de la matrice d'adjacence, trouvons la matrice des distances du graphe
orienté suivant :

0 1 0 1
On a la matrice d’adjacence est 𝑀 = [0 0 0 1]
0 1 0 1
0 1 0 0
0 1 0 1 0 1 0 1 0 1 0 1
Et 𝑀 2 = 𝑀 × 𝑀 = [0 0 0 1] × [0 0 0 1] = [ 0 1 0 0]
0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 0 0 1 0 0 0 0 0 1
0 1 0 1 0 1 0 1 0 1 0 1
D’où 𝑀3 = 𝑀2 × 𝑀 = [0 1 0 0] × [0 0 0 1] = [ 0 0 0 1]
0 1 0 1 0 1 0 1 0 1 0 1
0 0 0 1 0 1 0 0 0 1 0 0
0 1 ∞ 1
Donc 𝐷 = [∞ 0 ∞ 1]
∞ 1 0 1
∞ 1 ∞ 0
Exercice N° 15
Numérotons les sommets, comme dans la figure ci-dessous. La matrice C et ses
puissances successives sont :

P A G E |9
Filière: Génie Informatique Année universitaire : 2023/2024
Semestre : 3 Travaux dirigés N° 01 Module: Théorie des Graphe,
Cryptographie et Python
(Corrigé)
Enseignant : Sidati KHABID Matière : Théorie des Graphe et
Cryptographie

0 5 ∞ 10 ∞
∞ 0 2 ∞ 11
𝐶= ∞ ∞ 0 2 5
∞ ∞ ∞ 0 1
[∞ ∞ ∞ ∞ 0]

0 5 7 10 11
∞ 0 2 ∞ 11
𝐶2 = ∞ ∞ 0 2 3
∞ ∞ ∞ 0 1
[∞ ∞ ∞ ∞ 0 ]

0 5 7 9 11
∞ 0 2 4 5
𝐶3 = ∞ ∞ 0 2 3
∞ ∞ ∞ 0 1
[∞ ∞ ∞ ∞ 0]

0 5 7 9 10
∞ 0 2 4 5
𝐶4 = ∞ ∞ 0 2 3
∞ ∞ ∞ 0 1
[∞ ∞ ∞ ∞ 0]

0 5 7 9 10
∞ 0 2 4 5
𝐶5 = ∞ ∞ 0 2 3 = 𝐶4
∞ ∞ ∞ 0 1
[∞ ∞ ∞ ∞ 0]

P A G E | 10
Filière: Génie Informatique Année universitaire : 2023/2024
Semestre : 3 Travaux dirigés N° 01 Module: Théorie des Graphe,
Cryptographie et Python
(Corrigé)
Enseignant : Sidati KHABID Matière : Théorie des Graphe et
Cryptographie

Exercice N° 16
Le graphe simple R5 est donné par la figure ci-dessous. La matrice C et ses puissances
successives sont :

0 1 1 1 1 1
1 0 1 ∞ ∞ 1
1 1 0 1 ∞ ∞
𝐶=
1 ∞ 1 0 1 ∞
1 ∞ ∞ 1 0 1
[1 1 ∞ ∞ 1 0]

0 1 1 1 1 1
1 0 1 2 2 1
𝐶2 = 1 1 0 1 2 2 = 𝐶3
1 2 1 0 1 2
1 2 2 1 0 1
[1 1 2 2 1 0]

P A G E | 11
Filière: Génie Informatique Année universitaire : 2023/2024
Semestre : 3 Travaux dirigés N° 01 Module: Théorie des Graphe,
Cryptographie et Python
(Corrigé)
Enseignant : Sidati KHABID Matière : Théorie des Graphe et
Cryptographie

Exercice N° 17
Appliquons l'algorithme de Dijkstra pour trouver un chemin minimum (et sa valeur)
entre les sommets x5 et x4 :

Poids x1 x2 x3 x4 x5 Sélectionné
0 6. x5 0. x5 x5
6 12. x2 6. x5 9. x2 15. x2 x2
9 11. x3 9. x2 15. x3 x3
11 11. x3 13. x1 x1
13 13. x1 x4
C=[X5, X2, X3, X1, X4] et Valeur=13

Exercice N° 18
Trouvons un flot maximum dans le réseau suivant :

Donc le flot maximum est 8+5+4=6+4+7=17

P A G E | 12