Groupe d’études et de recherche en analyse des décisions

House of Graphs : Quels sont les graphes intéressants ?

Hadrien Mélot Université de Mons, Belgique

Plusieurs livres rassemblent des exemples ou des contre exemples de graphes qui apparaissent fréquemment ou jouent un rôle particulier en théorie des graphes. De plus, les systèmes de découverte assistée par ordinateur en théorie des graphes (comme AutoGraphiX, Graffiti ou GraPHedron permettent l'identification de graphes particuliers apparaissant comme intéressants (ou appropriés) pour un problème donné (e.g., graphes extrémaux ou contre exemples). Nous partons de l'hypothèse suivante : il y a très peu de graphes intéressants parmi le nombre très important de graphes. En d'autres mots, nous pensons que quelques graphes ou classes de graphes apparaissent très fréquemment dans de nombreux problèmes différents en théorie extrémale des graphes.

Nous proposons une méthode permettant d'identifier un ensemble initial de graphes intéressants en générant et résolvant un ensemble de problèmes de manière totalement automatisée (en utilisant le système GraPHedron). En outre, nous avons conçu un prototype d'une interface web destinée aux chercheurs, et baptisée "House of Graphs". Cet outil peut être vu comme un dépôt de graphes intéressants et de listes complètes de certaines classes de graphes, ainsi qu'une plateforme permettant d'obtenir et de partager des information à leur propos.

(En collaboration avec G. Brinkmann, K. Coolsaet et J. Goedgebeur)