Exercice : Vocabulaire des graphes et parcours

Étape 1

On modélise le réseau informatique par un graphe non orienté dont les sommets représentent les serveurs et les arêtes représentent les liaisons directes entre deux serveurs.

Étape 2

Le graphe possède $9$ sommets et $17$ arêtes. Le nombre de liaisons directes rattachées à un serveur correspond au degré de ce sommet dans le graphe.

Étape 3

Calculons la somme des degrés de tous les sommets du graphe :

Étape 4

$$6 \times 4 + 2 \times 2 + k = 24 + 4 + k = 28 + k$$

Étape 5

D'après la propriété fondamentale des graphes, la somme des degrés des sommets est égale au double du nombre d'arêtes du graphe.

Étape 6

Ce qui équivaut à l'équation suivante :

Étape 7

$$28 + k = 2 \times 17$$

Étape 8

$$28 + k = 34$$

Étape 9

On en déduit :

Étape 10

$$k = 34 - 28 = 6$$

Étape 11

Le dernier serveur est donc relié directement à $6$ autres serveurs.