Master Informatique - Université de Bordeaux

Responsables : Éric Sopena et Marthe Bonamy.

Ce cours du semestre 9 est obligatoire pour AM et en option pour VL. Il vaut 3 ECTS.

La théorie des graphes est un modèle très général qui permet de représenter des problèmatiques très variées, que ce soit dans les réseaux (de toute nature) mais aussi pour des structures hierarchisées comme les bases de données. La culture générale des problématiques de graphe que nous proposons dans ce cours ainsi que la connaissance des outils efficaces pour ces problématiques sont des atouts pour reconnaître et traiter les problèmes qu'elles modélisent.

Cet enseignement présente des notions avancées de théorie des graphes et familiarise l’étudiant avec certaines techniques de preuve classiques, liées notamment à la coloration de graphes. Quelques problèmes et conjectures classiques sont abordés.

—

Graph theory is a very general model that can represent various problems, from networks (of any kind) to hierarchical structures such as data bases. The general knowledge of graph theory we provide in this course is useful for recognising and dealing with the problems it modelizes.

This teaching presents advanced notions of graph theory and faces the student with some classical proof techniques on graphs, illustrated in particular on graph coloring . Some classical problems and conjecture are also presented.