Chapitre V

Premières notions sur les graphes

1. Graphes non orientés

a) Définition
A titre d’exemple

On considère un réseau ferroviaire composé des lignes :

Paris-Strasbourg ; Paris-Lyon ; Paris-Marseille ; Paris-Rennes ; Lyon-Strasbourg ; Lyon-Marseille ; Lyon-Rennes ;
Marseille-Nice ; Marseille-Bordeaux ; Rennes-Bordeaux et Bordeaux-Nice.

Sur chaque ligne, la circulation peut se faire dans les deux sens.
1. Faire un schéma du réseau ferroviaire en représentant les stations par leurs initiales et les lignes par un segment
reliant deux stations.

Le réseau est alors représenté par un graphe, non orienté car on peut se déplacer dans les deux sens sur chaque ligne.
• Chaque station correspond à un sommet du graphe ;
p V-2 Chap. V

• chaque ligne correspond à une arête du graphe ;

• le nombre de stations est l’ordre du graphe.

2. A partir de Rennes, combien de villes peut-on atteindre en prenant une seule ligne ?

• Les villes qu’on peut atteindre en prenant une seule ligne depuis Rennes correspondent aux sommets adjacents
au sommet R.

• Le nombre de villes qu’on peut atteindre en prenant une seule ligne depuis Rennes correspond au degré du
sommet R.

3. Peut-on partir de Bordeaux et arriver à Nice en prenant une seule ligne ? deux lignes ? Trois lignes ? Quatre
lignes ? Si oui, donner le parcours en indiquant dans l’ordre les initiales des villes, séparées par « - ».

• Un tel parcours constitue une chaîne du graphe ; sa longueur est le nombre d’arêtes.
• Un parcours ayant la même ville comme départ et comme arrivée correspond à une chaîne fermée : par exemple,
P-R-L-M-B-R-P (on remarque qu’on retrouve une arête à deux reprises).
4. Décrire une boucle ayant pour départ et arrivée Paris, et passant par quatre lignes toutes différentes les unes
des autres.

• Une telle boucle ayant la même ville de départ et d’arrivée, et empruntant des lignes différentes constitue un
cycle du graphe.

Définition

• Un graphe non orienté d’ordre n est un ensemble de n points, nommés sommets, éventuellement reliés
par des segments, nommés arêtes.
• Deux sommets reliés par une arête sont dits adjacents.
• Le degré d’un sommet est le nombre d’extrémités d’arêtes parvenant à ce sommet.

• Un graphe est complet si ses sommets sont tous deux à deux adjacents.
• On dit qu’un graphe est connexe si quels que soient les sommets u et v du graphe, il existe une chaîne reliant
u à v.

Recherche 1

Dresser le tableau donnant le degré de chaque sommet du graphe de l’exemple précédent.

....................................................................................................................
....................................................................................................................
....................................................................................................................
....................................................................................................................
....................................................................................................................
....................................................................................................................

Laboratoire de Maths du lycée Roland-Garros à LA REUNION

 1.. GRAPHES NON ORIENTÉS p V-3

En guise d’explications

On peut envisager une arête reliant un sommet à lui-même ; dans ce cas-là, cette arête « compte double » pour le
calcul du degré du sommet.

Par exemple, on s’intéresse à des parcours pédestres dans une forêt, reliant quatre secteurs A, B, C et D.
Il existe un sentier reliant les secteurs A et B, un autre reliant A et C, un autre reliant B et C, un autre reliant C et
D, et un sentier faisant une boucle qui part et revient au secteur A.
Représenter le graphe correspondant, et dresser le tableau donnant le degré de chaque sommet.

Recherche

Exercice 1 : Parmi huit élèves volontaires, un professeur de Mathématiques doit constituer un groupe de trois
personnes pour faire une interrogation orale. Le professeur doit faire attention aux relations entre élèves :

• Erwan ne supporte pas Thibault ;

• Jordan refuse de travailler avec Gwendoline ;
• Thibault n’arrive jamais à rester sérieux avec Alexis ;
• Elodie n’apprécie ni Gwendoline, ni Alim, ni Aya ;

• Alim a du mal à travailler avec Alexis et Aya ;

• Alexis ne veut pas travailler avec Erwan ;
• Aya ne supporte ni Jordan, ni Alim.

1. Construire un graphe non orienté, qui permettra au professeur de constituer deux groupes : un avec Erwan, et
un deuxième à constituer parmi les élèves absents du premier groupe.

2. Malgré toutes ces rancoeurs entre élèves, le professeur pourrait-il constituer un groupe de quatre élèves ?

b) Degré et nombre d’arêtes

Propriété ▶ Somme des degrés d’un graphe

Dans un graphe, la somme des degrés de tous les sommets est égale au double du nombre d’arêtes.
Explications : Une arête a deux extrémités ; dans la somme des degrés, chaque arête est comptée deux fois.

Exercice 2 : entraînement avec un corrigé en vidéo

Appliquer la propriété de la somme des degrés (graphe)

Recherche

Exercice 3 : Est-il possible de relier chacun des ces sept ordinateurs

à exactement trois autres ? A exactement quatre autres ?
Si oui, représenter ci-contre le réseau obtenu.

Laboratoire de Maths du lycée Roland-Garros à LA REUNION

p V-4 Chap. V

Exercice 4 : Au cours d’un week-end, un tournoi de jeux de plateau est organisé par équipe. Les organisateurs
prévoient que 4, 5, 6 ou 7 équipes peuvent être engagées dans ce tournoi, et ils doivent élaborer des affrontements
dans chacune de ces configurations.

1. Quatre équipes. On note A, B, C et D ces équipes et on représente les rencontres du tournoi par le graphe
ci-dessous.

D C

a) Combien d’affrontements devront dispu-

ter chaque équipe ?
b) Combien d’affrontements seront disputés
au cours de ce week-end ?
A B

2. Cinq équipes. On note E la cinquième équipe engagée.

a) Représenter les rencontres du tournoi par un graphe de façon à ce que chaque équipe dispute quatre
affrontements.
b) Combien d’affrontements seront alors disputés ?

c) Pourquoi n’aurait-on pas pu organiser le tournoi de manière à ce que chaque équipe ne joue que trois
affrontements ?

3. Les deux graphes précédents sont-ils complets ?

4. Six équipes. On note F la sixième équipe engagée.

a) Représenter les rencontres du tournoi par un graphe de façon à ce que chaque équipe dispute trois affron-
tements.
b) Ce graphe est-il complet ?

c) Combien d’affrontements seront alors disputés ?

5. Sept équipes. On note H la septième équipe engagée.

a) Est-il possible d’organiser le tournoi de telle façon que chaque équipe dispute exactement quatre affronte-
ments ? Cinq ?

b) Représenter une telle situation par un graphe lorsque c’est possible. Combien d’affrontements seront alors
disputés ?

c) Chaîne Eulérienne
Définition

Hormis la longueur, les termes définis ci-dessous ne seront valables que pour un graphe non orienté.
• Une chaîne est une liste ordonnée d’arêtes telles que l’extrémité d’une arête soit l’origine de la suivante (sauf
pour la première et la dernière). On note une chaîne avec les sommets rencontrés successivement, séparés par
des tirets.
• La longueur d’une chaîne est le nombre d’arêtes la constituant.
• Une chaîne fermée est une chaîne dont l’origine de la première arête et l’extrémité de la dernière sont le même
sommet.

• Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes.

Laboratoire de Maths du lycée Roland-Garros à LA REUNION

 1.. GRAPHES NON ORIENTÉS p V-5

Exercice 5 : reconnaître une chaîne, une chaîne fermée et un cycle

En guise d’explications

On s’intéresse au problème suivant : pour un graphe donné, peut-on déterminer une chaîne passant une et une seule
fois par toutes les arêtes (on pourrait alors tracer le graphe sans lever le crayon et sans repasser sur un trait) ?
Si oui, est-il possible de trouver un cycle passant par toutes les arêtes (c’est-à-dire qu’on passe une seule fois par toutes
les arêtes, et que le sommet d’origine est le sommet d’arrivée) ?
La résolution de ce type de problème se ramène à l’étude des degrés des sommets. En lien avec ces questions, on
définit :

Définition

• Une chaîne eulérienne est une chaîne contenant chaque arête du graphe une et une seule fois.

• Un cycle eulérien est un cycle contenant chaque arête du graphe une et une seule fois.

Exercice 6 : reconnaître une chaîne eulérienne et un cycle eulérien

Laboratoire de Maths du lycée Roland-Garros à LA REUNION

p V-6 Chap. V

Recherche

Exercice 7 : Pour chacun des graphes suivants, compléter le tableau des degrés des sommets, et déterminer s’il
existe une chaîne eulérienne, puis s’il existe un cycle eulérien.

1. 2.
D C D C

E E

A B A B

Sommet A B C D E Sommet A B C D E
Degré Degré

3. 4.
D C D C

E E

A B A B

Sommet A B C D E Sommet A B C D E
Degré Degré

5.
D C

F E

A B

Sommet A B C D E F
Degré

Laboratoire de Maths du lycée Roland-Garros à LA REUNION

 1.. GRAPHES NON ORIENTÉS p V-7

En guise d’explications

Voici un raisonnement qui permit à Leonhard Euler d’obtenir une condition nécessaire à l’existence d’une chaîne
eulérienne (ce nom leur fut donné en hommage) :
On considère une chaîne eulérienne ; pour celle-ci, on s’intéresse à la liste ordonnée des sommets rencontrés (comme
on peut passer plusieurs fois par le même sommet, on peut trouver le même sommet à plusieurs reprises dans la liste).
On efface les noms du premier et du dernier sommet de la liste : on obtient la liste des « sommets intermédiaires ».
Parcourons la chaîne eulérienne : chaque fois qu’on arrive à un sommet intermédiaire X, on supprime l’arête menant
à ce sommet X. Comme les arêtes de la chaîne eulérienne sont toutes distinctes, on ne peut pas passer par une arête
déjà empruntée ; ainsi à chaque sommet, on supprimera une arête.
Et au sommet Y suivant le sommet intermédiaire X , on supprimera une nouvelle arête joignant X : le passage par
chaque point intermédiaire X conduit à effacer deux arêtes ayant le sommet X pour extrémité.
E C
Exemple : Dans le graphe suivant, A-B-C-D-
E-B-F-G-E-A-G est une chaîne eulérienne. A B D
La liste des points intermédiaires est
[B ;C ;D ;E ;B :F :G ;E ;A]. F
G

E C E C E C E C

A B D A B D A B D A B D

F F F F
G G G G

[ B ;C ;D ;E ;B ; [B ; C ;D ;E ;B ; [B ;C ; D ;E ;B ; [B ;C ;D ; E ;B ;
F ;G ;E ;A] F ;G ;E ;A] F ;G ;E ;A] F ;G ;E ;A]

Si, en parcourant la chaîne, on repasse par un point intermédiaire déjà rencontré, d’après l’explication précédente, on
supprimera deux nouvelles arêtes joignant ce sommet.

E C E C E C E C E C

A B D A B D A B D A B D A B D

F F F F F
G G G G G

[B ;C ;D ;E ; B ; [B ;C ;D ;E ;B ; [B ;C ;D ;E ;B ; [B ;C ;D ;E ;B ; [B ;C ;D ;E ;B ;
F ;G ;E ;A] F ;G ;E ;A] F ; G ;E ;A] F ;G ; E ;A] F ;G ;E ; A ]

A l’arrivée au dernier point intermédiaire, on a supprimé l’arête qui y mène. Mais il reste une dernière arête, celle
qui relie ce point intermédiaire au point d’arrivée : en supprimant celle-ci, on aura effacé deux arêtes ayant le dernier
point intermédiaire comme extrémité.
Ceci justifie que pour chaque point intermédiaire, après avoir parcouru la chaîne, on a supprimé un nombre pair
d’arêtes.
Existe-t-il une arête qui rejoint un de ces points intermédiaires, et qui n’aurait pas été supprimée ?
Non, car par définition de la chaîne eulérienne, celle-ci contient toutes les arêtes du graphe. Après avoir parcouru la
chaîne eulérienne, toutes les arêtes ont été supprimées.
Ainsi le nombre d’arêtes ayant pour extrémité un des sommets intermédiaires, c’est-à-dire le degré de ce point inter-
médiaire, est un nombre pair : voici la condition nécessaire à l’existence d’une chaîne eulérienne.
Si cette chaîne eulérienne est un cycle eulérien, alors le sommet d’origine et d’arrivée est également d’ordre pair, car
il est atteint par la première et la dernière arête supprimées.

Laboratoire de Maths du lycée Roland-Garros à LA REUNION

 p V-8 Chap. V

Propriété ▶ Théorème d’Euler (Admis)

Dans un graphe non-orienté, un graphe connexe admet une chaîne eulérienne si et seulement si le nombre de sommets
de degré impair vaut 0 ou 2.

Conséquences :

• Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
• Si le graphe connexe a deux sommets de degré impair, ce sont les extrémité de la chaîne eulérienne.
• Un graphe qui a plus de deux sommets de degré impair ne possède pas de chaîne eulérienne.

Recherche

Exercice 8 : Le problème suivant a été résolu par Euler : la ville de Koenigsberg, ancienne capitale de la Prusse-
Orientale et actuellement capitale de l’enclave russe de Kaliningrad, possède sept ponts reliant les quatre quartiers A,
B, C et D de la ville, comme illustré sur le dessin ci-dessous :

Est-il possible, à partir d’un des quartiers de la ville, de passer par tous les ponts une et une seule fois ?

2. Graphes orientés
A titre d’exemple

Une exposition est organisée dans un parc, et répartie entre plusieurs secteurs représentés par des lettres. On décide
d’y instaurer un plan de circulation : certaines allées sont à sens unique, d’autres sont à double sens. Voici le descriptif :
B
• Sens unique de A vers B ;
• double-sens entre B et C ;

• double-sens entre C et D ; Compléter le schéma,

selon les descriptions A
• sens unique de B vers D ; précédentes.
• double-sens entre D et E ;
• double-sens entre A et E. E

Définition

• Un graphe orienté d’ordre n est un ensemble de n sommets reliés entre eux par des flèches nommées arcs. Un
sommet peut être relié à lui-même par une boucle.
• Le degré d’un sommet est le nombre d’extrémités et d’origines d’arcs parvenant à ce sommet.

Laboratoire de Maths du lycée Roland-Garros à LA REUNION

 3.. MATRICE D’ADJACENCE p V-9

• Un chemin est une liste ordonnée d’arcs tels que l’extrémité d’un arc soit l’origine du suivant (sauf pour le
premier et le dernier). On note un chemin avec les sommets rencontrés successivement, séparés par des tirets.

• La longueur d’un chemin est le nombre d’arcs le constituant.

• Un chemin fermé est un chemin dont l’origine du premier arc et l’extrémité du dernier sont le même sommet.
• Un circuit est un chemin fermé dont tous les arcs sont distincts.

Propriété

On retrouve la même propriété sur le lien degré-nombre d’arcs que pour les graphes non orientés :
Dans un graphe orienté, la somme des degrés de tous les sommets est égale au double du nombre d’arcs.

Recherche

Exercice 9 : On considère le graphe orienté ci-dessous :

G B

1. Déterminer l’ordre du graphe, ainsi que le degré de

chaque sommet.

F
A
C
2. En déduire par un calcul le nombre d’arcs de ce
graphe.

3. Déterminer un chemin de longueur 5 reliant G à C.

4. Déterminer un circuit d’origine A.
E
D

3. Matrice d’adjacence
a) Définition
A titre d’exemple

On travaillera ici sur les exemples introductifs des parties précédentes.

1. On veut modéliser le réseau ferroviaire à l’aide d’une matrice. Pour cela, on va d’abord ordonner de manière
arbitraire les sommets : on choisira B ; L ; M ; N ; P ; R ; S .
La première ligne représentera les liaisons ferroviaires avec Bordeaux : on écrit 1 s’il existe une ligne entre
Bordeaux et une ville de la liste ordonnée, 0 sinon. On obtient :

B L M N P R S
B ( 0 0 1 1 0 1 0 )
Procéder ainsi en rajoutant les lignes correspondant aux autres villes ; on note M la matrice obtenue.
2. On veut modéliser le plan de circulation du parc à l’aide d’une matrice. Pour cela, on va d’abord ordonner de
manière arbitraire les sommets : on choisira A ; B ; C ; D ; E .
La première ligne représentera les allées ayant pour origine A : on écrit 1 s’il existe une allée menant de A vers
un secteur du parc, 0 sinon. On obtient :

A B C D E
A ( 0 1 0 0 1 )
Procéder ainsi en rajoutant les lignes correspondant aux autres secteurs ; on note N la matrice obtenue.

Les matrices M et N sont les matrices d’adjacence associées aux graphes.

Laboratoire de Maths du lycée Roland-Garros à LA REUNION

p V-10 Chap. V

3. a) Pour le réseau ferroviaire, compléter le tableau ci-dessous avec les nombres de chaînes de longueur 2 menant
de B vers les autres sommets.
B L M N P R S
nombre de chaînes
de longueur 2
à partir de B

b) Calculer M 2 .

4. a) Pour le parc d’exposition, compléter les tableaux ci-dessous avec les nombres de chemins de longueur 3
menant de A vers les autres secteurs, puis menant de B vers les autres secteurs.
A B C D E A B C D E
nombre de chemins nombre de chemins
de longueur 3 de longueur 3
à partir de A à partir de B

b) Calculer N 3 .

On peut ainsi conjecturer une propriété remarquable des puissances des matrices d’adjacence d’un graphe.

Définition

On considère un graphe d’ordre n, orienté (ou non). On ordonne ses n sommets, en leur attribuant un numéro entre
1 et n.
2
Pour tout couple (i, j) ∈ J1; nK , on attribue la valeur 1 au coefficient mi,j s’il existe un arc (ou une arête) d’origine
le sommet i et d’extrémité le sommet j ; sinon, on attribue la valeur 0 au coefficient mi,j .
La matrice M = (mi,j )1⩽i⩽n,1⩽j⩽n , matrice carrée d’ordre n, est la matrice d’adjacence associée au graphe.
On peut remarquer que la matrice d’adjacence d’un graphe non orienté est symétrique par rapport à la diagonale
« haut gauche - bas droit », car on a toujours mi,j = mj,i .

Propriété

On se place ici dans le cas d’un graphe simple : il existe au plus une arête ou un arc reliant un sommet à un autre.
On considère un graphe d’ordre n, orienté (ou non), et sa matrice d’adjacence M = (mi,j ).
(k)
Pour tout entier k > 0, on note mi,j le coefficient d’indice (i, j) de la matrice M k .
(k)
Attention, on n’a pas forcément mi,j = mi,j k .
(k)
Le coefficient mi,j de la matrice M k est le nombre de chemins (ou de chaînes) de longueur k partant du sommet
numéro i et arrivant au sommet numéro j.

Démonstration

On se place ici dans le cas d’un graphe simple

(k)
Nous allons démontrer ce résultat par récurrence sur k. Pour k ⩾ 1, on note P(k) la propriété : Le coefficient mi,j
de la matrice M k est le nombre de chemins (ou de chaînes) de longueur k partant du sommet numéro i et arrivant au
sommet numéro j.

• Initialisation : Pour k = 1, la propriété est vraie, c’est la définition de la matrice d’adjacence.

• Hérédité : Supposons qu’il existe un entier k ⩾ 1 pour lequel P(k) soit vraie ; montrons que P(k + 1) est vraie.
On s’intéresse aux chemins (ou aux chaînes) de longueur k + 1 reliant le sommet i au sommet j.

• Intéressons-nous à ces chemins (ou chaînes), où l’avant-dernier sommet rencontré avant le sommet j est le
sommet 1.

Laboratoire de Maths du lycée Roland-Garros à LA REUNION

 3.. MATRICE D’ADJACENCE p V-11

Pour un tel chemin (ou chaîne), on a un chemin (ou une chaîne) de longueur k reliant le sommet i au
(k)
sommet 1 : il y en a mi,1 , par hypothèse de récurrence. Il suffit de rajouter l’arc (ou l’arête) menant du
sommet 1 au sommet j : il y a 0 ou 1 , c’est le coefficient m1,j .
∗ Si m1,j = 0, il n’y a aucun chemin (ou chaîne) de longueur k + 1, où l’avant-dernier sommet rencontré
(k)
avant le sommet j est le sommet 1 : il y en a donc mi,1 × m1,j = 0.
(k)
∗ Sinon, m1,j = 1, il y a mi,1 = mi,1 × m1,j chemins (ou chaînes) de longueur k + 1, où l’avant-dernier
sommet rencontré avant le sommet j est le sommet 1.
• Intéressons-nous à ces chemins (ou chaînes) de longueur k + 1 reliant le sommet i au sommet j, où l’avant-
dernier sommet rencontré avant le sommet j est le sommet 2.
(k)
Par un raisonnement similaire au précédent, on obtient qu’il y en a mi,2 × m2,j .

• Intéressons-nous à ces chemins (ou chaînes) de longueur k + 1 reliant le sommet i au sommet j, où l’avant-
dernier sommet rencontré avant le sommet j est le sommet n.
(k)
Par un raisonnement similaire au précédent, on obtient qu’il y en a mi,n × mn,j .

(k) (k) (k)

• En conclusion, on a établi qu’il y a mi,1 × m1,j + mi,2 × m2,j + . . . + mi,n × mn,j chemins (ou chaînes) de
longueur k + 1 reliant le sommet i au sommet j.
Par définition du produit matriciel, ce résultat est égal au coefficient (i, j) de la matrice M k+1 , comme illustré
ci-dessous :

colonne j
de M
 
.. .. .. ..
. . m1,j . .
.. .. .. ..
. . m2,j . .
 
.. .. .. ..
. . m3,j . .
 
. .. .. .. ..
.. . . . .
 
.. .. .. ..
. . m . .
   n,j

... ... ... ... ...
 ... ... ... ... ...   
 (k)   
ligne i de M k m (k)
mi,2
(k)
mi,3 . . . mi,n 
(k)  (k+1)
mi,j 
 i,1   
 ... ... ... ... ...   
... ... ... ... ...

Ceci prouve l’hérédité.

La propriété a été initialisée au rang 1, et est héréditaire : elle est par conséquent vraie pour tout entier k ⩾ 1.

Laboratoire de Maths du lycée Roland-Garros à LA REUNION

p V-12 Chap. V

Recherche

Exercice 10 : Un guide de randonnée en montagne décrit les itinéraires possibles autour d’un pic rocheux.
La description des itinéraires est donnée par le graphe ci-contre. Les sommets de ce graphe correspondent aux lieux
remarquables. Les arêtes de ce graphe représentent les sentiers possibles entre ces lieux.

Ãb Èb

Légende :
À Départ Á Passerelle
 Roche percée à Col des 3 vents
b Ä
Ä Pic rouge Å Refuge DÀ b
b

Æ Col vert Ç Pont Napoléon Á b

Æ
b
È Cascade des anglais É Arrivée b
ÉA
Å
b
b Ç
Â

1. a) Dresser un tableau décrivant les degrés de chaque sommet du graphe.

b) En déduire le nombre d’arêtes de ce graphe.
2. Donner un itinéraire allant de D à A passant par tous les sommets du graphe une seule fois mais n’empruntant
pas forcément tous les sentiers.
3. Existe-t-il un itinéraire allant de D à A utilisant tous les sentiers une seule fois ?
Justifier votre réponse.

 
4. On note M la matrice d’adjacence associée à ce 56 78 75 82 59 57 54 40 26 31
graphe, les sommets étant pris dans l’ordre. On 78 88 95 89 96 57 50 65 48 30
75 
donne ci-contre M 5 .  95 68 68 77 68 46 73 52 23
82 13
 89 68 62 98 49 29 79 67 
a) Que représente le nombre 89 situé sur la 59 96 77 98 50 82 80 40 24 46
M =
5
57

deuxième ligne et la quatrième colonne ?  57 68 49 82 36 25 68 49 16
54 50 46 29 80 25 10 73 60 5
b) Déterminer le nombre d’itinéraires allant  
40 65 73 79 40 68 73 32 14 48
de D à A empruntant 5 sentiers. Citer un 26 48 52 67 24 49 60 14 6 39
tel itinéraire passant par le pic rouge. 31 30 23 13 46 16 5 48 39 2

Laboratoire de Maths du lycée Roland-Garros à LA REUNION

 3.. MATRICE D’ADJACENCE p V-13

Recherche

Exercice 11 :
D
Un parcours sportif est composé d’un banc pour abdomi- H

naux, de haies et d’anneaux. Le graphe orienté ci-contre

indique les différents parcours possibles depuis l’entrée D
du parcours jusqu’à sa sortie F.
B
Les sommets sont : D (départ), B (banc pour abdominaux),
A
H (haies), A (anneaux), et F (fin du parcours).
Les arcs représentent les différents sentiers reliant les som-
mets A, B, D, F, H.
F

1. Quel est l’ordre du graphe ?

2. Déterminer le degré de chaque sommet puis en déduire le nombre d’arêtes.

3. On note M la matrice d’adjacence de ce graphe où les sommets sont rangés dans l’ordre alphabétique.
a) Déterminer M.
 
0 0 0 0 0
0 0 0 0 0
 
b) On donne M = 
3
0 1 0 3 0

0 0 0 0 0
0 0 0 1 0
Assia souhaite aller de D à F en faisant un parcours constitué de trois sentiers. Est-ce possible ? Si oui,
combien de parcours différents peut-elle emprunter ? Préciser ces parcours.
4. Le responsable souhaite ajouter une barre de traction notée T. De nouveaux sentiers sont construits et de nou-
veaux parcours sont possibles. La matrice d’adjacence N associée au graphe représentant les nouveaux parcours,
dans lequel les sommets sont classés dans l’ordre alphabétique, est :
 
0 1 0 1 0 1
0 0 0 1 0 0
 
1 1 0 0 1 0
N=  .

0 0 0 0 0 0
1 1 0 1 0 1
0 0 0 1 0 0

Compléter le graphe orienté ci-dessous pour obtenir celui correspondant à la matrice N.

D
H

Laboratoire de Maths du lycée Roland-Garros à LA REUNION

p V-14 Chap. V

Recherche

Exercice 12 :
D

Une fourmi se promène de manière aléatoire le long des E

arêtes de ce solide. Elle part du sommet A, se déplace
le long d’une arête et chaque fois qu’elle arrive sur un B
sommet, la probabilité qu’elle s’engage sur une arête est la
F
même pour toutes les arêtes joignant ce sommet.
A
On pourra effectuer les calculs avec la calculatrice.

1. Construire un graphe représentant la situation.

2. Est-il envisageable que la fourmi, en partant du sommet A, emprunte une et une seule fois chaque arête ?
Justifier. Le cas échéant, donner son parcours.

3. Donner la matrice d’adjacence M associée au graphe, puis donner M2 . Sans rien écrire sur votre copie, vérifier
la justesse de vos calculs en remarquant que :
 
8 12 12 12 8 12
12 8 12 12 12 8
 
12 12 8 8 12 12
M3 = 12 12
.
 8 8 12 12
 8 12 12 12 8 12
12 8 12 12 12 8

4. Donner le nombre de chaînes fermées (même sommet de départ et d’arrivée) de longueur 8 partant du sommet A.

5. Déterminer le nombre total de chaînes de longueur 8 partant de A.

6. Quelle est la probabilité que la fourmi se retrouve au sommet A après huit déplacements ?

7. Quelle est la probabilité que la fourmi se retrouve au sommet A après huit déplacements, sachant qu’après 3
déplacements elle s’est retrouvée en B ?

Laboratoire de Maths du lycée Roland-Garros à LA REUNION