Couplages dans les graphes

video: https://mediakiosque.univ-pau.fr/avc/courseaccess?id=2289 transparents: http://vulgarisation.xavierviennot.org/Colleges_et_Lycees_files/Pau14.pdf National audience De combien de façons peut-on couvrir un échiquier avec des dominos ? Voici un problème typique de dénombrement de pavages, qui so...

Full description

Bibliographic Details
Main Author: Viennot, Xavier Gérard
Other Authors: Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Format: Conference Object
Language:French
Published: HAL CCSD 2014
Subjects:
Online Access:https://hal.archives-ouvertes.fr/hal-00998357
Description
Summary:video: https://mediakiosque.univ-pau.fr/avc/courseaccess?id=2289 transparents: http://vulgarisation.xavierviennot.org/Colleges_et_Lycees_files/Pau14.pdf National audience De combien de façons peut-on couvrir un échiquier avec des dominos ? Voici un problème typique de dénombrement de pavages, qui sont en fait des couplages parfaits dans un graphe. D'une manière générale, un couplage d'un graphe est la donnée d'un ensemble d'arêtes dont les extrémités sont disjointes deux à deux. Lorsque tous les sommets du graphe sont couverts, le couplage est dit parfait. Je montrerai des "formules" remarquables donnant le nombre de couplages parfaits de certains graphes, en particulier le graphe associé à un "échiquier" ayant m lignes et n colonnes. Curieusement, ce genre de formule résoud un modèle introduit en physique pour étudier le ferromagnétisme. Si l'on change le graphe "échiquier" en d'autres réseaux, comme le diagramme dit "Aztèque", des formules très simples et stupéfiantes apparaîssent. Certains dénombrements de couplages partiels permettent de retrouver des formules "scolaires" de trigonométrie sur les sinus et cosinus. C'est la "philosophie" de la combinatoire actuelle: des preuves "visuelles" évitant des calculs compliqués. Enfin, avec le "théorème du cercle arctique", je donnerai un aperçu de recherches récentes en combinatoire sur des couplages aléatoires du diagramme Aztèque, associant combinatoire, algorithmes, probabilités, physique statistique et mathématiques visuelles.