Des relations au graphe
Nouveau thème : les réseaux sociaux. Et une question de fond : comment une machine peut-elle « comprendre » qui est ami avec qui, au point de te suggérer des amis, des vidéos, des publicités ?
Pour cela, il lui faut d'abord une façon de représenter les relations. C'est l'objet de cette séance, et l'outil s'appelle un graphe.
Une table ne suffit pas
Voici les relations d'amitié dans un petit groupe. Tu reconnais la forme : c'est une table, comme au chapitre précédent.
| Personne | Est ami avec |
|---|---|
| Alice | Bob, Chloé |
| Bob | Alice, David |
| Chloé | Alice, Emma |
| David | Bob, Emma |
| Emma | Chloé, David |
Réponds mentalement : Alice et David ont-ils un ami en commun ? Qui est le plus « central » du groupe ? Combien de relations faut-il traverser pour aller d'Alice à David ?
C'est pénible, non ? Pourtant l'information est là, complète. Le problème n'est pas la donnée, c'est sa représentation : une table range bien les valeurs, mais elle cache les liens.
Dessiner les relations
Changeons de représentation. On garde exactement les mêmes données, mais on les dessine :
- chaque personne devient un cercle (on écrira son initiale) ;
- chaque relation d'amitié devient un segment entre deux cercles.
Maintenant, relis les questions du dessus. Les amis communs se voient. Le chemin d'Alice à David se suit du doigt. La même information, mais elle est devenue lisible.
La leçon
Une donnée n'a pas une seule forme possible. Bien choisir sa représentation, c'est déjà résoudre la moitié du problème. La table et le dessin contiennent strictement la même chose ; l'un rend les questions difficiles, l'autre les rend faciles.
Le vocabulaire : sommets et arêtes
Cette représentation s'appelle un graphe. C'est l'un des objets les plus utilisés en informatique, et c'est lui qui permet aux réseaux sociaux de te connaître.
- Les cercles sont les sommets (on dit aussi nœuds). Ici, les personnes.
- Les segments sont les arêtes. Ici, les relations d'amitié.
Deux sommets reliés par une arête sont dits voisins. Le degré d'un sommet est son nombre de voisins : le degré d'Alice est 2 (Bob et Chloé).
L'arête n'a pas de sens
Si Alice est amie avec Bob, alors Bob est ami avec Alice : la relation marche dans les deux sens. C'est pourquoi on trace un segment, pas une flèche. (Sur d'autres réseaux, comme les abonnements sur Instagram ou X, la relation est à sens unique : il faudrait alors des flèches. On dit que le graphe est orienté, mais ce n'est pas notre cas ici.)
Exercice - Dessiner un graphe
Voici un autre réseau. Dessine son graphe (appelons-le G2), en plaçant les sommets de façon à ce que les arêtes ne se croisent pas.
| Personne | Est ami avec |
|---|---|
| A | B, E |
| B | A, C |
| C | B, D, F |
| D | C, F |
| E | A, F |
| F | C, D, E |
Correction
Vérifie chaque ligne du tableau : A est bien relié à B et E, C est bien relié à B, D et F, etc. Il existe plusieurs dessins corrects (on peut déplacer les sommets) : ce qui compte, ce sont les arêtes, pas la position des cercles.
Exercice - Degré
Dans G2, donne le degré de chaque sommet. Quel sommet a le plus d'amis ?
Correction
A : 2 · B : 2 · C : 3 · D : 2 · E : 2 · F : 3.
C et F ont le degré maximal (3) : ce sont les plus « connectés » du groupe.
Se déplacer dans un graphe
Un chemin entre deux sommets est une suite d'arêtes qui permet d'aller de l'un à l'autre. Sa longueur est le nombre d'arêtes empruntées (attention, on ne compte pas les sommets).
La distance entre deux sommets est la longueur du plus court chemin entre eux.
Dans G2, pour aller de A à D, on peut passer par :
- A, E, F, D : 3 arêtes ;
- A, B, C, D : 3 arêtes.
Aucun chemin plus court n'existe, donc la distance entre A et D vaut 3.
Le premier chemin trouvé n'est pas le plus court
L'erreur classique est de trouver un chemin et d'annoncer sa longueur comme distance. Un chemin qui fait un détour est un chemin valide, mais ce n'est pas le plus court. Cherche toujours s'il en existe un meilleur avant de conclure.
Exercice - Distances
Dans G2 :
- Quelle est la distance entre B et F ? Donne un plus court chemin.
- Quelle est la distance entre B et D ? Donne un plus court chemin.
Correction
- B, C, F : 2 arêtes. La distance entre B et F vaut 2. (B, A, E, F ferait 3 : c'est un chemin, mais pas le plus court.)
- B, C, D : 2 arêtes. La distance entre B et D vaut 2.
Ce qu'on retient
- Un graphe représente des relations : les sommets sont les objets (ici des personnes), les arêtes sont les liens (ici des amitiés).
- Deux sommets reliés sont voisins ; le degré d'un sommet est son nombre de voisins.
- Un chemin est une suite d'arêtes ; sa longueur est le nombre d'arêtes.
- La distance entre deux sommets est la longueur du plus court chemin. Toujours vérifier qu'il n'existe pas plus court.
- La même information peut se ranger de plusieurs façons : la table cache les liens, le graphe les montre. Bien choisir sa représentation, c'est déjà résoudre une partie du problème.
Et ensuite
Tu sais lire un graphe. À la prochaine séance, on va le mesurer : quel sommet est le plus central ? Quelle est la « taille » du réseau ? Ces mesures sont exactement celles qu'utilisent les réseaux sociaux.