Graphes au lycée

La théorie des graphe est une démarche mathématique de résolution de problèmes qui connaît aujourd'hui de nombreux développements grâce à l'informatique. On distingue dans cette démarche trois étapes :

• montrer qu'il y a une ou plusieurs solutions possibles à un problème posé ;
• montrer que cette solution est calculable à l'aide d'un algorithme que l'on pourra programmer ;
• s'assurer que cet algorithme est efficace : qu'il conduit à la solution dans un temps de calcul raisonnable qui n'augmente pas de façon exponentielle en fonction du nombre de paramètres.

Cette dernière étape est un domaine de recherche mathématique qui s'est développé depuis 1935 à partir des travaux de K. Gôdel, A. Church et A. Turing.

Parmi la variété de problèmes abordés et résolus par l'étude des graphes, on trouve en particulier les problèmes de dénombrement, de coloriage, les problèmes de cheminement sur un graphe et les problèmes de graves probabiliste et Marco vient point c'est sur ces problèmes que notre groupe s'était forcé de rechercher les réponses argumentées au cours de cette année d'introduction de ce nouvel enseignement, au lycée, dans la série économique et sociale.