Annales sur Graphes et arbres

Graphes et arbres

Au programme

Les graphes et arbres sont au programme d'informatique commune (MP, PC, PSI) et MPI : représentations (matrice d'adjacence, listes), parcours (largeur BFS, profondeur DFS), arbres binaires, arbres de recherche, et algorithmes sur les graphes (plus court chemin, connexité). La MPI développe une théorie plus approfondie ; en MP/PC/PSI, le chapitre reste centré sur les implémentations.

Pourquoi c'est testé

36 sujets de concours dans notre base mobilisent les graphes et arbres. Présents en Info A X-ENS MP (récurrent), Info Mines-Ponts MP, S2I CCINP MP (chaînes de transmission), Info X-ENS PSI. Les pièges récurrents pointés par les jurys :

• Ne considérer que les arbres peignes : sous-cas non général (jury Info A X-ENS MP 2022 : « Beaucoup de candidats n'ont considéré que les arbres de multiplication qui sont des peignes (c'est-à-dire que chaque nœud interne est nécessairement relié à une feuille). Cette erreur a généralement impacté tout le reste de la partie »)
• Coût de deux opérations confondu avec produit des coûts (jury Info A X-ENS MP 2022 : « De trop nombreux candidats pensent que le coût pour effectuer deux multiplications de matrice est le produit des coûts pour effectuer chacune d'elles »)
• Résultats non justifiés notés zéro (jury Maths 2 Mines-Ponts MP 2024 : « Que les candidats sachent que toute réponse non justifiée, même juste, a en général obtenu la note 0 : on ne donne pas de points au bénéfice du doute »)
• Notation ~ ambiguë entre similitude et équivalence (jury Maths 2 Mines-Ponts MP 2024 : « Utiliser ∼ pour désigner la similitude entre matrices est porteur de confusion avec l'équivalence entre matrices, et la signification de cette notation doit donc être précisée dans la copie dès sa première utilisation »)

Comment réviser

Trois axes priorisés :

1. Maîtriser BFS et DFS : pseudo-code, complexité, invariant, application à la connexité et au plus court chemin (non pondéré). 2. Ne jamais traiter un cas particulier comme s'il était général — vérifier que l'arbre/graphe n'est pas plus complexe. 3. Travailler les sujets de référence : Info A X-ENS MP 2022-2025 (arbres et coûts), Info X-ENS PSI 2023, Maths 2 Mines-Ponts MP 2024 (probabilités sur graphes).