Graphe et itinéraires de pistes cyclables

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2015 | Académie : Antilles, Guyane


Antilles, Guyane • Septembre 2015

Exercice 2 • 5 points

Graphe et itinéraires de pistes cyclables

Un cycliste désire visiter plusieurs villages notés A, B, C, D, E, F et G reliés entre eux par un réseau de pistes cyclables.

Le graphe suivant schématise son plan ; les arêtes représentent les pistes cyclables et les distances sont en kilomètre.

matT_1509_04_00C_02

partie a

Pour faire son parcours, le cycliste décide qu’il procédera selon l’algorithme ci-dessous :

ligne 1

Marquer sur le plan tous les villages comme non « visités »

ligne 2

Choisir un village de départ

ligne 3

Visiter le village et le marquer « visité »

ligne 4

Rouler vers le village le plus proche

ligne 5

Tant que le village où il arrive n’est pas un village déjà visité

ligne 6

ligne 7

visiter le village et le marquer « visité »

rouler vers le village le plus proche sans revenir en arrière

ligne 8

Fin Tant que

ligne 9

Afficher la liste des villages visités

1. Quelle propriété du graphe permet à la ligne 4 d’être toujours exécutable ? (0,5 point)

2. En partant du village noté G, quelle sera la liste des villages visités ? (0,5 point)

3. Existe-t-il un village de départ qui permette, en suivant cet algorithme, de visiter tous les villages ? (1 point)

4. Le cycliste abandonne l’idée de suivre l’algorithme. Il souhaite maintenant, partant d’un village, y revenir après avoir emprunté toutes les pistes cyclables une et une seule fois. Cela sera-t-il possible ? (1 point)

partie b

1. Écrire la matrice M de transition de ce graphe (dans l’ordre A, B, C, … , G). (1 point)

2. On donne la matrice M4 :

ABCDEFGM4=ABCDEFG(1059114116530122318161691212149418112314281411234189141291211641191051616182312530)

Interpréter le terme en gras, ligne A, colonne F (valant 1) dans le contexte de l’exercice. (1 point)

Les clés du sujet

Durée conseillée : 45 minutes

Les thèmes en jeu

Boucle avec arrêt conditionnel « Tant que » • Matrice • Graphe pondéré • Chaîne de longueur donnée • Chaîne eulérienne • Plus court chemin.

Les conseils du correcteur

Partie A

1. Justifiez et utilisez la connexité du graphe.

4. Utilisez le théorème d’Euler.

Partie B

2. Les coefficients de M4 donnent le nombre de chaînes de longueur 4 entre deux sommets.

Corrigé

Corrigé

partie a

1. Reconnaître et utiliser une propriété d’un graphe

Le graphe est connexe, donc à partir d’un village donné, il est toujours possible d’atteindre au moins un autre village.

Donc la ligne 4 du graphe est donc toujours exécutable.

2. Déterminer sur un graphe un trajet déterminé par un algorithme

En partant du village noté G et en suivant l’algorithme, le trajet du cycliste peut être décrit de la manière suivante :

de G, il va en B, qui est le village le plus proche ;

de B, il va en A car il ne peut pas revenir en G ;

de A, il va en F car il ne peut pas revenir en B ;

de F, il ne peut aller qu’en G car il ne peut pas revenir en arrière ;

dans l’exécution de l’algorithme, on sort alors de la boucle « Tant que » car le cycliste arrive dans un village déjà visité.

En suivant l’algorithme proposé et en partant du village noté G, la liste des villages successivement visités sera donc :

GBAFG.

3. Déterminer un trajet passant par tous les sommets d’un graphe

On examine successivement tous les « points de départ » possibles d’un trajet déterminé en suivant l’algorithme.

Partant de A, le « circuit » serait :

A – B – G – E – D – G ;

partant de B : B – G – E – D – G ;

partant de C : C – D – E – G – B – A – F – G ;

partant de D : D – E – G – B – A – F – G ;

partant de E : E – D – G – B – A – F – G ;

partant de F : F – G – B – A – F ;

le cas du trajet partant de G a été étudié à la question précédente.

Il est possible, en suivant l’algorithme, de visiter tous les villages : il suffit de partir de C.

4. Déterminer si un graphe possède un cycle eulérien

Déterminer s’il existe un trajet partant d’un village et y revenant après avoir emprunté toutes les pistes cyclables une et une seule fois revient à déterminer si le graphe possède un cycle eulérien.

D’après le théorème d’Euler, un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.

On a vu précédemment que la chaîne C – D – E – G – B – A – F contient tous les sommets du graphe, donc ce graphe est connexe. On peut résumer dans un tableau le degré de ses sommets :

Sommet

A

B

C

D

E

F

G

Degré

2

4

2

4

2

2

4

Tous les sommets sont de degré pair ; d’après le théorème d’Euler, le graphe admet un cycle eulérien.

Il existe donc un trajet partant d’un village et y revenant après avoir emprunté toutes les pistes cyclables une et une seule fois.

partie B

1. Écrire la matrice de transition d’un graphe

La matrice de transition M du graphe donné est :

M=(0100010101100101010000110101000100110000010101110).

2. Interpréter un coefficient d’une puissance de la matrice de transition d’un graphe

Le terme (valant 1) situé ligne A, colonne F de la matrice M4 est le nombre de chaînes de longueur 4 (c’est-à-dire formées de 4 arêtes) entre A et F.

Il existe donc une seule chaîne de longueur 4 entre le village A et le village F :

A – B – D – G – F.