Les graphes en MPI demandent à la fois du vocabulaire précis, des algorithmes de parcours et une vraie rigueur de preuve. Le but n'est pas de mémoriser des dessins, mais de savoir traduire une situation en sommets, arêtes, invariants et complexité.
1. Stabiliser le vocabulaire avant les algorithmes
Un graphe est d'abord un objet formel. Selon le problème, il peut être orienté ou non orienté, pondéré ou non pondéré, simple ou avec des arcs multiples. Les sommets représentent des états, des objets ou des positions. Les arêtes représentent une relation ou une transition.
Les premières erreurs viennent souvent d'une définition floue : chemin, cycle, voisin, degré, composante connexe, forte connexité, distance, arbre couvrant. Si ces mots ne sont pas stabilisés, les preuves de parcours deviennent vite confuses.
En MPI, une définition doit être utilisable. Savoir réciter qu'un chemin est une suite de sommets ne suffit pas. Il faut aussi savoir dire ce que cette suite autorise, comment elle se compose et ce qu'elle permet de prouver sur l'accessibilité.
- Précise toujours si le graphe est orienté ou non.
- Distingue chemin, chaîne, cycle et circuit selon le cadre du cours.
- Relie chaque notion à une question algorithmique : atteindre, compter, détecter, optimiser.
2. Choisir la bonne représentation
La représentation change la manière de raisonner sur la complexité. Une matrice d'adjacence permet de tester rapidement l'existence d'une arête entre deux sommets, mais elle coûte cher en mémoire pour un graphe peu dense. Une liste d'adjacence est souvent plus naturelle pour parcourir tous les voisins.
Pour un parcours en profondeur ou en largeur, les listes d'adjacence donnent une complexité en O(|V| + |E|), car chaque sommet et chaque arête sont traités un nombre contrôlé de fois. Cette écriture est plus claire qu'un vague O(n).
Le guide sur la complexité algorithmique en prépa détaille ce réflexe : annoncer les paramètres, préciser la représentation, puis compter les opérations significatives.
3. Comprendre le parcours en largeur
Le parcours en largeur, souvent noté BFS, explore les sommets par distance croissante depuis une source. Il utilise une file : on traite d'abord les voisins immédiats, puis les voisins de ces voisins, et ainsi de suite.
L'idée de preuve importante est la couche. Quand un sommet sort de la file, sa distance depuis la source est déjà minimale parmi les chemins non pondérés. La file maintient l'ordre des distances, ce qui justifie l'utilisation de BFS pour calculer des plus courts chemins en nombre d'arêtes.
En copie, il faut éviter une justification purement visuelle. Explique que les sommets sont découverts par niveaux, que chaque arête sortante est examinée et qu'un sommet déjà découvert n'est pas réinséré inutilement.
4. Comprendre le parcours en profondeur
Le parcours en profondeur, ou DFS, suit un chemin tant qu'il peut avancer, puis revient en arrière. Il peut s'écrire récursivement ou avec une pile explicite. Son intérêt dépasse la simple visite : il sert à raisonner sur les cycles, les composantes, les ordres de fin et certaines structures de dépendance.
La difficulté vient souvent de la preuve. L'invariant n'est pas le même que pour BFS. On raisonne plutôt sur l'état des sommets, non vus, en cours d'exploration ou terminés, et sur la pile d'appels ou la pile explicite.
Pour détecter un cycle dans un graphe orienté, par exemple, il faut distinguer une arête vers un sommet terminé d'une arête vers un sommet encore en cours d'exploration. Cette nuance se perd si l'on se contente de dire que le sommet a déjà été vu.
5. Rédiger les preuves d'invariant
Une preuve de parcours doit répondre à trois questions : que garantit la structure de données, pourquoi l'algorithme termine, et pourquoi tous les sommets attendus ont été traités. Ces trois questions suffisent souvent à structurer la rédaction.
Pour la terminaison, on utilise le fait qu'un sommet change d'état un nombre fini de fois et qu'on n'ajoute pas indéfiniment les mêmes sommets. Pour la correction, on montre que chaque découverte correspond à une vraie arête du graphe et que tout sommet accessible finit par être atteint.
Ce type de preuve rejoint les raisonnements vus dans les automates en MPI : on définit un état, on explicite l'invariant, puis on montre qu'il est conservé par les transitions.
6. Réviser les graphes sans apprendre des dessins
Les dessins aident à comprendre, mais ils ne suffisent pas pour réviser. Après un exercice, note le point qui a bloqué : définition de connexité, choix de BFS plutôt que DFS, représentation, invariant, complexité ou condition de cycle.
Les flashcards d'informatique prépa peuvent servir à stabiliser le vocabulaire, les propriétés de parcours et les schémas de preuve. Elles ne remplacent pas l'écriture d'un algorithme ni la vérification sur un graphe concret.
Pour organiser l'ensemble de l'informatique MPI, l'article sur la spécialité informatique en MPI donne un cadre plus large : preuves, algorithmique, graphes, automates et programmation doivent rester reliés.
Stabilise les repères d'informatique MPI
PSD aide à revoir les définitions, parcours, complexités et idées de preuve avec des flashcards adaptées à la prépa scientifique.
Conclusion
Le bon usage de ce chapitre tient à une méthode simple : poser les définitions, vérifier les conventions, puis relier chaque résultat à un exercice ou à une preuve. C'est cette régularité qui rend la révision plus fiable.
Garde les flashcards pour les repères qui doivent revenir vite, et garde les exercices pour apprendre à choisir, rédiger et contrôler. Les deux formats se complètent, mais ils ne jouent pas le même rôle.
Questions fréquentes
Sources et références
- Ministère de l'Éducation nationale, Bulletin officiel, programmes de la filière MP2I et MPI.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C., Introduction to Algorithms, MIT Press, 4e édition, 2022.
- Sedgewick, R. et Wayne, K., Algorithms, Addison-Wesley, 4e édition, 2011.
- MIT OpenCourseWare, 6.006 Introduction to Algorithms, Massachusetts Institute of Technology.