Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

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 :

modélisation à l'aide d'un graphe

Les sommets du graphe (G) représentent les carrefours et les arêtes du graphe schématisent les routes reliant ces carrefours.

On pondère le graphe (G) par les longueurs, en centaines de mètres, de chacune des routes :

 graphe pondéré

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 :

    M=(010010101111010100011011110101010110) M = \begin{pmatrix} 0 &1 &0 &0 &1 &0 \\ 1 &0 &1 &1 &1 &1 \\ 0 &1 &0 &1 &0 &0 \\ 0 &1 &1 &0 &1 &1 \\ 1 &1 &0 &1 &0 &1\\ 0 &1 &0 &1 &1 &0 \end{pmatrix}

    Pour obtenir le nombre de chemins de trois routes reliant deux sommets on calcule M3M^3.

    À la calculatrice, on trouve :

    M3=(283574810811111138275451178119711511894114996) M^3 = \begin{pmatrix} 2 &8 &3 &5 &7 &4 \\ 8 &10 &8 &11 &11 &11 \\ 3 &8 &2 &7 &5 &4 \\ 5 &11 &7 &8 &11 &9 \\ 7 &11 &5 &11 &8 &9\\ 4 &11 &4 &9 &9 &6 \end{pmatrix}

    Le nombre de chemins de trois routes, reliant C à E, est le coefficient de M3M^3 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 MM 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 MnM^n situé à la ii-ème ligne et à la jj-ème colonne indique le nombre de chemins de longueur nn menant du sommet numéro ii au sommet numéro jj.

  • 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 :

    algorithme de Dijkstra

    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.