Petit monde et graphes

Introduction

Prenez cinq élèves de votre classe : Alice, Bob, Chloé, Diego et Emma. Demandez qui parle vraiment avec qui en dehors des cours. Vous obtenez une liste un peu brouillonne du genre « Alice avec Bob et Chloé, Bob avec Alice et Diego, Chloé avec Alice et Diego et Emma… ». Au-delà de quelques personnes, cette liste devient illisible. Les mathématiques offrent un outil bien plus parlant pour ces situations : le graphe. Et une fois qu'un réseau d'amitiés devient un graphe, on peut le mesurer — parler de distances, de chemins, de centre. La surprise sera de taille : à l'échelle de la planète entière, ces distances sont étonnamment petites. C'est le phénomène du petit monde.

Construire un graphe à partir d'une situation

Reprenons les cinq amis. On dessine un point par personne et on relie par un trait chaque paire qui se parle vraiment. Voici le résultat pour ces cinq élèves :

• Alice parle avec Bob et Chloé.
• Bob parle avec Alice et Diego.
• Chloé parle avec Alice, Diego et Emma.
• Diego parle avec Bob, Chloé et Emma.
• Emma parle avec Chloé et Diego.

Voilà un graphe. Le vocabulaire officiel est très simple :

Cette simple représentation suffit déjà à répondre à des questions concrètes : « Qui Alice connaît-elle directement ? », « Combien d'amis a Diego ? », « Existe-t-il un chemin de Bob à Emma ? ».

Compter la distance entre deux personnes

Prenez deux sommets, par exemple Alice et Emma. Pour aller de l'un à l'autre, on suit les traits du graphe. Sur le dessin précédent, plusieurs chemins sont possibles : Alice → Chloé → Emma (2 traits), ou Alice → Bob → Diego → Emma (3 traits). On retient toujours le plus court.

Sur l'exemple :

• distance(Alice, Bob) = $1$ (un seul trait direct).
• distance(Alice, Diego) = $2$ (Alice → Bob → Diego, ou Alice → Chloé → Diego).
• distance(Alice, Emma) = $2$ (Alice → Chloé → Emma).
• distance(Bob, Emma) = $2$ (Bob → Diego → Emma).

Pas de formule, pas de calcul savant — on regarde le dessin et on compte.

Rayon, diamètre, centre — trois mesures du graphe

Une fois qu'on sait compter une distance, on peut décrire le graphe entier par quelques nombres. Trois suffisent pour ce que demande le programme.

Le diamètre — la plus grande distance dans le graphe

Le diamètre, c'est la plus grande distance que l'on peut trouver entre deux sommets du graphe. Autrement dit : « si je prends les deux personnes les plus éloignées, combien de traits les séparent ? »

Sur notre exemple, en parcourant toutes les paires, la distance maximale est $2$ (par exemple Alice–Emma, ou Bob–Emma). Donc diamètre = 2.

Le rayon — la distance au plus loin depuis le sommet le mieux placé

Pour chaque sommet, on peut se demander : « à quelle distance est mon voisin le plus éloigné ? ». C'est sa distance au plus loin.

• Pour Alice : son sommet le plus éloigné est Diego ou Emma → distance $2$.
• Pour Bob : son sommet le plus éloigné est Chloé ou Emma → distance $2$.
• Pour Chloé : tous les autres sommets sont à distance $\leq 2$ → distance $2$, mais en fait Chloé est à distance $1$ de Alice, Diego et Emma, et à distance $2$ de Bob → distance au plus loin = $2$.
• Pour Diego : à distance $1$ de Bob, Chloé et Emma, à distance $2$ de Alice → distance au plus loin = $2$.
• Pour Emma : à distance $1$ de Chloé et Diego, à distance $2$ d'Alice et Bob → distance au plus loin = $2$.

Tous les sommets ont la même distance au plus loin ($2$). Le rayon du graphe est la plus petite de ces distances au plus loin. Ici, rayon = 2.

Le centre — le ou les sommets les mieux placés

Le centre du graphe est l'ensemble des sommets dont la distance au plus loin est la plus petite — autrement dit ceux qui atteignent le rayon. Intuitivement, les sommets les plus centraux, ceux dont « la distance au plus loin est la plus petite ».

Sur notre exemple, tous les sommets ont la même distance au plus loin ($2$), donc tout le monde est dans le centre : centre = {Alice, Bob, Chloé, Diego, Emma}.

Méthode pas à pas

Pour déterminer rayon, diamètre et centre d'un petit graphe :

1. Dessiner le graphe (sommets et arêtes).
2. Pour chaque sommet, compter la distance au plus loin (la plus grande distance vers les autres sommets).
3. Le rayon = la plus petite de ces distances au plus loin.
4. Le diamètre = la plus grande de ces distances au plus loin.
5. Le centre = la liste des sommets dont la distance au plus loin égale le rayon.

Pour s'organiser quand le graphe a 5 ou 6 sommets, on peut écrire un petit tableau : une ligne par sommet, une colonne par sommet, on remplit les distances. La dernière colonne donne la distance au plus loin de chaque sommet.

Lecture : rayon = 2, diamètre = 2, centre = {tous les sommets}.

Le petit monde : l'expérience de Milgram

En 1967, le psychologue américain Stanley Milgram a tenté de mesurer la distance moyenne entre deux personnes choisies au hasard aux États-Unis. Le protocole :

• Donner à des personnes du Nebraska une lettre destinée à un courtier en bourse de Boston.
• Demander à chacune d'envoyer la lettre à une seule connaissance personnelle, choisie pour la rapprocher du destinataire.
• Comptabiliser le nombre d'intermédiaires nécessaires pour que la lettre arrive — ou pas — à destination.

Des études modernes sur Facebook (2016) sur 1,6 milliard d'utilisateurs ont trouvé un nombre moyen d'intermédiaires d'environ 3,5. À l'échelle mondiale, en 2026, le « monde » est encore plus petit qu'au temps de Milgram.

Pourquoi cela influence ce que vous voyez

Un réseau social fonctionne sur ce graphe d'amitié. Quand l'algorithme sélectionne les contenus à vous montrer, il pioche en priorité chez vos amis directs, puis chez vos amis d'amis. Conséquence :

• Vos amis influencent vos opinions, vos goûts, votre fil d'actualité.
• Si vos amis pensent tous pareil, votre fil ne montrera qu'une seule vision du monde — c'est la bulle de filtre.
• La structure du graphe détermine ce que vous voyez avant tout algorithme. Choisir ses amis, c'est déjà choisir son information.

Cas particuliers et pièges

• Graphe non connexe : si un sommet n'est relié à aucun autre, la distance n'est pas définie. Dans la pratique des réseaux sociaux, on se concentre sur la composante connexe principale.
• Confusion rayon / diamètre : le rayon est la « meilleure » distance au plus loin (la plus petite), le diamètre la « pire » (la plus grande). Inverser les deux est l'erreur classique.
• Centre ≠ centre géométrique : sur un dessin, le centre du graphe peut être en bord de page. Ce qui compte, c'est la distance au plus loin, pas la position sur le papier.

Pour aller plus loin

Le terme savant pour « la distance au plus loin » d'un sommet est excentricité. Avec ce mot, les définitions deviennent : diamètre = max des excentricités, rayon = min des excentricités, centre = sommets d'excentricité minimale. Vous pouvez le retenir comme bonus, mais le mot n'est pas exigé : la formulation en français suffit largement à la SNT.

La théorie des graphes va bien au-delà des distances : coloration, plus courts chemins (Dijkstra), parcours en largeur/profondeur. Vous retrouverez ces notions en NSI Première et Terminale, avec leurs algorithmes associés.