Exercice 1 - Graphes · Bac Numérique et Sciences Informatiques Polynésie 2024 (jour 2)

EXERCICE 1 (6 points)

Cet exercice porte sur les structures de données FILE et PILE, les graphes et les algorithmes de parcours.

Partie A

Une agence de voyages organise différentes excursions dans une région de France et propose la visite de certaines villes. Ces excursions peuvent être visualisées sur le graphe ci-dessous: les sommets désignent les villes, les arêtes représentent les routes pouvant être empruntées pour relier deux villes et les poids des arêtes représentent des distances, exprimées en kilomètre.

1.

Déterminer le plus court chemin allant du sommet Mp au sommet Nc et préciser la longueur, en kilomètres, de ce chemin. Aucune justification n’est attendue.

km

2.

On souhaite toujours se rendre du sommet Mp au sommet Nc mais en visitant le minimum de villes. Déterminer les deux chemins possibles.

Partie B

L'agence souhaite proposer un itinéraire permettant de visiter toutes les villes. On appelle G le graphe non pondéré ci-dessous.

On choisit d'implémenter un graphe par listes d'adjacence, à l'aide d'un dictionnaire, en langage Python, dont:

les clés sont les sommets du graphe;

la valeur associée à une clé est la liste des voisins de ce sommet clé.

Les sommets sont de type str.

3.

Donner l'implémentation, en langage Python, du graphe de la figure 2. Le dictionnaire obtenu sera stocké dans une variable nommée G. Afin de faciliter la notation manuscrite ainsi que la lisibilité, écrire chaque couple clé/valeur sur une nouvelle ligne.

Voici, en langage Python, les opérations pouvant être effectuées sur une file:

creerFile(): renvoie une file vide;

estVide(F): renvoie True si la file F est vide et False sinon;

enfiler(F, e): ajoute l'élément e dans la file F;

defiler(F): renvoie l'élément à la tête de la file F en le retirant de la file F.

On donne la fonction parcours ci-dessous:

def parcours(graphe, sommet):

f = creerFile()

enfiler(f, sommet)

visite = [sommet]

while not estVide(f):

s = defiler(f)

for v in graphe[s]:

if not (v in visite):

visite.append(v)

enfiler(f, v)

return visite

6.

Donner le résultat renvoyé par l'appel parcours(G, 'Av') (selon votre implémentation de G).

7.

Parmi les deux propositions ci-dessous, sélectionner celle qui correspond au type de parcours de graphe réalisé par la fonction parcours:

A

Proposition A: parcours en largeur

B

Proposition B: parcours en profondeur

Dans la suite de l'exercice, la distance entre deux sommets désignera le nombre d'arêtes séparant ces deux sommets. Ainsi définie, la distance entre les sommets Mp et Nc du graphe de la figure 2 est 3.

8.

En modifiant la fonction parcours, écrire une fonction distance ayant pour paramètres graphe, un dictionnaire représentant un graphe sous la forme de listes d'adjacence, et une chaîne de caractères sommet représentant un sommet du graphe. Cette fonction renvoie un dictionnaire associant à chaque sommet du graphe sa distance au sommet d'origine sommet.

9.

Donner le résultat renvoyé par l'appel distance(G, 'Av').

On considère une pile. Voici, en langage Python, les opérations pouvant être effectuées sur une telle pile:

creerPile(): renvoie une pile vide;

estVide(P): renvoie True si la pile P est vide et False sinon;

empiler(P, e): ajoute l'élément e au sommet de la pile P;

depiler(P): renvoie le sommet de la pile P en le retirant de la pile P.

On donne, ci-dessous, le pseudo-code d'un algorithme de parcours d'un graphe G à partir d'un sommet s (avec la correction d'erratum: la ligne 3 crée une liste visite vide):

1 créer une pile p

2 empiler s dans p

3 créer une liste visite vide

4 tant que p n'est pas vide

5 x = depiler p

6 si x n'est pas dans la liste visite

7 ajouter x à la liste visite

8 pour chaque voisin v de x

9 empiler v dans p

10 fin pour

11 fin si

12 fin tant que

13 renvoyer visite

10.

Traduire, dans le corps d'une fonction Python nommée parcours2, l'algorithme en pseudo-code donné précédemment. Cette fonction prendra pour paramètres G, un dictionnaire représentant un graphe sous la forme de listes d'adjacence, et une chaîne de caractères s représentant un sommet du graphe.

11.

Donner un résultat possible renvoyé par l'appel parcours2(G, 'Av').