Graphes - Bac blanc ES/L Sujet 3 - Maths-cours 2018 (spé)
Exercice 3 (5 points)
Candidats ayant suivi l'enseignement de spécialité
Pour chacune des cinq affirmations suivantes, indiquer si elle est vraie ou fausse en justifiant la réponse.
Il est attribué un point par réponse exacte correctement justifiée.
Une réponse non justifiée n'est pas prise en compte.
On modélise le plan d'un village à l'aide du graphe (G) ci-dessous :
Les sommets du graphe (G) représentent les carrefours et les arêtes du graphe schématisent les routes reliant ces carrefours.
Affirmation 1 : Le graphe (G) est connexe.
Affirmation 2 : Le graphe (G) contient un sous-graphe complet d'ordre 4.
Affirmation 3 : Une personne peut parcourir toutes les routes du village sans emprunter plusieurs fois la même route.
Affirmation 4 : Il y a exactement 5 trajets de trois routes reliant les carrefours C et E.
On pourra utiliser la calculatrice pour justifier la réponse à l'aide d'un calcul matriciel.
On pondère le graphe (G) par les longueurs, en centaines de mètres, de chacune des routes :
Affirmation 5 : Le plus court chemin menant de A à D mesure 700 mètres .
On justifiera la réponse à l'aide d'un algorithme.
Corrigé
Affirmation 1 : Le graphe (G) est connexe : EXACT.
Un graphe est connexe si et seulement si on peut relier deux quelconques de ses sommets par une chaîne.
C'est bien le cas ici donc le graphe (G) est connexe.
Affirmation 2 : Le graphe (G) contient un sous-graphe complet d'ordre 4 : EXACT.
Considérons le sous-graphe d'ordre 4 composé des sommets B, D, E et F. Chacun de ces sommets est relié aux trois autres.
Ce sous-graphe est donc complet.Affirmation 3 : Une personne peut parcourir toutes les routes du village sans emprunter plusieurs fois la même route : EXACT.
La question revient à déterminer s'il existe une chaîne qui contient une fois et une seule chacune des arêtes du graphe c'est à dire une chaîne eulérienne.
Or, d'après le théorème d'Euler, un graphe connexe contient une chaîne eulérienne si et seulement s'il possède 0 ou 2 sommets de degré impair.
Le tableau ci-après recense le degré de chacun des sommets :
Sommet A B C D E F Degré 2 5 2 4 4 3 Le graphe (G) possède deux sommets de degré impair : B et F. Il existe donc au moins un trajet qui emprunte une fois et une seule chacune des routes du graphe.
Ces trajets ont nécessairement comme extrémités B et F ; par exemple : B-C-D-E-A-B-E-F-D-B-F.Affirmation 4 : Il y a exactement 5 trajets de trois routes reliant les carrefours C et E: EXACT.
La matrice de transition du graphe (G) obtenue en classant les sommets par ordre alphabétique est :
Pour obtenir le nombre de chemins de trois routes reliant deux sommets on calcule .
À la calculatrice, on trouve :
Le nombre de chemins de trois routes, reliant C à E, est le coefficient de situé sur la troisième ligne (correspondant au sommet de départ C) et la cinquième colonne (correspondant au sommet d'arrivé E).
Il y a donc bien 5 trajets de trois routes reliant les carrefours C et E.
En pratique
Soit la matrice de transition d'un graphe G. Pour déterminer le nombre de chemins de longueur \bm{n} reliant deux sommets du graphe on calcule \bm{M^n}.
Le coefficient de la matrice situé à la -ème ligne et à la -ème colonne indique le nombre de chemins de longueur menant du sommet numéro au sommet numéro .
Affirmation 5 : Le plus court chemin menant de A à D mesure 700 mètres : FAUX.
On utilise l'algorithme de Dijkstra en partant de A :
Le trajet le plus court menant de A à D mesure 6 centaines de mètres soit 600 mètres.
Il s'agit du trajet A-B-F-D.
Pour plus de détails sur la méthode employée dans cette question se reporter à la fiche consacrée à l'algorithme de Dijkstra.