Graph theory and operational research

Information

Teacher coordinator	Géraldine Del Mondo
Teacher(s)	Géraldine Del Mondo
Language	English
Credits	2.5
Teaching	Lectures : 10.5h Exercises : 10.5h
Web site	http://moodle.insa-rouen.fr/course/view.php?id=124

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

Prerequisites

Algorithmic

Bibliography

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

Assessment

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