Graphes, domination et identification

Graphes, domination et identification

L’objectif de ce cours est d’introduire la notion de graphe. Un graphe est composé d’un ensemble d’objets (appelés sommets) dont certains sont reliés entre eux.

Ces liaisons sont appelées arêtes. Les graphes sont un outil puissant pour la modélisation et sont cachés partout : on peut construire le graphe d’un réseau social (les sommets sont les personnes, les arêtes sont les amitiés entre deux personnes), d’un bâtiment (les sommets sont les pièces, les arêtes relient les pièces qui communiquent), d’une ville,…

Nous aborderons quelques aspects généraux sur les graphes avant de nous concentrer sur la notion de domination où l’on cherche un ensemble minimal de sommets qui est relié à tout le graphe. Nous montrerons certains résultats sur cette thématique et énoncerons des problèmes qui sont encore ouverts.

Les deux sujets de recherche proposés tournent autour de la notion d’identification, proche de celle de la domination. Il s’agit de bien choisir des sommets pour que chaque sommet du graphe soit unique par rapport à l’ensemble choisi.

Ces problèmes permettent par exemple de modéliser la détection d’incendie dans un bâtiment ou la localisation dans un espace représenté par un graphe.

Aline Parreau est chargée de recherche au CNRS au laboratoire LIRIS à Lyon. Elle étudie les mathématiques discrètes et s’intéresse en particulier à la théorie des graphes et aux jeux combinatoires. Elle intervient dans des actions de médiation avec MATh.en.JEANS et Maths à Modeler.

Michaela et Diego nous parlent de la conférence

Suivez-nous :

Les commentaires sont clos.
Facebook
Facebook
RSS