Exercice : Vocabulaire des graphes et parcours

Étape 1

Pour modéliser la situation, on associe à chaque serveur un sommet. Le graphe comporte donc $6$ sommets : $A$, $B$, $C$, $D$, $E$ et $F$.

Étape 2

Chaque liaison directe entre deux serveurs correspond à une arête reliant les deux sommets associées.

Étape 3

On recense les arêtes du graphe sans répétition :

Étape 4

Les arêtes reliées au sommet $A$ sont : $\{A, B\}$, $\{A, C\}$ et $\{A, D\}$.

Étape 5

Les arêtes reliées au sommet $B$ non encore comptabilisées sont : $\{B, C\}$ et $\{B, E\}$.

Étape 6

Les arêtes reliées au sommet $C$ non encore comptabilisées sont : $\{C, D\}$ et $\{C, F\}$.

Étape 7

L'arête reliée au sommet $E$ non encore comptabilisée est : $\{E, F\}$.

Étape 8

On peut également utiliser le lemme des poignées de main (théorème de la somme des degrés) : la somme des degrés de tous les sommets est égale au double du nombre d'arêtes du graphe.

Étape 9

Déterminons le degré de chaque sommet (nombre de connexions) :

Étape 10

$$\deg(A) = 3, \quad \deg(B) = 3, \quad \deg(C) = 4, \quad \deg(D) = 2, \quad \deg(E) = 2, \quad \deg(F) = 2$$

Étape 11

La somme des degrés vaut :

Étape 12

$$3 + 3 + 4 + 2 + 2 + 2 = 16$$

Étape 13

Le nombre d'arêtes du graphe est donc :

Étape 14

$$\frac{16}{2} = 8$$

Étape 15

Le graphe modélisant le réseau informatique comporte donc $8$ arêtes.