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é.