Aller au contenu

Devoir NSI sur les réseaux et les graphes

Exercice 1 (4 points)

Cet exercice porte sur les réseaux et les protocoles de routages.

Quelques rappels : Une adresse IPv4 est composée de 4 octets X1.X2.X3.X4 qui peuvent être écrits en notation binaire ou décimale.

La notation CIDR 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 la partie « hôte » (machine).

1. a. Donner le nombre de bits formant un octet.

b. Déterminer l'écriture décimale de l'adresse IPv4 correspondant à l'écriture binaire :

\[11000000.10101000.00000100.11110001\]
Corrigé

1.a. Un octet est composé de 8 bits.

1.b. Conversion octet par octet :

  • 11000000 = 128 + 64 = 192
  • 10101000 = 128 + 32 + 8 = 168
  • 00000100 = 4
  • 11110001 = 128 + 64 + 32 + 16 + 1 = 241

Adresse IPv4 décimale : 192.168.4.241

2. On considère la machine d'adresse IPv4 172.20.1.242 / 24.

a. Donner la notation décimale du masque de sous-réseau de cette machine.

b. Donner l'adresse décimale de ce réseau.

c. Donner le nombre maximal de machines que l'on peut connecter sur ce réseau.

Corrigé

2.a. Le préfixe /24 signifie que les 24 premiers bits sont à 1, les 8 suivants à 0.

Masque de sous-réseau : 255.255.255.0

2.b. On applique un ET logique bit à bit entre l'adresse IP et le masque :

172.20.1.242 AND 255.255.255.0 = 172.20.1.0

Adresse du réseau : 172.20.1.0

2.c. Le préfixe /24 laisse 8 bits pour la partie hôte, soit \(2^8 = 256\) adresses possibles. On soustrait l'adresse réseau (172.20.1.0) et l'adresse de diffusion broadcast (172.20.1.255).

Nombre maximal de machines : 256 − 2 = 254 machines

3. On considère le réseau représenté ci-dessous

Schéma du réseau

Le protocole RIP (Routing Information Protocol) est un protocole de routage qui cherche à minimiser le nombre de routeurs traversés (ce qui correspond à la distance ou au nombre de sauts).

Le réseau est composé de 7 routeurs : R1, R2, R3, R4, R5, R6 et R7 et utilise le protocole RIP. Le routeur R1 doit transmettre des données au routeur R5.

a. Déterminer le parcours pouvant être emprunté par ces données en vous aidant des tables de routage ci-dessous.

Table de routage de R1

Destination Passe par
R2 R2
R3 R6
R4 R2
R5 R6
R6 R6
R7 R7

Table de routage de R2

Destination Passe par
R1 R1
R3 R3
R4 R4
R5 R4
R6 R3
R7 R1

Table de routage de R3

Destination Passe par
R1 R6
R2 R2
R4 R2
R5 R6
R6 R6
R7 R6

Table de routage de R4

Destination Passe par
R1 R2
R2 R2
R3 R2
R5 R5
R6 R5
R7 R2

Table de routage de R5

Destination Passe par
R1 R6
R2 R4
R3 R6
R4 R4
R6 R6
R7 R6

Table de routage de R6

Destination Passe par
R1 R1
R2 R3
R3 R3
R4 R5
R5 R5
R7 R7
Corrigé

On suit les tables de routage pas à pas :

  • R1 veut atteindre R5 → passe par R6 (table de R1 : R5 via R6)
  • R6 veut atteindre R5 → passe par R5 (lien direct)

Parcours : R1 → R6 → R5 (2 sauts — chemin optimal selon RIP)

Pour les deux questions suivantes, on suppose que la liaison entre R1 et R6 est coupée.

b. Donner une nouvelle table de routage possible pour R1.

Corrigé

Sans la liaison directe R1–R6, R1 doit passer par R2 ou R7. Le chemin le plus court (en nombre de sauts) vers chaque destination devient :

Destination Passe par
R2 R2
R3 R2
R4 R2
R5 R2
R6 R2
R7 R7

R1 passe désormais par R2 pour joindre R5 et R6 (chemin le moins sauté disponible).

c. En déduire le parcours que suivront les données pour aller du routeur R1 au routeur R5.

Corrigé

On suit les tables de routage :

  • R1 → R5 : passe par R2 (nouvelle table de R1)
  • R2 → R5 : passe par R4 (table de R2)
  • R4 → R5 : passe par R5 (lien direct)

Parcours : R1 → R2 → R4 → R5 (3 sauts)

4. Pour la suite de l'exercice, on considère que la liaison entre R1 et R6 a été rétablie et on applique désormais le protocole de routage OSPF attribuant un coût à chaque liaison afin de trouver le chemin permettant une transmission plus rapide.

Le coût d'une liaison est défini par la relation :

\[\text{coût} = \dfrac{10^8}{d}\]

où d représente le débit en \(\text{bit·s}^{-1}\).

a. Recopier et compléter le tableau suivant :

Liaison Débit Coût
Ethernet \(10\)
Fast-Ethernet \(10^8\)
Fibre \(10^9\) \(0.1\)
Corrigé

On utilise la formule coût = \(\dfrac{10^8}{d}\) :

  • Ethernet : coût = 10 → d = \(\dfrac{10^8}{10}\) = \(10^7\) bit/s (10 Mbit/s)
  • Fast-Ethernet : d = \(10^8\) → coût = \(\dfrac{10^8}{10^8}\) = 1
  • Fibre : d = \(10^9\) → coût = \(\dfrac{10^8}{10^9}\) = 0,1 ✓
Liaison Débit Coût
Ethernet \(10^7\) bit/s 10
Fast-Ethernet \(10^8\) bit/s 1
Fibre \(10^9\) bit/s 0,1

b. Reproduire la Figure 2 en faisant apparaître le coût de chacune des liaisons

GR1R1R7R7R1--R7R6R6R1--R6R2R2R1--R2R6--R7R3R3R6--R3R5R5R6--R5R2--R3R4R4R2--R4R4--R5

\[\text{Figure 2 : Représentation du réseau}\]

Le coût d'un chemin est la somme des coûts des liaisons empruntées.

Corrigé

D'après la Figure 1, les types de liaisons et leurs coûts sont :

Liaison Type Coût
R1 — R2 Fibre 0,1
R1 — R6 Fibre 0,1
R1 — R7 Fast-Ethernet 1
R2 — R3 Fibre 0,1
R2 — R4 Fibre 0,1
R3 — R6 Ethernet 10
R4 — R5 Fast-Ethernet 1
R5 — R6 Fast-Ethernet 1
R6 — R7 Ethernet 10

La Figure 2 annotée reprend ce graphe avec ces valeurs sur chaque arête.

GR1R1R2R2R1--R20,1R6R6R1--R610R7R7R1--R71R3R3R2--R30,1R4R4R2--R40,1R6--R70,1R3--R61R5R5R4--R51R5--R610

c. Donner les 6 chemins possibles ainsi que leur coût lors de l'envoi d'un paquet depuis le routeur R1 vers le routeur R5.

Corrigé
N° Chemin Calcul Coût
1 R1 → R6 → R5 10 + 10 20
2 R1 → R2 → R4 → R5 0,1 + 0,1 + 1 1,2
3 R1 → R2 → R3 → R6 → R5 0,1 + 0,1 + 10 + 1 11,2
4 R1 → R6 → R3 → R2 → R4 → R5 0,1 + 10 + 1 + 0,1 + 1 12,2
5 R1 → R7 → R6 → R5 1 + 10 + 0,1 11,1
6 R1 → R7 → R6 → R3 → R2 → R4 → R5 1 + 1 + 1 + 0,1 + 0,1 + 0,1 3,3

d. Déduire, en respectant le protocole OSPF, le chemin le moins coûteux lors de l'envoi d'un paquet depuis le routeur R1 vers le routeur R5. Préciser le coût minimal.

Corrigé

Chemin optimal : R1 → R2 → R4 → R5 — Coût minimal : 1,2

Exercice 2

Partie A

On suppose que l'on dispose de l'interface suivante pour modéliser la structure abstraite de graphe non orienté :

  • creer_graphe_vide() : renvoie un graphe vide.

  • liste_sommets(G) : renvoie la liste des sommets du graphe G.

  • liste_voisins(G,s) : renvoie la liste des sommets voisins du sommet s dans le graphe G.

  • sont_voisins(G, s1, s2) : renvoie True si les sommets s1 et s2 sont voisins dans le graphe G, et False sinon.

  • ajouter_sommet(G,s) : ajoute le sommet s au graphe G, sans le relier à un autre sommet (cette fonction ne renvoie rien, elle modifie en place le graphe G).

  • ajouter_arete(G, s1, s2) : ajoute une arête entre les sommets s1 et s2 du graphe G, à condition qu'une telle arête n'existe pas déjà (si l'arête existe déjà, la fonction ne fait rien ; et cette fonction ne renvoie rien, elle modifie en place le graphe G).

La fonction Python taille(G) ci-dessous prend en paramètre un graphe G et renvoie la taille du graphe.

def taille(G) : 
    return len(liste_sommets(G))

  1. Écrire en Python le code d'une fonction degré(G, s) qui prend en paramètres un graphe G et un de ses sommets s et qui renvoie le degré du sommet s dans le graphe G, c'est-à-dire le nombre d'arêtes qui ont s comme extrémité.

    Étant donné un graphe non orienté \(G\), on appelle complémentaire de \(G\), et on note \(\overline{G}\), le graphe non orienté tel que :

    • ses sommets sont les mêmes que ceux de \(G\);

    • deux sommets \(s1\) et \(s2\) sont voisins dans \(\overline{G}\) si et seulement si \(s1\) et \(s2\) ne sont pas voisins dans \(G\).

    Par exemple, si \(G_1\) est le graphe:

    \(G_1\)

    alors son complémentaire \(\overline{G_1}\) est le graphe :

    \(\overline{G_1}\)

    Corrigé

    Le degré d'un sommet dans un graphe non orienté est égal au nombre de ses voisins :

    def degré(G, s):
    return len(liste_voisins(G, s))

  2. Tracer le complémentaire du graphe \(G_2\) ci-dessous :

    \(G_2\)

    Corrigé

    Le graphe \(G_2\) possède les sommets {A, B, C, D, E, F} et les arêtes : A-B, A-E, B-F, C-F, D-E, D-F

    Pour tracer \(\overline{G_2}\), on conserve les mêmes sommets et on relie exactement les paires non reliées dans \(G_2\) :

    Arêtes de \(\overline{G_2}\) : A-C, A-D, A-F, B-C, B-D, B-E, C-D, C-E, E-F

    (Dessin : graphe à 6 sommets avec ces 9 arêtes)

  3. On veut coder en Python la création du complémentaire d'un graphe \(G\).

    Écrire le code d'une fonction complementaire(G) qui prend en paramètre un graphe G et qui renvoie son complémentaire.

    On pourra suivre la démarche suivante :

    • on crée un graphe vide ;

    • on y ajoute tous les sommets du graphe G ;

    • pour tout sommet s1 de G et tout sommet s2 de G, si s1 et s2 sont distincts et qu'ils ne sont pas voisins dans G, on ajoute une arête entre s1 et s2 dans le nouveau graphe.

    Corrigé 
    def complementaire(G):
    G_comp = creer_graphe_vide()
    for s in liste_sommets(G):
        ajouter_sommet(G_comp, s)
    for s1 in liste_sommets(G):
        for s2 in liste_sommets(G):
            if s1 != s2 and not sont_voisins(G, s1, s2):
                ajouter_arete(G_comp, s1, s2)
    return G_comp

    Note : ajouter_arete gère les doublons, chaque arête n'est donc ajoutée qu'une seule fois.

  4. Étant donné un graphe G et un de ses sommets s, indiquer lequel des trois booléens b1, b2 ou b3 est évalué en True (vous pouvez vous aider de l'exemple du graphe \(G_1\) et de son complémentaire).

    >>> b1 = degré(complementaire(G), s) == taille(G) - degré(G,s)
>>> b2 = degré(complementaire(G), s) == taille(G) - 1 - degré(G,s)
>>> b3 = degré(complementaire(G), s) == taille(G) + 1 - degré(G,s)
    Corrigé

    Dans un graphe \(G\) à \(n = \text{taille}(G)\) sommets, un sommet \(s\) a \(\text{degré}(G, s)\) voisins.

    Dans le complémentaire \(\overline{G}\), \(s\) est relié à tous les sommets auxquels il n'était pas relié dans \(G\), en excluant \(s\) lui-même :

    \[\text{degré}(\overline{G}, s) = (n - 1) - \text{degré}(G, s)\]

    Vérification sur \(G_1\) (5 sommets, sommet A de degré 2 dans \(G_1\)) : degré(\(\overline{G_1}\), A) = 5 − 1 − 2 = 2 ✓ (A est relié à D et E dans le complémentaire)

    C'est b2 qui est True : 

    degré(complementaire(G), s) == taille(G) - 1 - degré(G, s)

Partie B

  1. Donner la matrice d'adjacence qui correspond au graphe \(G_2\) (on indexera les sommets dans l'ordre alphabétique)

    Corrigé

    Sommets dans l'ordre alphabétique : A, B, C, D, E, F

    Arêtes de \(G_2\) : A-B, A-E, B-F, C-F, D-E, D-F

    A B C D E F
    A 0 1 0 0 1 0
    B 1 0 0 0 0 1
    C 0 0 0 0 0 1
    D 0 0 0 0 1 1
    E 1 0 0 1 0 0
    F 0 1 1 1 0 0

  2. Écrire en python une fonction matcomp qui prend pour argument la matrice d'adjacence d'un graphe G (donc, en python, une liste de listes) et retourne la matrice d'adjacence du graphe complémentaire.

    Corrigé

    La matrice du complémentaire inverse les 0 et les 1, sauf sur la diagonale (qui reste à 0) :

    def matcomp(mat):
    n = len(mat)
    comp = []
    for i in range(n):
        ligne = []
        for j in range(n):
            if i == j:
                ligne.append(0)
            else:
                ligne.append(1 - mat[i][j])
        comp.append(ligne)
    return comp

  3. Donner la liste des degrès des sommets du graphe \(G_2\)

    Corrigé

    Le degré de chaque sommet est égal à la somme des valeurs de sa ligne dans la matrice :

    Sommet A B C D E F
    Degré 2 2 1 2 2 3

    Vérification : somme des degrés = 2+2+1+2+2+3 = 12 = 2 × 6 arêtes ✓

  4. Écrire en python une fonction qui permet de retourner la liste des degrès des sommets d'un graphe \(G\) à partir de sa matrice d'adjacence.

    Corrigé 
    def liste_degres(mat):
    return [sum(ligne) for ligne in mat]

    Version développée :

    def liste_degres(mat):
    degres = []
    for ligne in mat:
        degres.append(sum(ligne))
    return degres

  5. On dit qu'un graphe est régulier si ses sommets ont tous le même degré.

    Écrire en python une fonction regulier, qui prend en argument la matrice d'adjacence d'un graphe et retourne True si le graphe correspondant est régulier et False sinon.

    Corrigé 
    def regulier(mat):
    degres = liste_degres(mat)
    d0 = degres[0]
    for d in degres:
        if d != d0:
            return False
    return True

    Version compacte avec set :

    def regulier(mat):
    return len(set(liste_degres(mat))) == 1

    Application à \(G_2\) : les degrés sont [2, 2, 1, 2, 2, 3] → \(G_2\) n'est pas régulier.

  6. Donner la liste des sommets obtenus dans le cas où on réalise un parcours du graphe \(G_2\) en largeur en partant du sommet \(A\).

    Corrigé

    Adjacences de \(G_2\) (ordre alphabétique) : A : {B, E} — B : {A, F} — C : {F} — D : {E, F} — E : {A, D} — F : {B, C, D}

    Étape Nœud dépilé Voisins ajoutés à la file File après traitement
    1 A B, E [B, E]
    2 B F (A déjà visité) [E, F]
    3 E D (A déjà visité) [F, D]
    4 F C (B, D déjà en file/visités) [D, C]
    5 D — (E, F déjà visités) [C]
    6 C — (F déjà visité) []

    Ordre de parcours BFS depuis A : A, B, E, F, D, C