Devoir surveillé — Théorie des graphes

Une commune a installé six bornes de recharge pour véhicules électriques, notées A, B, C, D, E et F. Pour l'entretien du parc, le prestataire a câblé entre certaines bornes des liaisons de maintenance : lorsqu'une liaison existe entre deux bornes, un technicien peut lancer le diagnostic de l'une depuis l'autre, et cela fonctionne dans les deux sens.

On modélise la situation par le graphe non orienté $G=(S,\mathcal{A})$ ci-dessous : les sommets de $S$ sont les six bornes, et une arête de $\mathcal{A}$ relie deux bornes lorsqu'une liaison de maintenance existe entre elles.

1. Donner l'ordre $n$ du graphe $G$, puis dresser la liste de toutes les arêtes de $\mathcal{A}$ et en déduire le nombre $m$ d'arêtes. (0,5 point)

2. Déterminer le degré $d(s)$ de chacun des six sommets et présenter les résultats dans un tableau. Quelle borne est la moins bien reliée au reste du réseau ? Que se passerait-il pour elle si sa liaison tombait en panne ? (0,5 point)

3. Écrire la matrice d'adjacence $A$ du graphe $G$, les sommets étant rangés dans l'ordre alphabétique $(A,B,C,D,E,F)$. Indiquer un contrôle simple permettant de vérifier chaque ligne de la matrice à partir de la question 2. (0,75 point)

4. Démontrer, sans utiliser les valeurs numériques trouvées à la question 3, que la matrice d'adjacence d'un graphe non orienté est toujours symétrique. (0,25 point)

5. Énoncer la formule d'Euler dite des poignées de main, en expliquer la raison en une phrase, puis la vérifier sur le graphe $G$. (0,5 point)

6. Un technicien se trouve à la borne A et doit intervenir sur la borne F. Exhiber une chaîne de A à F et donner sa longueur. Cette chaîne est-elle de longueur minimale ? On justifiera la réponse en déterminant la valeur de $\delta (A,F)$. (0,5 point)

Une usine agroalimentaire est organisée en quatre ateliers numérotés $1$, $2$, $3$ et $4$. Les ateliers sont reliés par des convoyeurs à bande à sens unique : un convoyeur allant de l'atelier $i$ vers l'atelier $j$ achemine des palettes de $i$ vers $j$, et jamais dans l'autre sens. On modélise l'usine par le graphe orienté ci-dessous, dont les sommets sont les quatre ateliers et les arcs les convoyeurs.

Dans tout l'exercice, les sommets sont rangés dans l'ordre $(1,2,3,4)$ et on note $A$ la matrice d'adjacence du graphe. On appelle trajet de longueur $d$ de l'atelier $i$ vers l'atelier $j$ tout chemin orienté

$$i=u_0\to u_1\to \cdots \to u_d=j$$

empruntant exactement $d$ convoyeurs en respectant leur sens. Un atelier peut être traversé plusieurs fois par un même trajet.

1. Dresser la liste des six arcs du graphe, puis écrire la matrice $A$. La matrice $A$ est-elle symétrique ? Commenter. (0,5 point)

2. Déterminer, pour chacun des quatre ateliers, son degré sortant $d^{+}$ et son degré entrant $d^{-}$. Vérifier que la somme des degrés sortants et la somme des degrés entrants valent toutes les deux le nombre d'arcs, et expliquer pourquoi. (0,5 point)

3. Calculer $A^2$ en détaillant le calcul de chaque ligne. Interpréter le coefficient $(A^2{)}_{3,2}$ dans le contexte de l'usine, et le vérifier en énumérant les trajets correspondants. (1 point)

4. Calculer $A^3$ en détaillant le calcul de chaque ligne. (1 point)

5. Le service logistique veut connaître le nombre de trajets de longueur $3$ de l'atelier $1$ vers l'atelier $2$. Donner ce nombre à l'aide de la question 4, puis énumérer tous ces trajets pour vérifier le résultat. (0,5 point)

6. On constate que $(A^3{)}_{2,1}=0$. Un ingénieur en conclut que « les palettes de l'atelier $2$ ne peuvent jamais atteindre l'atelier $1$ ». Cette conclusion est-elle correcte ? Justifier soigneusement. (0,25 point)

7. Calculer la somme de tous les coefficients de $A^2$ et interpréter le nombre obtenu. Retrouver ce nombre à l'aide des degrés de la question 2. (0,25 point)

Une commune alimente son réseau d'eau potable à partir de cinq réservoirs, notés $R_1$, $R_2$, $R_3$, $R_4$ et $R_5$. Certains réservoirs sont reliés deux à deux par une canalisation de transfert, dans laquelle l'eau peut circuler dans les deux sens. Le service technique recense exactement six canalisations, reliant les paires de réservoirs suivantes :

On modélise ce réseau par le graphe non orienté $G$ dont les sommets sont les cinq réservoirs et les arêtes les six canalisations. On note $A$ la matrice d'adjacence de $G$, les sommets étant rangés dans l'ordre $(R_1,R_2,R_3,R_4,R_5)$.

1. Écrire la matrice $A$. (0,5 point)

2. Déterminer le degré de chacun des cinq réservoirs, puis vérifier la formule des poignées de main. (0,5 point)

3. Calculer $A^2$, puis $A^3$, en détaillant les calculs. Vérifier que ces deux matrices sont symétriques et expliquer pourquoi c'était prévisible. (0,75 point)

4. Énoncer le critère matriciel de connexité vu en cours, puis démontrer que le réseau est connexe. On pourra remarquer que tous les coefficients de $A^4$ sont des entiers positifs ou nuls, ce qui évite de calculer cette matrice. (0,75 point)

5. Déterminer la distance $\delta (R_1,R_j)$ de $R_1$ à chacun des autres réservoirs. On justifiera chaque valeur, et on indiquera comment les matrices des questions 1 et 3 permettent de contrôler les résultats. (0,5 point)

6. Déterminer l'excentricité de chacun des cinq réservoirs, puis le diamètre $\mathrm{diam}(G)$ du réseau. Interpréter ce diamètre pour le service technique. (0,5 point)

7. Une canalisation se rompt. Dans chacun des deux cas suivants, dire si le réseau reste connexe et le justifier. (0,5 point)

a. La canalisation $\{R_2,R_4\}$ est rompue.

b. La canalisation $\{R_4,R_5\}$ est rompue.

Le logo d'une association est un motif formé de six points, notés A, B, C, D, E et F, reliés par onze traits rectilignes. On note $G$ le graphe dont les sommets sont ces six points et dont les arêtes sont les onze traits du logo. Ces traits relient les paires de points suivantes :

Un graphiste veut dessiner ce logo d'un seul geste : sans jamais lever le crayon, et sans repasser deux fois sur un même trait. Autrement dit, il cherche une chaîne eulérienne dans le graphe $G$.

On rappelle le théorème d'Euler, admis en cours. Soit $G$ un graphe connexe.

• $G$ admet un cycle eulérien (une chaîne eulérienne qui revient à son point de départ) si et seulement si tous ses sommets sont de degré pair.
• $G$ admet une chaîne eulérienne non fermée si et seulement s'il possède exactement deux sommets de degré impair, et ces deux sommets en sont alors les extrémités.

1. Déterminer le degré de chacun des six points et présenter les résultats dans un tableau. Préciser quels sont les sommets de degré impair. (0,5 point)

2. Vérifier la formule des poignées de main sur le graphe $G$ et retrouver ainsi le nombre de traits du logo. (0,5 point)

3. Démontrer que, dans tout graphe non orienté, le nombre de sommets de degré impair est un nombre pair. (0,75 point)

4. Justifier que $G$ est connexe, puis répondre aux deux questions du graphiste : peut-il dessiner le logo d'un seul geste ? Peut-il, en plus, revenir à son point de départ ? Préciser les points de départ et d'arrivée possibles. (0,5 point)

5. Exhiber explicitement un tracé convenable, sous la forme de la liste ordonnée des points rencontrés. Vérifier ce tracé trait par trait : on justifiera que chaque trait emprunté est bien un trait du logo, et que les onze traits sont parcourus une fois et une seule. (1,25 point)

6. Insatisfait, le graphiste veut absolument revenir à son point de départ. Il s'autorise pour cela à ajouter au logo un douzième trait, entre deux des six points existants. Démontrer qu'il n'a qu'un seul choix possible, puis exhiber un tracé fermé du nouveau logo. (0,5 point)

Une entreprise de sept salariés, notés A, B, C, D, E, F et G, analyse l'usage de sa messagerie interne. On construit un graphe non orienté $G$ dont les sommets sont les sept salariés : deux salariés sont reliés par une arête lorsqu'ils échangent régulièrement des messages. Le service informatique obtient le graphe suivant.

Dans tout l'exercice, les sommets sont rangés dans l'ordre alphabétique $(A,B,C,D,E,F,G)$ et on note $n$ l'ordre du graphe.

On rappelle les deux mesures de centralité vues en complément du cours. Elles ne sont pas exigibles au programme, et toutes les définitions utiles sont redonnées ci-dessous.

Le degré de centralité d'un salarié $s$ est le quotient

$$C_D(s)={\displaystyle \frac{d(s)}{n-1}},$$

c'est-à-dire la proportion des autres salariés avec lesquels $s$ échange directement.

Le degré d'intermédiarité d'un salarié $s$ est défini de la façon suivante. Pour deux salariés $u$ et $v$ distincts et tous deux différents de $s$, on note ${\sigma }_{u,v}$ le nombre de chaînes de longueur minimale reliant $u$ à $v$, et ${\sigma }_{u,v}(s)$ le nombre de celles qui passent par $s$. On pose alors

$$C_B(s)=\sum _{\{u,v\}}{\displaystyle \frac{{\sigma }_{u,v}(s)}{{\sigma }_{u,v}}},$$

la somme portant sur toutes les paires $\{u,v\}$ de salariés distincts et différents de $s$, chaque paire n'étant comptée qu'une seule fois.

Partie A. Qui échange avec le plus de monde ?

1. Déterminer le degré de chacun des sept salariés, présenter les résultats dans un tableau, puis vérifier la formule des poignées de main. (0,5 point)

2. Écrire la matrice d'adjacence $A$ du graphe. On la présentera sous la forme d'un tableau à sept lignes et sept colonnes, bordé par les noms des salariés. (0,5 point)

3. Calculer le degré de centralité $C_D(s)$ de chacun des sept salariés, sous forme de fraction simplifiée puis de valeur décimale arrondie au centième. Quels sont les salariés les mieux connectés au sens de cette mesure ? (0,5 point)

Partie B. Qui fait circuler l'information ?

4. Déterminer la distance $\delta (A,s)$ de A à chacun des six autres salariés, en justifiant chaque valeur. En déduire l'excentricité $e(A)$. (0,75 point)

5. Déterminer l'excentricité de chacun des sept salariés, puis le diamètre $\mathrm{diam}(G)$ du réseau. Préciser entre quels salariés ce diamètre est atteint. (0,5 point)

6. Calculer le degré d'intermédiarité $C_B(D)$ du salarié D. On détaillera, dans un tableau, les quinze paires de salariés à considérer, leurs chaînes de longueur minimale, et la contribution de chaque paire à la somme. (1,25 point)

7. Calculer, de la même façon, le degré d'intermédiarité $C_B(B)$ du salarié B. (0,5 point)

8. Comparer les résultats des questions 3, 6 et 7 pour les salariés B et D. Que constate-t-on ? Rédiger, en une ou deux phrases, une conclusion indiquant quel salarié fragiliserait le plus la circulation de l'information s'il quittait l'entreprise, et justifier cette réponse en examinant ce qu'il advient du graphe lorsqu'on retire ce salarié. (0,5 point)