Ignorer la navigation

Activité 4

Réseaux sociaux et graphes

Imaginez un réseau social ayant 6 abonnés (A, B, C, D, E et F) où :

  • A est ami avec B, C et D

  • B est ami avec A et D

  • C est ami avec A, E et D

  • D est ami avec tous les autres abonnés

  • E est ami avec C, D et F

  • F est ami avec E et D

 Il existe un moyen plus "visuel" pour représenter ce réseau social : on peut représenter chaque abonné par un cercle (avec le nom de l'abonné situé dans le cercle) et chaque relation "X est ami avec Y" par un segment de droite reliant X et Y ("X est ami avec Y" et "Y est ami avec X" étant représenté par le même segment de droite).

Voici ce que cela donne avec le réseau social décrit ci-dessus :

Graphe

Ce genre de figure s'appelle un graphe. Les graphes sont des objets mathématiques très utilisés, notamment en informatique. Les cercles sont appelés des sommets et les segments de droites des arêtes.

Un peu de vocabulaire : considérons le graphe ci-contre.

distance : La distance entre deux sommets est le nombre de liens constituant le plus court chemin entre eux. (exemple : la distance entre A et F est de 2).

diamètre : le diamètre d'un graphe est la plus grande distance entre deux sommets du graphe.

(exemple : la distance maximale entre 2 sommets est de 2 : donc son diamètre est 2).

rayon : le rayon d'un graphe est la plus petite distance à laquelle l’un sommet peut se trouver de tous les autres (exemple : le rayon est ici de 1).

exemple : D est à une distance de 1 de tous les autres sommets : c'est le centre du graphe ; nous pouvons donc dire que le rayon du graphe est de 1.

centre : le centre d'un graphe est le sommet placé à la plus petite distance de tous les autres (le centre n'est pas nécessairement unique) : exemple : tous les sommets ont une distance égale à 2 à l'exception du sommet D qui est le seul situé à une distance de 1 de tous les autres ; nous pouvons donc affirmer que le centre du graphe 1 est unique et a pour sommet D, de rayon 1.

Exercice :

  1. Construisez un graphe de réseau social à partir des informations de la matrice suivante :

    Relations d’amitiés

    A

    B

    C

    D

    E

    F

    G

    A

    1

    B

    1

    1

    1

    C

    1

    1

    1

    D

    1

    E

    1

    1

    1

    F

    1

    1

    G

    1

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

  3. Déterminer la distance séparant A de D

  4. Légender avec le vocabulaire suivant : arête, centre, sommet, diamètre, rayon.

  5. Si C partage une information à son entourage, combien de partages faudra-t-il en plus pour que tout le monde soit informé ?