Exercice 15

Commençons par lister les affinités de chaque personne : $$A:\{\text{montagne, sport}\} \quad ; \quad B:\{\text{sport, rencontres}\} \quad ; \quad C:\{\text{musée}\}$$

$$D:\{\text{montagne, sport, rencontres}\} \quad ; \quad E:\{\text{montagne, musée, sport}\}$$ On compte alors les affinités communes à chaque paire, deux personnes étant compatibles dès qu'elles en partagent au moins deux :

La relation « être compatible » est symétrique : le graphe est donc non orienté, et ses arêtes sont $A$--$D$, $A$--$E$, $B$--$D$ et $D$--$E$.

En rangeant les sommets dans l'ordre $A$, $B$, $C$, $D$, $E$ : $$\boxed{M=\begin{pmatrix} 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}}$$ Cette matrice est symétrique, comme toute matrice d'adjacence de graphe non orienté, et sa diagonale est nulle puisqu'on ne se déclare pas compatible avec soi-même. La somme de tous ses coefficients vaut $8$, soit deux fois le nombre d'arêtes.

On remarque que $C$ n'est compatible avec personne : son unique affinité, les musées, n'est partagée qu'avec $E$, et une seule affinité commune ne suffit pas. À l'inverse, $D$ est compatible avec tout le monde sauf $C$ : c'est le profil le plus « riche », avec trois affinités.