Exercice 2 - Graphes · Bac Numérique et Sciences Informatiques Asie jour 1 - Remplacement 2025

Exercice 2 (6 points)

Cet exercice porte sur les réseaux, le routage, les graphes et la programmation

Un aéroport dispose d’un réseau informatique décomposé en différents sous-réseaux:

Navigation (N): utilisé principalement par la tour de contrôle;

Guichets (G): utilisé aux guichets dans le hall;

Achats (A): utilisé sur les bornes d’achat placées dans le hall;

Sécurité (S): utilisé aux contrôles de sécurité;

Portes (P): utilisé au niveau des portes d’accès aux avions;

Bagages (B): utilisé par les services qui gèrent le transit des bagages;

Commerces (C): utilisé par tous les commerces.

Le réseau possède l’architecture suivante, où R1, R2, R3, R4, R5, R6 et R7 sont des routeurs:

Pour éviter ce problème, on veut reconfigurer les routeurs en réécrivant leurs tables de routage à l'aide d'un programme. Pour y parvenir, on modélisera le réseau par un graphe.

Dans toute la suite, les sommets du graphe, qui représenteront les routeurs du réseau, seront décrits par leur nom (type str) et un graphe sera représenté par un dictionnaire associant à chaque sommet la liste des sommets qui lui sont liés par une arête.

Pour la prochaine question uniquement, on considère le réseau obtenu en se limitant aux routeurs R1, R2, R3 et R5. On obtient alors le réseau suivant:

5.

Donner le dictionnaire correspondant au réseau de la Figure 2.

Pour remplir les tables de routage en évitant le problème soulevé à la question 4, on souhaite utiliser le protocole RIP, qui minimise le nombre de routeurs par lesquels les paquets transitent. Une première idée est de construire la liste de tous les chemins possibles reliant ces deux routeurs puis de choisir un chemin le plus court possible dans cette liste.

On suppose que l'on dispose d'une fonction liste_chemins(graphe, r_depart, r_arrivee) qui prend en paramètres un graphe, un routeur de départ et un routeur d'arrivée et qui renvoie la liste de tous les chemins liant les deux routeurs, les chemins étant représentés par les listes des routeurs par lesquels passer.

En notant g le graphe écrit à la question 5. On a donc:

>>> liste_chemins(g, 'R1', 'R5')

[['R1', 'R2', 'R5'], ['R1', 'R3', 'R2', 'R5']] On a besoin de connaître un chemin le plus court possible entre deux routeurs en utilisant le protocole RIP.

7.

Écrire une fonction plus_court_chemin(graphe, r_depart, r_arrivee) qui renvoie une liste représentant un des plus courts chemins entre les routeurs r_depart et r_arrivee en utilisant le protocole RIP. On utilisera la fonction liste_chemins définie à la question précédente.

L'agent responsable du réseau consulte un informaticien au sujet de cette fonction. Il lui explique que cette fonction a un défaut: construire tous les chemins liant deux routeurs peut être long pour un réseau étendu. En effet, le nombre de chemins augmente de façon quasi exponentielle avec le nombre de routeurs. Pour remédier à ce problème et améliorer le temps d'exécution de la recherche d'un plus court chemin, l'informaticien lui propose d'utiliser une autre approche basée sur un parcours en largeur du graphe. En effet, avec un tel parcours, si un chemin est trouvé, il est forcément de longueur minimale.

8.

Compléter la fonction plus_court_chemin_largeur(graphe, r_depart, r_arrivee) suivante qui traduit l'idée de l'informaticien, réalisant un parcours en largeur et dans laquelle le dictionnaire dict_chemins associe à un routeur le chemin reliant r_depart à ce routeur.

def plus_court_chemin_largeur(graphe, r_depart, r_arrivee):

dict_chemins = {}

L = [r_depart]

sommets_marques = [r_depart]

dict_chemins[r_depart] = [r_depart]

for r in L:

for s_r in graphe[r]:

if not s_r in sommets_marques:

sommets_marques.append(...) # <-- Compléter (1)

dict_chemins[s_r] = dict_chemins[r] + [s_r]

if s_r == r_arrivee:

return... # <-- Compléter (2)

L.append(s_r)

9.

Écrire alors une fonction table_routage(graphe, routeur) qui renvoie la table de routage du routeur passé en paramètre sous la forme d'un dictionnaire associant à chaque routeur destination la passerelle correspondante. On pourra utiliser les fonctions écrites dans les questions précédentes.