Activité 2 - Les graphes

Objectifs

1. Comprendre la notion de graphe ;
2. Représenter des situations avec un graphe ;
3. Comprendre des concepts de fonctionnement des réseaux sociaux.

Activité

L'ensemble de l'activité se fait soit sur feuille, soit sur un document word.

On donne le graphe suivant dont les sommets représentent des individus, et les arêtes le fait que 2 individus se connaissent :

Ici, E connaît G par exemple.

Lecture de graphe

1. Quelles sont les personnes qui connaissent F ? Quelles sont les personnes que F connait ?
2. Quelles sont les personnes qui connaissent C ? Quelles sont les personnes que C connait ?
3. Si on compte le nombre de relations de F et C, qui est le plus populaire entre les 2 ?
4. Combien de connaissances séparent F et C ?
5. Si F voulait apprendre à connaître C, par qui devrait-il passer pour rencontrer C de façon optimale ?

Application

1. On s'intéresse à l'individu E. Recopier le tableau en dessous et compléter la colonne liaison avec l’ensemble des liaisons, et distance avec le nombre représentant la distance entre la personne E et les autres personnes.

   Liaison	Distance
   E-D	1
   E-G
   E-F

2. Quel est le sommet le plus éloigné de E ? En déduire la valeur de son excentricité.
3. Quelle est l’excentricité de la personne D ?
4. On appelle degré d’un sommet le nombre d’arêtes que le sommet possède.
   Recopier le tableau ci-dessous et compléter la colonne sommet avec les sommets du graphe, et degré pour chaque sommet.

   Sommet	Degré
   A	3
   B
   C

5. Si une information devait être transmise dans ce cercle de personnes, qui devrait être la personne à transmettre l’information, pour toucher le plus de monde ?

Caractéristiques

1. En vous servant des questions précédentes, quel(s) sommet(s) pourrai(en)t être le centre de ce graphe ?
2. Déterminer à partir des questions précédentes le rayon de ce graphe.
3. Déterminer à partir des questions précédentes le diamètre de ce graphe.
4. Que représenterait finalement le diamètre si 2 personnes devaient s’échanger une information ?

Système de follower/following

On dispose du graphe suivant cette fois-ci, composé de flèches :

On peut donc lire que la personne B suit la personne D, mais que D ne suit pas B. D suit A, etc ...

1. Recopier et compléter le tableau suivant en mettant une croix dans la case en fonction de si la personne de la rangée suit la personne de la colonne.

   	A	B	C	D	E
   A
   B				X
   C
   D	X
   E

2. Qui serai(en)t la/les personne(s) pouvant diffuser une information à le plus de personnes ?
3. En déduire le centre du graphe ainsi que son rayon.
4. Si une information devait être transmise, quelle(s) personne(s) ne devrai(en)t pas envoyer l’information ?
5. En déduire la valeur du diamètre du graphe.