Graphes et influence

1. a)Sommets = utilisateurs ; arêtes = relations d'amitié. (1)
2. b)Un abonnement n'est pas forcément réciproque (A peut suivre B sans que B suive A) : chaque lien a un sens. (1)
3. c)Longueur (nombre d'arêtes) d'une plus courte chaîne reliant les deux sommets. (1)
4. d)Ensemble des sommets dont l'excentricité (plus grande distance aux autres) est minimale, égale au rayon. (1)

À retenir — Une distance se mesure toujours sur une plus courte chaîne, et en arêtes, pas en sommets.

1. a)8 sommets (Rémi, Sara, Théo, Ugo, Véra, Wael, Xavier, Yasmine) et 8 arêtes. (1)
2. b)Rémi 2, Sara 2, Théo 3, Ugo 3, Véra 2, Wael 1, Xavier 2, Yasmine 1. (1)
3. c)2 + 2 + 3 + 3 + 2 + 1 + 2 + 1 = 16 = 2 × 8 : somme des degrés = double du nombre d'arêtes. (1)
4. d)La somme des degrés serait 7 × 3 = 21, nombre impair ; or elle vaut le double du nombre d'arêtes, donc elle est paire : impossible. (1)

Repère — La somme des degrés est toujours paire : c'est un contrôle rapide de tout comptage.

1. a)Niveaux depuis Rémi : 1 : Sara, Théo ; 2 : Ugo ; 3 : Véra, Xavier ; 4 : Wael, Yasmine. Donc d(Rémi, Yasmine) = 4 (Rémi–Théo–Ugo–Xavier–Yasmine). (1)
2. b)Rémi 4, Sara 4, Théo 3, Ugo 2, Véra 3, Wael 4, Xavier 3, Yasmine 4. (1)
3. c)Diamètre = plus grande excentricité = 4 ; rayon = plus petite = 2. (1)
4. d)Centre = {Ugo} (seul d'excentricité 2) : prévenu en premier, il fait parvenir l'information à tous en 2 étapes au plus. (1)

Erreur fréquente — Choisir Théo parce qu'il a autant d'amis qu'Ugo : le centre se lit sur les excentricités, et celle de Théo vaut 3.

1. a)len(g['c']) = 3 : c'est le degré du sommet 'c' (voisins 'a', 'd', 'e'). (1)
2. b)Somme des longueurs : 2 + 1 + 3 + 1 + 1 = 8 ; chaque arête compte deux fois, donc 8 ÷ 2 = 4 arêtes. (1)
3. c)Il affiche b, d, e (une ligne chacun) : les sommets de degré 1, qui n'ont qu'un seul voisin. (1)
4. d)g['b'].append('d') puis g['d'].append('b') : la relation doit figurer dans les deux listes. (1)

Attention — Dans un graphe non orienté codé en Python, toute modification doit être faite dans les deux listes.

1. a)Des participants devaient faire parvenir une lettre à un inconnu de Boston via des connaissances personnelles ; les chaînes réussies comptaient en moyenne un peu plus de cinq intermédiaires. (1)
2. b)Malgré un très grand nombre de sommets, la distance entre deux sommets reste petite (quelques unités). (1)
3. c)Distance 1 : 40 personnes. Chaque ami a 39 autres amis qu'elle, soit au plus 40 × 39 = 1 560 personnes à distance 2. Total : 40 + 1 560 = 1 600 au plus. (1)
4. d)Beaucoup d'amis ont des amis en commun (ou sont amis entre eux) : ces personnes sont comptées plusieurs fois dans le calcul, qui n'est qu'un majorant. (1)

Le point clé — Le calcul « 40 × 39 » suppose qu'il n'y a aucun ami commun : c'est un maximum, jamais une valeur exacte.