EXO-Mat-Dji - 3
EXO-Mat-Dji - 3
EXO-Mat-Dji - 3
FEUILLE D’EXERCICES
MATRICES-GRAPHES PONDÉRÉS
Exercice 1
Un journaliste britannique d’une revue consacrée à l’automobile doit tester les autoroutes françaises.
Pour remplir sa mission, il décide de louer une voiture et de circuler entre six grandes villes françaises : Bordeaux (B),
Lyon (L), Marseille (M), Nantes (N), Paris (P) et Toulouse(T).
Le réseau autoroutier reliant ces six villes est modélisé par le graphe ci-dessous sur lequel les sommets représentent
les villes et les arêtes les liaisons autoroutières entre ces villes.
L
M
B T
Partie A
1
2023-2024 Théorie des graphes MATHS EXPERTES
Partie B
On a indiqué sur le graphe ci-dessous le temps nécessaire en minutes pour parcourir chacune des liaisons autoroutières.
268
391
222
214
340 L
M
396
305
N 236
206 336
B T
153
Exercice 2
Le graphe ci-dessous représente le plan d’un centre de vacances. Les arêtes représentent les allées et les sommets, les
carrefours. On a indiqué sur chaque arête la longueur en mètre des allées entre deux carrefours.
B 50 D
75 103
42 80
A 30 F G
40
110 93
72
C E
1. Le service d’entretien doit nettoyer toutes les allées. En partant du carrefour C, peut-on nettoyer toutes les
allées en passant une et une seule fois par chacune d’elles ? Justifier la réponse.
2. Existe-t-il un parcours permettant de nettoyer toutes les allées en passant une et une seule fois par chacune
d’elles et de revenir au point de départ ? Justifier la réponse.
3. Déterminer le trajet le plus court pour aller du carrefour A au carrefour G.
2
2023-2024 Théorie des graphes MATHS EXPERTES
Exercice 3
Le graphe ci-dessous représente les autoroutes entre les principales villes du Sud de la France :
Bordeaux (B), Clermont-Ferrand (C), Lyon (L), Marseille (M), Montpellier (P), Brive (R), Toulouse (T), Valence (V)
et Biarritz (Z).
L
R
C
B
V
M
Z
P
T
Sommets B C L M P R T V Z
Degrés
Exercice 4
Deux amis, Louisa et Antoine, passent la journée dans un parc d’attraction.
Le plan du parc est donné par le graphe Γ ci-après. Les arêtes de ce graphe représentent les allées du parc et les
sommets correspondent aux intersections de ces allées. On a pondéré les arêtes de ce graphe par les temps de parcours
en minutes.
3
2023-2024 Théorie des graphes MATHS EXPERTES
N
8
8
J
7
F
4
3
6
4
M
8
G K
5 1
6
2 L
3
5
4
E 6 H 7 I
(b) Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant F à L. Préciser ces chemins.
(c) Déterminer, en justifiant, le nombre de chemins de longueur 3 partant de E.
(d) Que signifie le coefficient à l’intersection de la première ligne et de la troisième colonne de S ?
4. Un défilé part tous les jours à 14 h du sommet N. Louisa et Antoine choisissent de déjeuner dans un restaurant
situé au sommet E avant d’aller admirer le défilé.
(a) À l’aide d’un algorithme, déterminer le chemin que doivent emprunter Louisa et Antoine pour se rendre
du restaurant au départ du défilé le plus rapidement.
(b) À quelle heure au plus tard doivent-ils quitter le restaurant pour assister au début du défilé ?