Titre : PHOEG helps obtaining extremal graphs

Conférencier : Hadrien Mélot – Université de Mons, Belgique 

Résumé : L'objectif de la théorie extrémale des graphes est de déterminer des bornes sur des invariants ainsi que les graphes qui atteignent ces bornes. Certains invariants sont difficiles à calculer et il peut être complexe, pour un humain, de développer des intuitions sur leur influence sur la structure des graphes.

Il y a donc un besoin d'outils pour aider les chercheurs à explorer les subtilités de ces invariants. Il existe déjà plusieurs tentatives d'atteindre ce but, e.g., Graph, GrInvIn, Graffiti, AutoGraphiX, Digenes, GraPHedron. Cependant, ces outils ne rencontrent pas pleinement nos besoins pour obtenir des graphes extrêmes de façon exacte et pour explorer les transformations de graphes. Être capable de faire des requêtes rapides sur des invariants de graphes est également une fonctionnalité intéressante pour rapidement approfondir ou abandonner une idée lors d'une discussion de recherche, e.g., 'quels graphes sont des minima locaux pour une transformation et un invariant donnés ?' ou 'pour quels graphes connexes deux invariants donnés ont-ils les mêmes valeurs ?'

Dans le but de répondre à de telles questions, nous sommes en train de développer le système Phoeg, qui peut être vu comme un successeur de GraPHedron. Il utilise une grande base de données de graphes et travaille avec l'enveloppe convexe de graphes vu comme des points dans l'espace des invariants. De cette façon, il permet de déterminer de manière exacte les graphes extrêmes (de petit ordre) et d'inférer des bornes optimales sur les invariants. Cette base de données permet également de réaliser des requêtes sur les graphes. Phoeg va un pas plus loin en assistant le processus de conception de preuves guidées par l'application successive de transformations de n'importe quel graphe vers un graphe extrême.

Entrée gratuite.
Bienvenue à tous!