Exercices: Rayon, diamètre, centre et petit monde

Un réseau social de cinq amis est modélisé par un graphe. Les arêtes (relations d'amitié) sont : Alice–Bruno, Bruno–Chloé, Chloé–David, David–Emma.

1. a) Dessiner mentalement ou sur papier ce graphe et donner la distance entre Alice et Emma.

1. b) Donner la distance entre Alice et Chloé.

Dans un graphe, l'excentricité d'un sommet est la plus grande distance qui le sépare des autres sommets. Les arêtes du graphe sont : A–B, A–C, A–D.

1. a) Calculer l'excentricité de chacun des sommets A, B, C et D.

1. b) En déduire le rayon et le diamètre du graphe.

Rappeler la définition du diamètre d'un graphe et celle du centre d'un graphe. Les appliquer au graphe en chaîne P–Q–R (arêtes P–Q et Q–R).

Un groupe de six élèves d'un lycée de Lyon est modélisé par le graphe dont les arêtes sont : 1–2, 2–3, 3–4, 4–5, 5–6, 2–5.

1. a) Calculer l'excentricité de chaque sommet.

1. b) Donner le rayon, le diamètre et le ou les centres du graphe.

En 1967, Stanley Milgram a demandé à des personnes de faire parvenir une lettre à un inconnu en la transmettant uniquement à une connaissance personnelle. Les chaînes abouties comptaient en moyenne environ 6 transmissions (soit environ 5 intermédiaires).

1. a) Expliquer ce que cette expérience cherchait à montrer.

1. b) Expliquer ce qu'on appelle un « petit monde » et pourquoi cette expérience n'en est pas une preuve absolue (citer une limite).

Dans un lycée de Nantes, Léa a des liens très proches avec les 8 membres de son club de handball (qui se connaissent tous entre eux). Elle est aussi en contact avec Hugo, un cousin qui vit à Marseille et travaille dans un autre milieu.

1. a) Dire quelle relation relève du « bonding » (capital social de cohésion) et laquelle du « bridging » (capital social de pont).

1. b) Expliquer pourquoi le lien avec Hugo peut être plus utile pour trouver un stage dans un domaine inconnu du club.

Un graphe a pour sommets A, B, C, D, E, F, G et pour arêtes : A–B, B–C, C–D, D–E, E–F, F–G, C–F.

1. a) Calculer l'excentricité de chaque sommet.

1. b) Déterminer le rayon, le diamètre et le centre.

1. c) On ajoute l'arête A–G. Que deviennent le diamètre et le rayon ? Justifier.

On considère un graphe connexe de $n$ sommets.

1. a) Montrer que son diamètre est au plus $n-1$.

1. b) Donner un graphe à 6 sommets dont le diamètre vaut 5, puis un graphe à 6 sommets dont le diamètre vaut 2. Justifier.

1. c) Vérifier par le calcul que, pour le graphe en chaîne à 5 sommets, le diamètre est inférieur ou égal à deux fois le rayon.

Un réseau social A compte 2,9 milliards d'abonnés, un réseau de messages courts B en compte 0,45 milliard et un réseau professionnel C en compte 0,9 milliard. On suppose que dans chaque réseau le nombre moyen de relations par abonné est de 150 pour A, 200 pour B et 100 pour C.

1. a) Calculer le nombre total approximatif de relations (arêtes) de chaque réseau, sachant que chaque relation est comptée une fois pour deux abonnés.

1. b) Dans un réseau où chaque abonné a en moyenne 150 relations et où les relations sont « aléatoires », estimer le nombre de personnes atteintes en 2 étapes, puis en 3 étapes (ordre de grandeur $150^k$). Expliquer en quoi cela rend plausible le phénomène de petit monde.

1. c) Expliquer pourquoi cette estimation surévalue la réalité dans un groupe d'amis très soudé (bonding).