Problèmes de réalisabilité et de connexité dans les graphes chimiques

Cette maîtrise s'inscrit dans le domaine de la chimie mathématique, et plus précisément le domaine de la théorie des graphes chimiques. Ce domaine est en pleine expansion depuis les travaux de William Cullen en 1758. Plusieurs invariants chimiques liés à la théorie des graphes ont été étudiés tels que l'indice de Randic, ainsi que le premier et le second indice de Zagreb. On les regroupe aujourd'hui sous le nom d'indices Adriatiques. Plusieurs modèles mathématiques ont été développés pour déterminer des bornes inférieures et supérieures pour ces invariants chimiques, ainsi que les graphes extrêmes correspondants. Ces modèles ne prennent pas en compte la connexité des graphes, en ce sens qu'aucune contrainte de connexité n'est imposée sur les graphes extrêmes générés. Nos recherches ont porté sur le développement d'un algorithme capable de générer des graphes extrêmes simples (c'est-à-dire sans boucle ni arête multiple) et connexes atteignant la kème plus petite ou la plus grande valeur des indices Adriatiques (k ≥ 1). Pour ce faire, nous avons déterminé des conditions nécessaires et suffisantes pour l'existence d'un graphe simple et connexe lorsque pour toute paire i, j d'entiers strictement positifs, on impose le nombre mij d'arêtes reliant les sommets de degré i à ceux de degré j. Nous avons ensuite montré qu'il est possible d'imposer ces conditions à l'aide d'un modèle linéaire en nombres entiers. Puis, nous avons utilisé ce modèle mathématique pour déterminer les valeurs extrêmes de plusieurs indices Adriatiques pour plusieurs familles de graphes, et nous avons finalement montré comment il est possible de générer les graphes qui atteignent ces valeurs. Mots clés : graphes chimiques, invariants adriatiques, programmation linéaire en nombres entiers, problèmes de connexité.

Abstract

This research lies is in the field of mathematical chemistry, and more specifically in the area of the theory of chemical graphs. This domain is in full expansion since the early works of William Cullen in 1758. Several graphical chemical invariants have been studied such as the Randic index, and the first and second Zagreb index. These invariants are known today as the Adriatic invariants. Several mathematical models have been developed to determine lower and upper bounds for these chemical invariants, as well as their corresponding extreme graphs. However, these models do not take connexity constraints into account, in that sense that it is not imposed that the generated extreme graphs should be connected. The main objective of my research was to develop an algorithm able to generate extreme simple (i.e., without loops of multiple edges) and connected graphs that reach the kth smallest ou largest value of Adriatic invariants (k ≥ 1). For this purpose, we have first determined necessary and sufficient conditions for the existence of a simple connected graph when for every pair i, j of striclty positive integers, it is imposed that the generated graphs should have a fixed number mij of edges linking vertices of degree i with vertices of degree j. We have then shown that these conditions can be imposed by an integer programming model. The model was then used to determine extremal values of Adriatic indices for several families of graphs, and we have finally shown how to generate graphs that reach these values. Key words: Chemical graphs, Adriatic indices, linear integer programming, connectivity problems.