Etude théorique et algorithmique sur la recherche de noyaux dans les graphes orientés

Abstract

Dans ce mémoire, nous nous sommes intéressées principalement à l'étude du noyau dans les graphes orientés. Ce concept a connu quatre généralisations: Noyau dans un graphe orienté, noyau par des chemins monochromatiques dans un graphe orienté m-coloré, (k,l)-noyau et (k,l)-plus noyau dans un graphe orienté. Nous commençons par une étude théorique sur le noyau et ses généralisations dans les graphes orientés ; Nous donnons des définitions et certaines propriétés de chaque concept de noyau et également quelques résultats connus sur ces quatre concepts. Ensuite, nous proposons deux algorithmes polynomiaux de recherche de (k,l)plus-noyaux dans les graphes orientés sans circuits et les graphes orientés bipartis. Enfin, nous élaborons un logiciel qui récapitule nos travaux sur la recherche de (k,l)-plus- noyaux dans les graphes orientés sans circuits et les graphes orientés bipartis.