Initiée par Euler, avec le célèbre Problème des 7 ponts de Konigsberg, les applications de la théorie des graphes et de la recherche opérationnelle sont aujourd'hui immenses tant au plan civil que militaire : aide à la décision, stratégie, optimisation (plus court chemin, coût minimal), réseaux de transports, etc.

 La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets, et d'arêtes entre ces sommets ; ces arêtes sont appelées, dans les graphes orientés, des arcs.

Public cible: deuxième année informatique

Objectifs du cours

Le cours "Théorie des graphes " est destiné aux étudiants de deuxième année informatique, il vise à :

• Résoudre de nombreux problèmes concrets,
• Représenter plusieurs situations par des graphes tels que réseaux routiers, processus à étapes, automates finis, etc.

A l'issu de ce cours, l'apprenant ou l'étudiant sera capable de :

• Modéliser et schématiser des situations réelles par des graphes pour ensuite les résoudre
• Résoudre plusieurs problèmes pratiques tels que les feux tricolores avec le moyen de coloration dans les graphes
• Connaitre les outils de base pour l'optimisation combinatoire