ملخص: Dans cette thése, nous avons naturellement reconsidéré la question d'existence de noyaux dans les graphes orienté d'une part dans les graphes non orienté qu'on munit d'une orientation. Nous connaissons; à présent trois maniéres de démontrer qu'un digraphe est noyau parfait. La premiére elle établie par P. Duchet; et qui consiste à réorienter les arcs symétriques dans les circuits de maniére à se ramener aux conditions d'existence du noyaux de V. Neuman et Morgenstern et ceux de Richardson; et donc lui permettent de conclure. La seconde maniére de procéder, est celle de raisonner par induction en supposant que tout sous-digraphe est noyau parfait puis arriver à construire un noyau du digraphe entier. Et enfin la troisiéme maniére est celle d'utiliser les opérations de composition de diagraphes noyaux parfaits. En fait nous citons les résultats essentiels qui conduisent à la détermination du noyau dans un digraphe tout en les améliorant. Nous considérons le probléme d'existence de noyaux dans les digraphes sans circuits et ceux sans circuits impairs dont nous établirons un algorithme polynominal dans chacun des cas. Nous étudions ensuite l'existence de noyaux dans les graphes triangulés, munis de l'orientation normale dont nous donnons un algorithme de recherche de noyaux dans cette classe de graphes qui sont parfaits. Nous procéderons ensuite à la programmation de chacun des algorithmes à la fin des chapitres, ce qui nous permettra de déterminer facilement le noyau dans de tels graphes. Par ailleurs, les résultats obtenus par Boros et Gurvich concernant la conjecture générale " un graphe parfait est solvable" dépendent entiérement de ceux tiré de la théorie des jeux, ce qui nous a amené à en faire une étude compléte.

طبعة: Blida: Université de Blida
لغة: فرنسية
الوصف المادي: 63 p. ill. ;30 cm
الشهادة: Magister
مؤسسة مناقشة الرسالة: Université de Blida

ملاحظة: Annexe pp.[1-10]; Bibliogr.pp.[1-2]