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.

Pour lire la suite :