Complément : Un peu de vocabulaire
Répondre aux questions suivantes à partir de la vidéo proposée.
3. Quel "objet mathématique" permet de représenter un réseau routier ?
4.1. De quoi un graphe est-il constitué ?
4.2. Qu'est-ce qui différencie les arêtes pour le réseau social Twitter de Facebook ?
4.3. Le graphe pour Facebook est-il orienté ou non-orienté ? Justifier.
4.4. Qu'appelle-t-on distance dans un graphe ?
4.5. Définir le plus court chemin dans un graphe.
Définition :
Dans un graphe, l'écartement d'un sommet est la distance maximale qui existe entre ce sommet et les autres sommets du graphe.
Le diamètre d'un graphe est égal à l'écartement maximal de ses sommets : cela correspond au nombre maximal de liens intermédiaires nécessaires pour mettre deux personnes quelconques du réseau en relation.
Le centre d'un graphe est l'ensemble des sommets d'écartement minimal, le centre d'un graphe peut donc être constitué de plusieurs sommets : dans le cas d'un réseau social, cela correspond donc au groupe d'individus qui aura besoin d'un minimum d'intermédiaires pour pouvoir contacter toutes les personnes du réseau.
Le rayon d'un graphe est l'écartement d'un des sommets du centre du graphe, c'est-à-dire l'écartement minimal.
Exemple : réseau de type Facebook
Alban, Béatrice, Charles, Déborah, Éric, Fatima, Gérald, sont inscrits sur Facebook.
Alban, Béatrice, Charles, Déborah, Éric, Fatima, Gérald, sont inscrits sur Facebook.
Alban est ami avec Béatrice, Éric et Fatima.
Béatrice est amie avec Alban, Charles, Déborah.
Charles est ami avec Béatrice, Déborah et Gérald.
Déborah, avec Charles, Béatrice et Gérald.
Éric, avec Fatima et Alban.
Fatima, avec Alban et Éric.
Gérald, avec Charles et Déborah.
Quelles personnes ont le plus d'amis ?
Et le moins d'amis ?
Tous les participants ont-ils des amis en commun ?
Peuvent-ils tous entrer en contact par le biais de leurs amis ?
On a résumé le réseau précédent dans un tableau :
5.1. vous devez le compléter en ajoutant une croix dans la colonne de gauche de chaque membre dès qu'une relation d'amitié existe.
5.2. Ce tableau n'est pas très visuel pour comprendre les relations entre les personnes.
Vous allez réaliser le graphe de ce réseau social : chaque personne sera représentée par la première lettre de son prénom et constituera un sommet.
5.3. Faut-il mettre des flèches au niveau des arêtes de ce graphe ? Justifier.
6.1. Compléter le tableau précédent en indiquant la distance entre chacun des sommets du graphe dans la colonne de droite.
6.2. Compléter le tableau suivant donnant l'écartement de chacun des sommets du graphe :
7. Déterminer, pour ce graphe :
Le diamètre du graphe
Le centre du graphe : Béatrice
Le rayon du graphe
8. Déterminer le diamètre du graphe dans l'expérience de Milgram.
Exemple : réseau de type Twitter
Dans ce type de réseau, les relations sont souvent orientées : David peut être abonné à Zoé (« follower » de Zoé) sans que la réciproque soit nécessairement vraie.
Alban, Béatrice, Charles, Déborah, Éric, Gérald et Fatima sont également inscrits sur Twitter.
Voici leurs activités :
Alban suit Béatrice et Déborah ;
Béatrice suit Alban ;
Charles suit Béatrice et Gérald ;
Déborah suit Alban, Charles et Fatima ;
Éric suit Alban et Déborah ;
Fatima suit Éric ;
Gérald suit Déborah.
Réaliser le graphe de ce réseau.
Déterminer son diamètre, son centre et son rayon.
Qui était le leader du réseau Facebook ? Pourquoi ?
Qui est le leader de ce réseau Twitter ? Comment l'identifier ?
Pour qui cette information est-elle importante et pourquoi ?