Sciences numériques et technologie · Seconde
Graphes et petits mondes : exercices corrigés de 2de
Publié le 9 novembre 2026 · Mis à jour le 9 novembre 2026 · Signaler une erreur
L'essentiel
- Un graphe se compose de sommets (les personnes) et d'arêtes (les relations) ; le degré d'un sommet compte ses arêtes.
- La distance entre deux sommets est le nombre d'arêtes du plus court chemin qui les relie.
- Dans un graphe, la somme des degrés vaut deux fois le nombre d'arêtes : le degré moyen s'en déduit.
- L'effet petit monde : deux personnes quelconques sont reliées par une chaîne courte, surtout grâce à quelques raccourcis.
- Ajouter une seule arête-raccourci peut faire baisser nettement la distance moyenne du réseau.
Comment utiliser ces exercices
Ces exercices s'adressent aux élèves de seconde qui ont déjà vu le fonctionnement des réseaux sociaux. Ils t'entraînent à lire un graphe, à compter des degrés, à trouver un plus court chemin et à comprendre pourquoi un réseau peut être un « petit monde ». Les difficultés sont croissantes : commence par les premiers, puis monte en niveau. Cherche toujours seul(e) pendant quelques minutes avant d'ouvrir un indice, et seulement ensuite la correction.
Un peu de contexte pour situer le sujet. Le « phénomène du petit monde » est une hypothèse, encore discutée : deux personnes prises au hasard dans une société seraient reliées par une courte chaîne de relations sociales 3. L'idée des « six degrés de séparation » a été formulée en 1929 par Frigyes Karinthy 3. L'expérience du petit monde a été conduite en 1967 par le psychosociologue Stanley Milgram 3. En 1998, Duncan Watts et Steven Strogatz ont publié un premier modèle de réseau reproduisant cet effet 3.
Les exercices
Exercice 1 Lire le degré d'un sommet
Un petit réseau compte cinq personnes : A, B, C, D et E. Les relations sont les suivantes : A–B, A–C, B–C, C–D et D–E.
Quel est le degré de la personne C ?
Indice 1
Liste toutes les relations dans lesquelles C apparaît.
Indice 2
Le degré compte les arêtes, pas les voisins de voisins.
Voir la correction pas à pas
On repère les relations qui contiennent C : A–C, B–C et C–D.
On compte ces relations : il y en a trois.
Le degré de C est donc 3. Contrôle : C est la personne la plus connectée du réseau, car A, B et D ont un degré de 2 et E n'a qu'une relation.
Le degré de C vaut 3. Le degré mesure la popularité locale d'un sommet : ici C sert de pivot entre le groupe A–B–C et la fin de la chaîne D–E.
Exercice 2 Trouver une distance
Dans le même réseau (relations A–B, A–C, B–C, C–D, D–E), quelle est la distance entre A et E, c'est-à-dire la longueur de la plus courte chaîne qui les relie ?
Indice 1
Dessine les cinq personnes et trace les relations.
Indice 2
Essaie la chaîne A–B–C–D–E, puis cherche un chemin plus court.
Voir la correction pas à pas
Première chaîne possible : A–B–C–D–E, de longueur 4.
Cherche un raccourci : A est relié directement à C, d'où la chaîne A–C–D–E.
Cette chaîne compte trois arêtes : A–C, C–D et D–E.
Aucune chaîne de deux arêtes ne convient, car E n'est relié qu'à D et A n'est pas relié à D.
La distance entre A et E est 3. La première chaîne trouvée n'est pas toujours la plus courte : il faut comparer.
Exercice 3 Six relations, combien d'intermédiaires ?
On dit que deux personnes sont séparées par une chaîne de six relations, comme dans l'idée des « six degrés de séparation » 3. Combien de personnes intermédiaires se trouvent entre ces deux personnes ?
Indice 1
Fais un schéma avec une ligne de points : 6 segments, combien de points ?
Indice 2
Les deux personnes aux extrémités ne sont pas des intermédiaires.
Voir la correction pas à pas
Une chaîne de 6 relations relie 7 personnes : les deux extrémités et celles du milieu.
On retire les deux extrémités : 7 − 2 = 5.
On retrouve la règle : intermédiaires = relations − 1, soit 6 − 1.
Il y a 5 intermédiaires. Retiens que le nombre de personnes d'une chaîne dépasse toujours d'une unité le nombre de relations.
Exercice 4 Degré moyen d'un groupe
Dans un club, 8 élèves forment un réseau où l'on compte 12 amitiés (chaque amitié est une arête, sans doublon). Quel est le degré moyen d'un élève ?
Indice 1
Chaque amitié relie deux élèves : à combien de degrés contribue-t-elle au total ?
Indice 2
Le degré moyen est la somme des degrés divisée par le nombre de sommets.
Voir la correction pas à pas
Une arête touche deux sommets : elle ajoute 1 au degré de chacun, donc 2 à la somme totale.
Somme des degrés : 2 × 12 = 24.
On divise par le nombre d'élèves : 24 ÷ 8 = 3.
Contrôle : en moyenne, chaque élève a 3 amis dans le club, ce qui est plausible pour 8 personnes.
Le degré moyen est 3 amitiés par élève. La somme des degrés vaut toujours le double du nombre d'arêtes, ce qui sert de test de contrôle sur n'importe quel graphe.
Exercice 5 Distance moyenne dans un anneau
Six personnes numérotées de 1 à 6 sont placées en cercle. Chacune est reliée à ses deux voisines : 1–2, 2–3, 3–4, 4–5, 5–6 et 6–1.
Calcule la distance moyenne entre la personne 1 et les cinq autres.
Indice 1
Détermine séparément la distance de 1 vers 2, 3, 4, 5 et 6.
Indice 2
Pour aller de 1 à 5, tu peux tourner dans un sens ou dans l'autre : garde le plus court.
Voir la correction pas à pas
Vers 2 : une arête, distance 1. Vers 6 : une arête, distance 1.
Vers 3 : chaîne 1–2–3, distance 2. Vers 5 : chaîne 1–6–5, distance 2.
Vers 4 : chaîne 1–2–3–4 ou 1–6–5–4, distance 3 dans les deux sens.
Somme : 1 + 1 + 2 + 2 + 3 = 9.
Moyenne : 9 ÷ 5 = 1,8.
La distance moyenne depuis la personne 1 vaut 1,8 arête. Dans un anneau, les personnes les plus éloignées sont de l'autre côté du cercle.
Exercice 6 L'effet d'un raccourci
On reprend l'anneau de six personnes et on ajoute une seule relation : un raccourci entre 1 et 4. Les autres relations ne changent pas.
Quelle est maintenant la distance moyenne entre la personne 1 et les cinq autres ?
Indice 1
Seule une distance diminue sûrement : laquelle ?
Indice 2
Vérifie aussi 3 et 5 : le raccourci les rapproche-t-il ?
Voir la correction pas à pas
Vers 2 et vers 6 : toujours 1.
Vers 4 : la nouvelle arête 1–4 donne une distance de 1 (au lieu de 3).
Vers 3 : la chaîne 1–2–3 reste de longueur 2, et 1–4–3 aussi.
Vers 5 : 1–6–5 reste de longueur 2, et 1–4–5 aussi.
Somme : 1 + 2 + 1 + 2 + 1 = 7 ; moyenne : 7 ÷ 5 = 1,4.
La distance moyenne passe de 1,8 à 1,4 : une seule arête de plus fait baisser la moyenne d'environ 22 %, car 0,4 ÷ 1,8 ≈ 0,22. Cette baisse forte obtenue avec très peu de changements est justement l'intuition des modèles de petit monde : modifier quelques arêtes suffit à faire chuter la distance 3.
Exercice 7 Population multipliée par mille
Sur le plan mathématique, l'effet petit monde se traduit par une distance moyenne entre deux nœuds proportionnelle au logarithme du nombre de nœuds 3. Pour simplifier, on adopte le modèle suivant : la distance moyenne vaut , où est le nombre de personnes du réseau.
Un réseau passe de à personnes. De combien d'arêtes la distance moyenne augmente-t-elle dans ce modèle ?
Indice 1
Rappelle-toi que .
Indice 2
Calcule d'abord la distance pour chaque taille, puis fais la différence.
Voir la correction pas à pas
Pour : .
Pour : .
Augmentation : arêtes.
Comparaison : la population a été multipliée par , mais la distance n'a augmenté que de 3.
La distance augmente de 3 arêtes seulement. Quand la taille du réseau est multipliée par mille, la distance gagne trois unités : c'est la croissance très lente d'un logarithme, qui rend crédible une chaîne courte même dans un très grand réseau. Ce coefficient 1 est une simplification d'exercice, pas une mesure réelle.
Exercice 8 Un réseau est-il un petit monde ?
Deux réseaux de 1 000 personnes sont décrits.
- Réseau X : chaque personne connaît uniquement ses 4 voisines les plus proches sur un grand cercle. La distance moyenne dépasse la centaine d'arêtes (environ 125).
- Réseau Y : même construction, mais on a déplacé quelques dizaines de relations pour relier des personnes très éloignées sur le cercle.
- Lequel présente l'effet petit monde ? Justifie.
- Que se passe-t-il pour les groupes d'amis proches dans le réseau Y ?
Indice 1
Pense à ce que fait un raccourci sur la distance moyenne, comme dans l'exercice précédent.
Indice 2
Demande-toi si les quelques relations déplacées détruisent les groupes d'amis.
Voir la correction pas à pas
Le réseau X a une distance moyenne qui grandit avec le nombre de personnes, à la manière d'un treillis : il n'est pas un petit monde.
Dans le réseau Y, chaque raccourci relie deux régions éloignées du cercle et fait chuter fortement la distance moyenne.
Seules quelques arêtes ont changé : l'essentiel des groupes d'amis proches, voisins sur le cercle, reste intact.
Le réseau Y réunit donc les deux caractéristiques des petits mondes : une distance moyenne faible et des structures proches de cliques 3.
Le réseau Y est un petit monde. Cette construction est celle du modèle publié en 1998 par Watts et Strogatz 3 : on part d'un réseau très régulier, on modifie quelques liens, et la distance s'effondre sans que les groupes soudés disparaissent. Les relations lointaines jouent le rôle de ces liens faibles qui tiennent ensemble un réseau social 3.
Les questions qu'on se pose
Comment savoir si je dois compter les arêtes ou les sommets ?
Une distance et un degré se comptent toujours en arêtes. Tu comptes des sommets seulement quand on te demande combien de personnes une chaîne contient. Pour passer de l'un à l'autre : une chaîne de arêtes traverse sommets.
Le phénomène du petit monde est-il une vérité démontrée ?
C'est une hypothèse qui reste discutée 3. Elle s'appuie sur l'expérience de Milgram en 1967 et sur des modèles de réseaux, mais on ne peut pas affirmer que deux humains quelconques sont toujours reliés par exactement six relations. En exercice, on travaille donc sur des graphes précis, dont on connaît toutes les arêtes.
Pourquoi un seul raccourci change-t-il autant la distance moyenne ?
Un raccourci relie deux zones éloignées du réseau : toutes les chaînes qui devaient faire le tour passent désormais par cette arête. Dans l'exercice de l'anneau à six personnes, la distance moyenne depuis la personne 1 baisse de 1,8 à 1,4 avec une seule arête ajoutée. Plus le réseau est grand, plus l'effet d'un raccourci est spectaculaire.
Sources
- Document Éduscol - Sciences Numériques et Technologie, Ministère de l'Éducation nationale - Éduscol. Consulté le 9 novembre 2026.
- INSEE - Méthodologie statistique - Partitionnement et analyse de graphes, INSEE. Consulté le 9 novembre 2026.
- Étude du petit monde, Wikipédia. Consulté le 9 novembre 2026.
Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.