La théorie des graphes est une extension de la théorie des ensembles qui constitue un outil de modélisation très puissant pour l'ingénieur. Ce cours permet de se familiariser avec les notions de base importantes en théorie des graphes, et avec des problèmes d'optimisation qui apparaissent dans le contexte des graphes.
Une première partie du cours aborde les graphes orientés et non orientés, leurs représentations numériques sous forme de matrices ou de tableaux, les notion de planarité, connexité, isomorphisme de graphes, ainsi que des graphes particuliers : arbres, chemins, chaînes, graphes bipartis, cliques...
La seconde partie du cours se concentre sur les problèmes d'optimisation dans les graphes et leurs applications : arbres couvrants de poids minimal, plus courts chemins et application au problème central de l'ordonnancement, flots de valeur maximale.
- Enseignant: Knippel Arnaud
- Enseignant (simple): Mace De Gastines Etienne