Graph theory and operational research


Teacher coordinatorGéraldine Del Mondo
Teacher(s)Géraldine Del Mondo
TeachingLectures : 10.5h Exercises : 10.5h
Web site

Aim and objective

The main objective is to acquire basic knowledge in graph theory and operational research. This course aims to put in perspective classic problems of operational research and research-oriented issues, in particular by presenting current research projects on the subject of graphs.

  • This EC aims to :
    • Know how to go from a real problem to a problem modeled by graph theory
    • Know how to use graph properties to solve a problem
    • Know how to evaluate the complexity of a problem
  • Outcome learning

    • INSA reference data :
      • Optimiser un modèle [3P]
      • Déterminer des classes de problèmes [2P]
    • CNISF reference data :
      • J10C [2I]
      • J10G [2I]
      • J10Q [1P]
    1 - Notion, 2 - Concept, 3 - Application, I - fully, P - incomplete

    Course description

    • Graphs, graph properties, modelisation by graph
    • Graph coloring
    • Spatial graphs
    • Computer representation of a graph
    • Initiation in complexity theory




    • Algorithmes de graphes, P. Lacomme, C. Prins, M. Sevaux, Eyrolles, 2003.
    • Introduction to graph theory, D. B. West, Pearson, 2001
    • Faure R., Précis de Recherche Opérationnelle, Dunod Décision


    • Final exam : 80%, project and/or other continuous control : 20%