# 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.

- 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%