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.

  1. Quelles personnes ont le plus d'amis ?

  2. Et le moins d'amis ?

  3. Tous les participants ont-ils des amis en commun ?

  4. 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 ;

  1. Réaliser le graphe de ce réseau.

  2. Déterminer son diamètre, son centre et son rayon.

  3. Qui était le leader du réseau Facebook ? Pourquoi ?

  4. Qui est le leader de ce réseau Twitter ? Comment l'identifier ?

  5. Pour qui cette information est-elle importante et pourquoi ?