Exercice 2 - Graphes · Bac Numérique et Sciences Informatiques Métropole 1 remplacement 2024

EXERCICE 2 (6 points)

Cet exercice porte sur les réseaux, les protocoles de routage et les graphes.

Partie A

Le réseau informatique d'une société est constitué d'un ensemble de routeurs interconnectés à l'aide de fibres optiques.

La figure ci-dessous représente le schéma de ce réseau. Il est composé de deux réseaux locaux L1 et L2. Le réseau local L1 est relié au routeur R1 et le réseau local L2 est relié au routeur R9.

Dans cette partie, les adresses IP sont composées de 4 octets, soit 32 bits. Elles sont notées X1.X2.X3.X4, où X1, X2, X3 et X4 sont les valeurs des 4 octets, converties en notation décimale. La notation X1.X2.X3.X4/n signifie que les n premiers bits de poids forts de l'adresse IP représentent la partie « réseau », les bits suivants représentent la partie « hôte ».

Toutes les adresses des machines connectées à un réseau local ont la même partie réseau.

Le tableau suivant indique les adresses IPv4 des machines constituant le réseau de la société.

NOM · TYPE · ADRESSE IPV4

R1 · Routeur · Interface 1:192.168.1.1/24

Interface 2:192.168.2.1/24

Interface 3:192.168.3.1/24

Interface 4:192.168.4.1/24

Interface 5:192.168.5.1/24

R2 · Routeur · Interface 1:192.168.2.2/24

Interface 2:192.168.7.1/24

Interface 3:192.168.8.1/24

R3 · Routeur · Interface 1:192.168.3.2/24

Interface 2:192.168.7.2/24

Interface 3:192.168.9.1/24

Interface 4:192.168.10.1/24

R4 · Routeur · Interface 1:192.168.5.2/24

Interface 2:192.168.6.1/24

R5 · Routeur · Interface 1:192.168.8.2/24

Interface 2:192.168.9.2/24

Interface 3:192.168.11.1/24

Interface 4:192.168.12.1/24

R6 · Routeur · Interface 1:192.168.4.2/24

Interface 2:192.168.6.2/24

Interface 3:192.168.10.2/24

Interface 4:192.168.11.2/24

Interface 5:192.168.13.1/24

Interface 6:192.168.14.1/24

R7 · Routeur · Interface 1:192.168.12.2/24

Interface 2:192.168.13.2/24

Interface 3:192.168.15.1/24

Interface 4:192.168.16.1/24

R8 · Routeur · Interface 1:192.168.14.2/24

Interface 2:192.168.15.2/24

Interface 3:192.168.17.1/24

R9 · Routeur · Interface 1:192.168.16.2/24

Interface 2:192.168.17.2/24

Interface 3:192.168.18.1/24

P1 · Portable · 192.168.1.10

P2 · Portable · Non fourni

P3 · Portable · Non fourni

P4 · Portable · Non fourni

Partie B

Le graphe G, représenté ci-dessous, schématise l'architecture du réseau de la société. Les sommets représentent les routeurs et les arêtes représentent les liaisons.

3.

Donner l'implémentation Python des listes d'adjacence de ce graphe à l'aide d'un dictionnaire dont les clés sont les sommets et les valeurs la liste des sommets adjacents du sommet clé. On nomme G ce dictionnaire.

Afin de faciliter la notation, on s'autorise à écrire chaque couple clé/valeur sur une nouvelle ligne.

6.

On appelle M la matrice d'adjacence du graphe de la figure 2. Les sommets sont rangés par ordre croissant des numéros des routeurs (R1, R2,..., R9).

Donner l'écriture en Python de cette matrice d'adjacence sous la forme d'une liste de listes.

7.

Le degré d'un sommet est le nombre d'arêtes dont ce sommet est une extrémité.

Recopier et compléter les lignes 3, 5 et 6 de la fonction degre qui prend en paramètre la matrice d'adjacence d'un graphe donné sous forme d'une liste de listes et qui renvoie la liste des degrés de tous les sommets du graphe rangés dans le même ordre que les sommets de la matrice d'adjacence.

1 def degre(MATRICE):

2 d = []

3 for... in...:

4 cpt = 0

5 for... in...:

6 cpt = cpt +...

7 d.append(cpt)

8 return d

8.

Donner la liste renvoyée par degre(M).

9.

On appelle chaîne eulérienne d'un graphe non orienté un chemin qui passe une et une seule fois par toutes les arêtes du graphe. Un graphe connexe admet une chaîne eulérienne si et seulement si le graphe possède, au plus, deux sommets de degré impair.

En utilisant le résultat de la question précédente et en admettant que le graphe est connexe, indiquer si le robot peut parcourir l'ensemble du réseau en suivant les fibres optiques et en empruntant chaque fibre optique une et une seule fois.