Fiche de cours
Les graphes
Dans un réseau social, il est parfois compliqué de se représenter tous les liens pouvant exister entre les utilisateurs. On utilise en mathématiques des graphes qui permettent de représenter graphiquement les connexions qui existent dans un réseau social.
En guise d'exemple, on considère un réseau social ne contenant que 8 abonnés : Mathieu, Nathan, Brice, Julia; Bastien, Camille, Franck et Cécilia.
On représente par un trait les liens d'amitiés entre les abonnés.
On peut alors répondre à divers questions : si tous les utilisateurs ont des amis en commun, comment peut faire un utilisateur pour connecter un ami via d'autres amis, ou si tous les membres du réseau sont connectés.
1) Vocabulaire
Ce type de schéma est appelé un graphe.
Chaque utilisateur représente un sommet du graphe. L'ensemble des sommets est note $V$.
Les connexions entre les utilisateurs sont appelées