Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones

Sommets et arêtes, degrés, matrice d’adjacence, chemins et composantes, BFS et Dijkstra, arbres, arbre couvrant minimal et graphe de calcul d’un neurone — le tout sur un seul graphe de sept villes.

14 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 8 sur 52

1. Carte de l’intelligence artificielle : qu’est-ce qui est quoi et comment tout s’emboîte
2. Brève histoire de l’intelligence artificielle : de Turing aux modèles de langage
3. Données, modèle, entraînement, inférence : les notions de base sur un seul exemple
4. Lire la notation mathématique : symboles, indices, sommes et quantificateurs
5. Ensembles et relations : les briques dont sont faites les définitions en IA
6. Fonctions et applications : pourquoi tout modèle d’IA est une fonction
7. Logique et démonstrations : les règles selon lesquelles on raisonne en IA
8. Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones
9. Algèbre linéaire pour l’apprentissage automatique : vecteurs, matrices et pourquoi l’IA multiplie surtout
10. Dérivées, gradient et règle de dérivation en chaîne : comment un modèle sait dans quelle direction apprendre
11. Descente de gradient : comment un modèle apprend
12. Qu’est-ce que la probabilité : du lancer de dé aux axiomes de Kolmogorov
13. Probabilité conditionnelle et théorème de Bayes : comment réviser une estimation quand on apprend du nouveau
14. Variable aléatoire et fonction de répartition : une seule fonction qui dit tout de la loi
15. Fonction de densité et fonction de masse : pourquoi une variable continue a une probabilité nulle en chaque point
16. Espérance, variance et covariance : où se situe une loi, quelle est sa largeur et ce qui varie avec quoi
17. Panorama des lois de probabilité : Bernoulli, binomiale, Poisson, uniforme, normale et exponentielle
18. Loi des grands nombres et théorème central limite : pourquoi les moyennes sont si prévisibles
19. Statistique et estimation de paramètres : maximum de vraisemblance, MAP et intervalles de confiance
20. Théorie de l’information : entropie, entropie croisée et divergence KL — d’où viennent les fonctions de perte
21. Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations
22. Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search
23. Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques
24. Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts
25. Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA
26. Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques
27. Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée
28. Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler
29. Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court
30. Optimisation par essaim de particules : inertie, expérience propre et expérience de l’essaim
31. Neuroévolution : faire évoluer les poids et la forme des réseaux de neurones, et l’algorithme NEAT
32. Ensembles flous et fonctions d’appartenance : comment écrire « un peu chaud »
33. Logique floue et probabilité : pourquoi « un peu chaud » ne veut pas dire « probablement chaud »
34. Logique floue : t-normes, implications et règles SI–ALORS
35. Commande floue : Mamdani et Sugeno, du ventilateur au pendule inversé sur un chariot
36. Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters
37. Systèmes neuro-flous (ANFIS) : des règles floues qui apprennent à partir des données
38. Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank
39. Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête
40. Réseaux bayésiens : pourquoi l’herbe est mouillée et ce que cela implique pour l’arroseur
41. Le filtre de Kalman : comment estimer, à partir de mesures imprécises, où se trouve une voiture et à quelle vitesse elle roule
42. Types d’apprentissage automatique : supervisé, non supervisé, semi-supervisé et plus
43. Prompts, contexte et RAG : comment donner au modèle les bonnes informations
44. Autoencodeurs variationnels (VAE) : de nouvelles images à partir d’un espace latent continu
45. Réseaux antagonistes génératifs (GAN) : le faussaire contre le détective
46. Modèles de diffusion : comment une image naît du bruit pur
47. Processus de décision markoviens : états, actions, récompenses et équations de Bellman
48. Q-learning et DQN : apprendre la valeur des actions, du tableau au réseau de neurones
49. Policy gradient et PPO : apprendre directement la politique
50. Comment fonctionne un agent IA : un modèle de langage en boucle avec des outils
51. Programmer avec des agents IA : consigne, tests et vérification
52. Évaluation et sécurité des systèmes d’IA : comment mesurer et comment surveiller

Programme complet de la série 52 sur 83 sujets publiés

Une carte de villes et de routes, un réseau d’amis, l’espace d’états d’un jeu, un réseau de neurones, et même le calcul dans lequel on obtient le gradient — tout cela est un graphe : des points reliés par des traits. Les graphes sont la structure la plus universelle de l’informatique, et en intelligence artificielle vous les rencontrerez à chaque pas. Les arbres en sont le cas particulier le plus simple et le plus utile.

Toute cette partie repose sur un seul graphe : sept villes de A à G et des routes avec leur longueur. Nous y montrerons pas à pas les degrés, la façon de stocker un graphe, les plus courts chemins et l’arbre couvrant minimal.

1. Qu’est-ce qu’un graphe

Définition — graphe

Un graphe est un couple G = (V, E), où V est un ensemble fini de sommets et E un ensemble d’arêtes.

Dans un graphe non orienté, une arête est un ensemble à deux éléments {u, v} ; dans un graphe orienté, c’est un couple (u, v) — une flèche de u vers v. Un graphe orienté est donc une relation sur V.

Un graphe pondéré possède en plus une fonction w : E → ℝ, qui associe à chaque arête un poids (longueur, coût, durée).

2. Degré d’un sommet

Définition — degré et lemme des poignées de main

Le degré deg(v) d’un sommet v est le nombre d’arêtes qui en partent.

Théorème (lemme des poignées de main). Dans tout graphe non orienté, ∑_{v ∈ V} deg(v) = 2 |E|.

La somme des degrés vaut 2 + 4 + 4 + 4 + 4 + 4 + 2 = 24 et il y a 12 arêtes — exactement comme le dit le théorème. Le degré a un sens pratique : dans un réseau social, c’est le nombre d’amis, sur le Web, le nombre de liens, et les sommets de grand degré sont souvent les plus importants.

3. Comment stocker un graphe dans un ordinateur

Un ordinateur ne voit pas d’image, il lui faut des nombres. Deux représentations sont courantes :

• Matrice d’adjacence — un tableau |V| × |V| ; la case (u, v) contient le poids de l’arête, ou 0. La question « y a-t-il une arête ? » est rapide, mais la mémoire croît comme |V|².
• Liste d’adjacence — pour chaque sommet, la liste de ses voisins. La mémoire ne croît que comme |V| + |E|, ce qui fait une énorme différence pour les graphes creux (réseau social, carte).

La matrice est symétrique par rapport à la diagonale — c’est la marque d’un graphe non orienté. En IA, la matrice d’adjacence sert aux réseaux de neurones sur graphes, qui apprennent directement sur des graphes (molécules, réseaux sociaux, réseau routier).

4. Chemins, cycles et connexité

Définition — chemin, cycle, connexité

Un chemin de u à v est une suite de sommets deux à deux distincts u = v₀, v₁, …, v_k = v, où deux sommets consécutifs sont toujours reliés par une arête. Sa longueur est k (le nombre d’arêtes), ou la somme des poids dans un graphe pondéré.

Un cycle est un chemin qui revient à son sommet de départ (au moins trois arêtes).

Un graphe est connexe si un chemin relie deux sommets quelconques. Les parties connexes maximales d’un graphe sont ses composantes connexes — et « être dans la même composante » est une équivalence, donc les composantes forment une partition de V.

5. Plus courts chemins

La question « comment aller le plus vite de A à G » est la recherche d’un plus court chemin — exactement ce que faisaient les algorithmes de la partie sur la recherche dans l’espace d’états. Mais tout dépend de ce que l’on mesure.

Si ce qui compte est le nombre d’arêtes, le parcours en largeur suffit : d’abord les voisins de A, puis leurs voisins… Le nombre au-dessus d’un sommet est sa distance à A en arêtes :

Trois arêtes mènent à G (par exemple A–B–E–G). Mais si l’on compte la longueur des routes, il faut l’algorithme de Dijkstra — il repart toujours du sommet non encore fermé le plus proche. Le nombre au-dessus d’un sommet est maintenant la plus courte distance en kilomètres, et le plus court chemin vers G est mis en évidence :

Le plus court chemin A–B–D–E–G a quatre arêtes, donc plus que le chemin à trois arêtes trouvé par BFS, mais une longueur de seulement 12. Le chemin A–B–E–G mesurerait 4 + 7 + 3 = 14. Moins d’étapes ne veut pas dire un chemin plus court — c’est exactement la différence entre BFS et UCS que nous avons vue sur le labyrinthe avec de la boue.

6. Arbres

Définition — arbre et arbre enraciné

Un arbre est un graphe connexe sans cycle. Une forêt est un graphe sans cycle (chacune de ses composantes est un arbre).

Théorème. Pour un graphe à n sommets, les propriétés suivantes sont équivalentes : (1) c’est un arbre ; (2) il est connexe et a n − 1 arêtes ; (3) il est sans cycle et a n − 1 arêtes ; (4) entre deux sommets quelconques passe exactement un chemin.

Un arbre enraciné a un sommet distingué, la racine. Les voisins d’un sommet situés à l’opposé de la racine sont ses enfants, un sommet sans enfant est une feuille, et la profondeur d’un sommet est la longueur du chemin depuis la racine.

En IA, les arbres sont partout. Un arbre de décision classe par une série de questions, de la racine jusqu’à une feuille. Les algorithmes de recherche construisent un arbre de recherche — l’arbre de BFS et de DFS de la partie sur la recherche, c’est exactement cela. Et un programme d’échecs calcule un arbre de jeu, dont les sommets sont des positions et les arêtes des coups.

7. Arbre couvrant minimal

Définition — arbre couvrant et algorithme de Kruskal

Un arbre couvrant d’un graphe connexe G est un sous-graphe qui contient tous les sommets de G et qui est un arbre. Un arbre couvrant minimal a la plus petite somme des poids de ses arêtes.

Algorithme de Kruskal : trier les arêtes par poids croissant, puis ajouter successivement chaque arête qui ne crée pas de cycle. C’est un algorithme glouton, et pourtant il trouve toujours l’optimum.

L’arbre couvrant a 6 arêtes pour 7 sommets — exactement n − 1, comme le dit le théorème sur les arbres — et une longueur totale de 18. L’algorithme a rejeté les six routes restantes, parce qu’elles auraient créé un cycle.

8. Graphes acycliques et calcul d’un réseau de neurones

Définition — DAG et ordre topologique

Un graphe orienté acyclique (DAG) est un graphe orienté sans cycle orienté.

Un ordre topologique est un rangement des sommets tel que chaque arête (u, v) va de gauche à droite — u est avant v. Théorème. Un graphe orienté admet un ordre topologique si et seulement s’il est acyclique.

C’est ainsi que calcule tout réseau de neurones. Voici le calcul d’un seul neurone ŷ = σ(w · x + b) et de son erreur L(ŷ, y) sous forme de graphe de calcul : les entrées à gauche, les opérations comme sommets, les flèches montrent ce qui dépend de quoi. Les nombres donnent l’ordre topologique :

Le réseau calcule vers l’avant dans l’ordre topologique — d’abord le produit, puis la somme, la sigmoïde et l’erreur. Et quand il apprend, il parcourt le même graphe à rebours : la rétropropagation de l’erreur (backpropagation) visite les sommets dans l’ordre topologique inverse et applique en chacun la règle de dérivation en chaîne. Des bibliothèques comme PyTorch construisent elles-mêmes ce graphe à chaque calcul. Au passage, le graphe des dépendances entre modules dans le plan de cette série est lui aussi un DAG.

9. Les graphes en intelligence artificielle

• L’espace d’états est un graphe : les états sont les sommets, les actions des arêtes avec un coût. Chercher, c’est trouver un chemin dans un graphe.
• Les graphes de calcul des réseaux de neurones sont des DAG ; l’entraînement est un aller-retour à travers eux.
• Les graphes de connaissances stockent des faits sous forme d’arêtes « Prague — est la capitale de — Tchéquie », et les moteurs de recherche en tirent leurs réponses.
• Les réseaux bayésiens sont des DAG de dépendances probabilistes — nous y viendrons dans le module sur les modèles probabilistes.
• Les réseaux de neurones sur graphes apprennent directement sur des graphes : ils prédisent les propriétés de molécules, le trafic ou des recommandations.

10. Résumé

• Un graphe est un ensemble de sommets et d’arêtes ; les arêtes peuvent avoir une direction et un poids. La somme des degrés est le double du nombre d’arêtes.
• On stocke un graphe par une matrice d’adjacence ou par des listes d’adjacence — bien plus économes pour les graphes creux.
• BFS trouve le chemin avec le moins d’arêtes, Dijkstra le plus court selon les poids — et ce n’est pas forcément le même.
• Un arbre est un graphe connexe sans cycle à n − 1 arêtes ; l’arbre couvrant minimal se trouve avec l’algorithme glouton de Kruskal.
• Un réseau de neurones est un DAG de calcul : vers l’avant, on calcule dans l’ordre topologique, le gradient à rebours.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.