Etude theorique et algorithemique sur la recherche de noyaux dans les digraphes et de noyaux par chemins monochromatiques dans certaines classes de digraphes ( m-colores)

Abstract

Dans ce mémoire, nous étudions le problème d’existence de noyaux dans les digraphes et de noyaux par chemins monochromatiques dans les digraphes m-colorés. Dans un premier temps, nous allons citer quelques résultats essentiels qui conduisent à la détermination du noyau dans certaines classes de digraphes, nous allons établir aussi des algorithmes polynomiaux de recherche de noyaux dans les digraphes tel que tout circuit possède un arc symétrique et les digraphes tel que tout circuit impair possède deux arcs symétriques. Dans un second temps, nous étudions la notion de noyaux par chemins monochromatiques dans les digraphes m-colorés, nous montrons l’existence de noyaux par chemins monochromatiques dans certaines classes de digraphes m-colorés comme les arbres orientés et les digraphes transitifs. Nous donnons un algorithme amélioré de recherche de la matrice du digraphe obtenu à partir du digraphe initial par la fermeture transitive par chemins monochromatiques. Puis nous fournissons un algorithme polynomial qui détermine un noyau par chemins monochromatiques dans les digraphes mcolorés sans circuit.

Enfin, nous élaborons un logiciel qui récapitule nos travaux sur la recherche de noyaux les digraphes et de noyaux par chemins monochromatiques dans les digraphes mcolorés étudiés. In this thesis, we study the problem of existence of kernels in digraphs and kernels by monochromatic paths in digraphs m-colored. At first, we will cite some essential results that lead to the determination of the kernel in some classes of digraphs. We will also establish polynomial algorithms for determination of kernels in digraphs such that any circuit has a symmetric arc and digraphs such that any odd circuit has two symmetrical arcs. In a second step, we will study the notion of kernels by monochromatic paths in the m-colored digraphs; we show the existence of kernels by monochromatic paths in some classes of digraphs such as oriented trees and transitive digraphs. We give an improved algorithm for finding the matrix of the digraphs obtained from the initial digraphs by the transitive closure by monochromatic paths. Then we give a polynomial algorithm to determine a kernel by monochromatic paths in m-colored digraphs without circuit. Finally, we develop a software that summarizes our work on the search for kernels in digraphs and kernels by monochromatic paths in studied digraphs m-colored.