Cette activité s'inscrit dans la thématique Les Réseaux Sociaux du programme de SNT.

Elle est proposée par Claire Savinas, actuellement professeure de mathématiques et d'ICN au lycée Jean Vilar à Villeneuve-lès-Avignon. Claire Savinas assure également les formations académiques de SNT.

Découverte du problème à résoudre

Fanny utilise avec ses amis un réseau social. Elle a fait la liste des liens d'amitiés dans le tableau suivant. Une croix dans le tableau signifie que les deux personnes concernées partagent un lien d'amitié. L'objectif de cette activité est de modéliser ces liens d'amitié pour pouvoir ensuite les étudier.

	Fanny	Chloé	Robin	Maéva	Angie	Matéi	Julia
Fanny		X	X				X
Chloé	X		X	X	X	X	X
Robin	X	X				X
Maéva		X			X		X
Angie		X		X			X
Matéi		X	X
Julia	X	X		X	X

Découverte de la notion de graphe

Pour étudier les liens d'amitié, on va utiliser une représentation sous forme de graphe.

1. Compléter le graphe ci-dessus où chaque arête signifie "... et .... sont amis".

   Chaque personne est représentée par un sommet et chaque lien d'amitié est représenté par une arête.

Découverte de l'écartement d'un sommet d'un graphe

On considère que seulement deux personnes amies peuvent communiquer entre elles. Fanny peut parler avec ses amis qui sont Chloé, Robin et Julia. Pour communiquer avec Maéva, elle doit passer par exemple par Chloé, ce qui fait une distance de 2. Pour parler à Angie, elle peut également passer par Chloé, ce qui fait également une distance de 2. Pour parler à Matéi, elle peut passer par Robin, ce qui fait également une distance de 2. La distance maximale entre Fanny et les autres personnes du graphe est de 2.

2. Compléter le tableau ci-dessous avec la distance maximale, c'est-à-dire le nombre de liens d'amitié entre un sommet avec les autres sommets du graphe.

   Fanny	Chloé	Robin	Maéva	Angie	Matéi	Julia
   2

Fanny	Chloé	Robin	Maéva	Angie	Matéi	Julia
2	1	2	2	2	2	2

Déterminer le ou les centres d'un graphe

Dans un graphe donné, le centre est le sommet dont l'écartement est minimal. Un graphe peut avoir plusieurs centres. Les centres d'un graphe sont alors les éléments à partir desquels l'information se diffuse le plus vite dans un réseau.

3. Déterminer le centre de ce graphe.

D'après le tableau précédent, la distance minimale est détenue par Chloé qui est donc le centre du graphe.

4. Interpréter la réponse précédente dans le contexte de l'activité.

Chloé est la personne qui devra passer par le moins d'intermédiaires pour joindre tout le groupe. Ici, elle est la seule qui puisse communiquer avec toutes les autres personnes directement.

Déterminer le rayon d'un graphe

Le rayon d'un graphe est l'écartement d'un centre du graphe.

5. Déterminer le rayon de ce graphe.

Chloé est le centre du graphe. Son écartement est de 1. Le rayon du graphe est donc 1.

6. Interpréter la réponse précédente dans le contexte de l'activité.

Le rayon est le nombre d'intermédiaires moins un pour joindre tout le groupe en partant du ou des centres du graphe.

Déterminer le diamètre d'un graphe

Dans un graphe donné, le diamètre est la plus longue distance entre deux sommets.

7. Déterminer le diamètre de ce graphe.

D'après le tableau des distances établi en début d'activité, la distance maximale entre deux sommets est de 2. Le diamètre de ce graphe est donc 2.

8. Interpréter la réponse précédente dans le contexte de l'activité.

Le diamètre du graphe est le nombre maximum d'intermédiaires moins un pour que deux personnes communiquent entre elles.

Déterminer le nombre de liens d'amitiés à utiliser pour contacter une personne.

Une chaîne d'un graphe est une liste ordonnée de sommets du graphe telle que chaque sommet de la liste soit adjacent au suivant. La longueur d'une chaîne est le nombre d'arêtes qui la composent. La distance entre deux sommets d'un graphe est la plus petite des longueurs des chaînes qui la relient.

La matrice d'adjacence associée à un graphe non orienté d'ordre $n$ dont les sommets sont numérotés de 1 à $n$ est la matrice carrée d'ordre $n$, où le terme figurant en ligne $i$ et colonne $j$ est égal au nombre d'arêtes reliant $i$ et $j$.

9. Déterminer la matrice d'adjacence de ce graphe.

En conservant le même ordre de prénoms que dans le tableau, la matrice d'adjacence est la suivante :

$\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ \end{pmatrix}$

Sur la calculatrice :

Soit M la matrice d'adjacence associée à un graphe non orienté dont les sommets sont numérotés. $p$ désigne un nombre entier naturel. $\text{M}^p$ donne le nombre de chaı̂nes de longueur $p$ reliant $i$ et $j$.

10. Saisir la matrice d'adjacence de ce graphe dans la calculatrice et calculer le carré de cette matrice.

    Appuyez sur la touche shift puis sur la touche exp de la calculatrice pour créer une matrice. La remplir ensuite avec les coefficients et appuyer sur la touche square pour calculer le carré.



11. Interpréter le coefficient $a_{1,2}$ du carré de la matrice d'adjacence.

$a_{1,2}=2$ donc il y a deux chaînes de longueur 2 qui relient Fanny et Chloé. Il s'agit de Fanny-Robin-Chloé et Fanny-Julia-Chloé.

12. Interpréter le coefficient $a_{3,4}$ du carré de la matrice d'adjacence.

$a_{3,4}=1$ donc il n'y a qu'une seule chaîne de longueur 2 qui relie Robin et Maéva. Il s'agit de Robin-Chloé-Maéva.

Différence de fonctionnement entre Facebook et Twitter

Sur le réseau Facebook, pour être en relation, deux personnes inscrites doivent en effet s'accepter mutuellement comme "amis", alors qu'il est possible sur Twitter, de suivre une personne inscrite sans que cela ne soit réciproque.

On peut représenter ces relations unilatérales par des graphes et modéliser le sens de la relation par une orientation de l'arête.