Exercice 2 - Graphes · Bac Numérique et Sciences Informatiques Antilles-Guyane 2026 (jour 2)

Exercice 2 (6 points)

Cet exercice porte sur les protocoles de routage et les graphes.

Partie A

Un réseau informatique, composé de six routeurs et des liens reliant ces routeurs, est représenté ci-dessous. Le coût d'un lien est inversement proportionnel au débit de la liaison. Ces coûts sont indiqués au-dessus des liaisons et les adresses IP des sous-réseaux sont indiquées en dessous. Le "/24" situé à la suite des adresses IP des sous-réseaux signifie que les identifiants réseaux sont codés sur 24 bits.

Le tableau ci-dessous donne les adresses IP des routeurs selon leurs liaisons aux différents sous-réseaux.

Adresse du sous-réseau · Adresses IP des routeurs

192.168.1.0/24 · R1 · 192.168.1.1 · R2 · 192.168.1.4

10.1.1.0/24 · R2 · 10.1.1.1 · R3 · 10.1.1.2

192.168.4.0/24 · R2 · 192.168.4.2 · R6 · 192.168.4.1

10.1.6.0/24 · R3 · 10.1.6.1 · R4 · 10.1.6.2

10.2.6.0/24 · R4 · 10.2.6.1 · R5 · 10.2.6.2

192.168.2.0/24 · R4 · 192.168.2.2 · R6 · 192.168.2.1

10.2.7.0/24 · R5 · 10.2.7.3 · R6 · 10.2.7.1

Le tableau suivant présente les adresses IP configurées sur chaque routeur suite à la mise à jour du réseau informatique:

7.

Représenter le réseau informatique mis à jour à l'aide d'un graphe.

Partie B

Un réseau routier, composé de six villes, est représenté ci-dessous.

Le réseau, modélisé par un graphe, est implémenté dans la suite par un dictionnaire de listes d'adjacence où chaque sommet du graphe est associé à la liste de ses voisins. Le réseau routier de la figure 2 est donc implémenté de la façon suivante:

route = {

'V1': ['V2'],

'V2': ['V1', 'V3', 'V6'],

'V3': ['V2', 'V4'],

'V4': ['V3', 'V5', 'V6'],

'V5': ['V4', 'V6'],

'V6': ['V2', 'V4', 'V5']

}

9.

Écrire la liste des sommets, dans l'ordre de leur visite, lors du parcours en largeur du graphe du réseau routier de la figure 2 depuis le sommet 'V3'.

En supposant que toutes les arêtes ont le même poids, la fonction itineraire_court, ci-après, renvoie le plus court chemin entre deux sommets d'un graphe.

1 def itineraire_court(graphe, depart, arrivee):

2 deja_visites = []

3 a_visiter = []

4 a_visiter.append(depart)

5 precedent = {depart: None}

6 while a_visiter != []:

7 sommet = a_visiter.pop(0)

8 if sommet not in deja_visites:

9 deja_visites.append(sommet)

10 for voisin in graphe[sommet]:

11 if voisin not in deja_visites:

12 a_visiter.append(voisin)

13 precedent[voisin] = sommet

14 if voisin == arrivee:

15 a_visiter = []

16 break

17 if arrivee not in precedent:

18 return []

19 chemin = []

20 ville = arrivee

21 while ville != None:

22 chemin.append(ville)

23 ville = precedent[ville]

24 chemin.reverse()

25 return chemin

L'instruction break permet d'interrompre l'exécution d'une boucle et d'exécuter la suite du script. La méthode reverse des listes en Python inverse l'ordre des éléments d'une liste sans en créer une nouvelle. On rappelle que la méthode pop des listes Python enlève et renvoie l'élément de la liste situé à l'index indiqué.

Par exemple, ma_liste.pop(4) enlève et renvoie l'élément de la liste ma_liste situé à l'index 4.

L'instruction suivante est saisie puis exécutée.

>>> itineraire_court(route, 'V1', 'V5')

10.

Compléter l'évolution du contenu de la variable precedent à chaque tour de la boucle while, donné ci-dessous, suite à l'exécution de l'instruction saisie.

Tour n°1: {'V1': None}

Tour n°2: {'V1': None, 'V2': 'V1'}

Tour n°3: {'V1': None, 'V2': 'V1', 'V3': 'V2'}

...

11.

Écrire ce que renvoie la fonction itineraire_court suite à l'exécution de l'instruction saisie.