Comparaison de graphes, applications à l'étude d'un réseau de sociabilité paysan au Moyen Age
Institution:
Toulouse 2Disciplines:
Directors:
Abstract EN:
The aim of this thesis is to compare graphs with algebraic tools (especially eigenelements of some graph matrices). A first aspect of this graph comparison is the study of a medieval social network. The eigenelements of the Laplacian matrix enable us to highlight some communities; by coupling this result with statistical methods it is possible to obtain a simplified representation of the network. The comparison of two medieval networks (for instance before and after the Hundred Years' war) can then be done by comparing the two simplified representations. Comparing two graphs by knowing only their spectra (for a given matrix, adjacency or Laplacian for example) raises the question of whether two graphs with the same spectrum are isomorphic. In other words: "Which are the graphs determined by their spectrum ?". At the moment, only few graphs have been proved to answer this question and finding new families of graphs determined by their spectrum will provide new elements of reply. In this thesis we expose a new way to count the closed walks on a graph which is relevant to show the non-cospectrality (for the adjacency matrix) of two given graphs. Then new classes of graphs determined by their spectrum are shown.
Abstract FR:
L'objectif de cette thèse est de comparer des graphes à l'aide d'outils algébriques (en particulier les éléments propres de matrices associées au graphe). Un premier aspect de cette comparaison de graphes est l'étude d'un réseau social entre paysans au Moyen Age. Les éléments propres du Laplacien nous permettent de mettre en évidence certaines communautés ; en couplant ce résultat à une étude métrologique et des méthodes statistiques on peut obtenir une représentation simplifiée du réseau. La comparaison de deux réseaux peut alors passer par la comparaison des deux représentations obtenues. Comparer deux graphes en connaissant uniquement leurs spectres (pour une matrice donnée, adjacence ou Laplacien par exemple) soulève la question de savoir si deux graphes possédant le même spectre sont isomorphes. En d'autres termes : "Quels sont les graphes déterminés par leur spectre ?". A l'heure actuelle, on ne connaît que peu de graphes répondant à cette question et trouver de nouvelles familles de graphes déterminés par leur spectre permet d'apporter de nouveaux éléments de réponse. Dans cette thèse nous exposons une méthode de dénombrement de marches fermées sur un graphe permettant de montrer la non-cospectralité (pour la matrice d'adjacence) de deux graphes donnés. Ensuite de nouvelles classes de graphes déterminés par leur spectre sont montrées.