Exercice 3 - Graphes · Bac Numérique et Sciences Informatiques Métropole 2026 (sujet 2)

Partie B

Alice, Maxime, Valérie et Clément doivent choisir un point de rendez-vous pour leur trajet de covoiturage. Ils ont identifié trois points de rendez-vous possibles. Dans le graphe suivant:

les sommets A, M, C, et V représentent les domiciles des quatre covoitureurs;

les sommets P1, P2, et P3 représentent les points de rendez-vous possibles;

les arêtes représentent des trajets entre ces lieux qui possèdent tous approximativement les mêmes conditions de parcours (distance et durée).

On utilise la fonction dico_distance donnée ci-après pour déterminer toutes les distances en nombre d'arêtes entre un point de rendez-vous et les autres sommets du graphe.

1 def dico_distance(graphe, depart):

2 """ graphe: dictionnaire

3 {sommet: liste de sommets adjacents }

4 depart: un sommet du graphe

5 renvoie un dictionnaire

6 {sommet atteignable depuis depart:

7 distance entre depart et ce sommet }"""

8

9 # initialisation d'une file

10 file = File()

11 file.inserer(depart)

12

13 # initialisation du dictionnaire de sortie

14 dico = {depart: 0}

15

16 while not file.est_vide():

17 # extraire le prochain sommet à explorer

18 sommet = file.extraire()

19 # pour chaque voisin encore non atteint

20 for voisin in graphe[sommet]:

21 if voisin not in dico:

22 # attribuer la distance à ce voisin

23 dico[voisin] = dico[sommet] + 1

24 # placer ce voisin dans la file

25 # pour une exploration future

26 file.inserer(voisin)

27 return dico La fonction dico_distance utilise une file pour gérer l'ordre d'exploration des sommets du graphe. Cette file est implémentée avec une classe File. En tapant la commande help(File) dans la console de Python on obtient:

class File(builtins.object)

| Methods defined here:

|

| __init__(self)

| initialise une file vide

|

| consulter(self)

| renvoie le premier élément disponible

| sans le retirer de la file

| lève une exception IndexError si la file est vide

|

| est_vide(self)

| renvoie True si la file est vide, False sinon

|

| extraire(self)

| renvoie le premier élément disponible et

| le retire de la file

| lève une exception IndexError si la file est vide

|

| inserer(self, element)

| ajoute l'élément donné dans la file

9.

Écrire un dictionnaire Python représentant le graphe de la Figure 2. Ce dictionnaire doit associer à chaque sommet la liste de ses sommets voisins.

12.

Donner le nom du type de parcours de graphe, utilisé dans la fonction dico_distance.

13.

On définit l'excentricité d'un sommet dans un graphe comme la plus grande distance parmi les distances entre ce sommet et un autre sommet quelconque du graphe.

Recopier et compléter la fonction excentricite suivante qui calcule l'excentricité d'un sommet dans un graphe. L'utilisation de la fonction max, disponible sans importation, n'est pas autorisée.

def excentricite(graphe, sommet):

""" graphe: dictionnaire

{sommet: liste de sommets adjacents }

renvoie l'excentricité de sommet

dans le graphe (int) """

dico = dico_distance(graphe, sommet)

...

...

...

...

...

14.

Donner, en le justifiant avec un indicateur, le meilleur point de rendez-vous pour ces quatre personnes (Alice, Maxime, Valérie et Clément).