100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Louis Funar

De la complexité des plans de tables. (ou comment la résolution d'un casse tête simple ouvre des horizons mathématiques insoupçonnés).

Mardi, 18 Octobre, 2005 - 18:30
Prénom de l'orateur : 
Vincent
Nom de l'orateur : 
DESPIEGEL
Résumé : 

Soit 2n personnes invitées à un banquets. Chacun connaît exactement 3 personnes (précision: il s'agit de 3 personnes en dehors de soi-même et il s'agit d'une relation symétrique (si A connaît B alors B connaît A.)). On sait qu'il existe un plan de table (circulaire) tel que chaque convive soit assis à coté de 2 personnes qu'il connaît. Alors, il existe un autre plan de table possible, que l'on ne peut obtenir à partir du premier par symétrie ou par rotation.

Ce sera l'occasion d'une introduction à la théorie des graphes, d'un survol de la notion de graphe hamiltonien (ie: qui admettent des circuits passant une et une seule fois par chaque sommet du graphe) avant d'arriver à une solution du problème à proprement parler.

Thème de recherche : 
Compréhensible
Salle : 
1 tour Irma
logo uga logo cnrs