Etude synthèse et génération des cliques maximales dans les graphes non orientés

Abstract

Au XIX ème siècle, avec l'avènement de la révolution industrielle, l'humanité avait grand besoin d'un puissant outil de modélisation et de résolution des problèmes concrets. le mot " graphe " a été introduit par l'anglais J.J. Sylvester en 1822. La théorie des graphes est l'un des outils utilisés pour résoudre les problèmes combinatoire, et comme on ne peut pas résoudre ce problème sans passer par l'utilisation d'un algorithme, on peut dire qu'il y a une grande relation celle-ci et l'informatique. Donc le problème de génération des cliques maximales exige l'étroite collaboration des deux sciences : la théorie des graphes et l'informatique. En effet, pour traiter ce problème il faut utiliser des algorithmes de génération des cliques maximales qui ont la capacité de parcourir un graphe à la recherche des cliques. Ils sont classés suivant trois critères :l'ordre lexicographique, le délai d'exécution et l'espace mémoire. De nos jours, de nombreux laboratoires de recherches, à travers le monde, travaillent sur l'amélioration de ces algorithmes. L'objectif de ce travail est de faire connaitre d'une manière générale le concept des cliques maximales dans les graphes non orientés tout en mettant en évidence leurs principaux avantages dans la recherche de ces cliques. Ce travail nous a permis de dégager plusieurs perspectives qui nous semblent intéressantes à explorer dans les travaux futures. Parmi ces perspectives, nous citons : " Étude et analyse des cliques maximales pour les différentes classes de graphes. " Synthèse et étude des applications des cliques maximales dans différents domaines.