Le prochain séminaire du laboratoire CEDRIC aura lieu le mercredi 28 mai prochain à partir de 14h. Il sera organisé par l’équipe OC, et les deux orateurs seront Christophe Picouleau et Dimitri Watel (salle à préciser).
Titre : De la reconstruction de graphes et hypergraphes.
Résumé : De nombreux problèmes consistent à vouloir reconstruire une structure, ici un graphe ou un hypergraphe, à partir d’une information partielle concernant cette structure. Parmi ces informations citons de manière non exhaustive : des projections de matrices d’adjacentes, des séquences de degrés, la structure complète ou non des voisinages de sommets ou d’arêtes. On peut voir cette information partielle comme une requête sur le graphe, ou comme une connaissance imparfaite car vue à travers une transformation du graphe. Nous allons monter deux exemples caractéristiques de tels problèmes.
Le premier consiste, connaissant une information partielle provenant d’un (hyper)graphe, à déterminer s’il existe au moins deux (hyper)graphes qui peuvent correspondre à ces informations. Par exemple, deux graphes k-réguliers de même taille donneront la même séquence des degrés, il n’y a donc pas unicité dans ce cas. On dit qu’il ne sont pas reconstructibles de manière unique par la requête « séquence des degrés ». La reconstruction de manière unique est importante car elle assure que l’information, même partielle, est suffisante pour reconstruire tout le graphe sans ambiguïté. La présentation se concentrera sur un type de requête bien particulier: pour chaque triplet de sommets d’un graphe, nous savons si un des trois est relié aux deux autres, mais que ces deux autres ne sont pas reliés. Autrement dit, ces 3 sommets forment une chaîne. Nous expliquerons les idées clefs permettant de déduire les graphes reconstructibles de manière unique pour cette requête.
Le second consiste, connaissant une information partielle, à déterminer s’il existe au moins un (hyper)graphe qui correspond à ces informations. Etant donné un hypergraphe le graphe d’intersection de ses hyperarêtes a pour ensemble sommets les hyperarêtes et deux sommets sont reliés si les deux hyperarêtes s’intersectent. Ceci généralise la notion de line-graphe pour le cas des graphes simples. Le problème de reconstruction associé consiste alors, étant donné un graphe décider s’il peut-être le graphe d’intersection d’un hypergraphe. Pour le cas de line-graphes le problème est bien résolution, à la fois structurellement et algorithmiquement. Il en va tout autrement pour les hypergraphes même dans le cas d’hypergraphes 3-uniformes (chaque hyperarête contient 3 sommets). Nous donnerons quelques résultats de nature algorithmique pour les graphes de 2-intersection (intersection par au moins 2 sommets) d’hypergraphes 3-uniformes.
.