Exercice 1 - Graphes · Bac Numérique et Sciences Informatiques Nouvelle-Calédonie 2025 (jour 1)

Cet exercice porte sur les graphes, les protocoles réseaux et la programmation orientée objet.

Partie A

Le graphe suivant modélise un ensemble de routeurs; les sommets sont les routeurs, les arêtes les liaisons entre ceux-ci.

Voici un résumé sommaire du fonctionnement du protocole RIP permettant à chaque routeur d'un réseau de taille modérée d'établir sa table de routage:

Règle a ( règle d'initialisation). Chaque routeur initialise sa table en y ajoutant ses voisins directs. Ils sont accessibles en un saut, sans passer par aucun routeur intermédiaire.

Règle b ( règle de transmission/réception). À intervalles de temps réguliers chaque routeur envoie sa table de routage à ses voisins.

Règle c ( règle de mise à jour). Lorsqu'un routeur reçoit les informations d'un routeur voisin, trois cas peuvent survenir:

une route vers un nouveau routeur lui est présentée: il l'ajoute à sa table de routage;

une route vers un routeur déjà connu lui est présentée, plus longue en nombre de sauts que celle inscrite dans sa table: elle est ignorée;

une route vers un routeur déjà connu lui est présentée, mais strictement plus courte en nombre de sauts que la précédente: l'ancienne est remplacée par celle-ci.

La réception par chaque routeur des tables de tous ses voisins et la mise à jour de sa table de routage en conséquence constitue une itération du protocole. Au bout d'un petit nombre de ces itérations, plus aucune table de routage ne varie, on dit que le processus est stabilisé.

Pour tout cet exercice, on n'envisagera pas les cas problématiques dans lesquels une liaison est coupée ou un routeur tombe en panne.

On considère des routeurs A, B, C, D, E et F connectés comme indiqué sur le graphe de la figure 1.

Voici la table de routage de A à l'initialisation du protocole RIP:

Table de routage de A

routeur · nombre de sauts · prochain routeur

B · 1 · –

C · 1 · –

E · 1 · –

On désire parcourir ce graphe en largeur depuis le sommet A.

1.

Dire lequel de ces parcours est un parcours en largeur en justifiant: