Efficient computational methods for two distance-based topological indices and applications on large networks

Abstract

De nombreux systèmes complexes et phénomènes du monde réel peuvent être modélisés sous forme de réseaux et analysés à l'aide de certaines techniques dérivées de la théorie des graphes. L'une des approches utilisées pour la caractérisation des informations structurelles des réseaux est une sorte de mesures quantitatives appelées les indices topologiques. La classe la plus considérée de ces mesures est celle des indices topologiques basés sur la distance, qui inclut l'une des plus importantes et anciennes mesures appelé l'indice de Wiener. Dans cette thèse, nous allons nous concentrer sur deux extensions récentes de l'indice de Wiener notamment l'indice de Terminal de Wiener et l'indice de Terminal de Wiener généralisé. L'objectif de ce travail est d'améliorer et de développer de nouvelles méthodes permettant le calcul efficace de l'indice de Terminal de Wiener et sa généralisation. Tout d'abord, nous étudions quelques propriétés fondamentales de ces indices, en particulier les limites maximales de l'indice de Terminal de Wiener pour le cas des arbres. Ensuite, nous proposons trois méthodes pour résoudre le problème de calcul de l'indice de Terminal de Wiener pour certains types de réseaux. Cependant, l'utilisation de ces méthodes dans le cas des réseaux larges et complexes serait une tâche difficile. Pour cette raison, nous étudions une nouvelle approche appelée la méthode de coupe "cut method" et nous utilisons cette technique pour dériver de nouvelles formules efficaces pour le calcul de l'indice de Terminal de Wiener et sa généralisation. De plus, nous nous concentrons sur une extension de la méthode de coupe basée sur un concept appelé la représentation canonique d'un réseau afin de réduire la complexité de calcul de ces indices et de développer un algorithme linéaire pour certains systèmes complexes.