Activité 2 - Les graphes

Au préalable

Question 1 sur 10

🧠

Vérifie tes connaissances

⭐Score: 0/10

Question 7

Que montre la théorie du 'petit monde' ?

Que les réseaux sociaux ne sont pas des graphes

Que tous les humains sont connectés directement

Qu’il existe en moyenne six degrés de séparation entre deux personnes

Qu’il existe peu de liens entre les individus sur Terre

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.

On donne le graphe suivant dont les sommets représentent des individus, et les arêtes le lien entre 2 individus :

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 ?
4. Combien de connaissances séparent F et C ?
5. Si F voulait rencontrer C, par quelles personnes devrait-il passer, 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.

   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

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 lit : la personne B suit la personne D, mais D ne suit pas B.

1. Recopier et compléter le tableau suivant. Il se complète 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.