Résumé:
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.
