Exercice 1 - Partie B : Parcours de graphes · Bac Numérique et Sciences Informatiques Polynésie 2024 (jour 1)

Partie A: Réseau dans un lycée

Dans un lycée, le réseau contient plusieurs sous-réseaux: pédagogie (noté P), administration (noté AD), vie_scolaire (noté VS).

Partie B: Réseaux et graphes

Dans un réseau dont la structure est connue, on veut pouvoir déterminer si deux routeurs peuvent communiquer entre eux, c’est-à-dire s’il existe entre eux une route constituée de routeurs reliés par des sous-réseaux. On représente ce réseau de routeurs par un graphe $G$ dont les routeurs sont les sommets et les sous-réseaux reliant les routeurs sont les arêtes.

On propose la fonction de recherche d’un chemin entre deux sommets R1 et R2 suivante:

def recherche(R1, R2):

if R1 == R2:

return True

for S in adjacents(R1, G):

if recherche(S, R2):

return True

return False

où adjacents(R1, G) renvoie la liste des sommets adjacents à R1 dans le graphe $G$, classés dans l’ordre alphabétique de leur nom.

8.

Indiquer ce qui se passera si on utilise cette fonction de recherche entre deux sommets non reliés par un chemin dans le graphe.

9.

Proposer une solution pour résoudre ce problème.