Département de Mathématiques

Permanent URI for this collection

Now showing 1 - 1 of 1

Problème des mariages stables
(ummto, 2020) Benchabane, Karima; Kedir, Cylia
La théorie des graphes constitue une branche de connaissances très importante. Elle représente un outil appréciable qui a pris une large part au sein d'un ensemble très vaste de méthodes et techniques généralement regroupées sous l'appellation Recherche opérationnelle ou mathématiques discrètes. L'utilité de la théorie des graphes s'avère par le développement d'une modélisation qui ramène une grande variété de problèmes concrets à l'étude d'une structure particulière et simplificatrice constituée de points et de lignes sur une surface, qui déterminent en leur ensemble un graphe. Le contenu de ce travail repose sur l'étude d'un problème bien connu en informatique (Knuth, 1971) et en économie (Roth et Oliveira Sotomayor, 1990), qui est celui des mariages stables. Il a été présenté en 1962 par deux mathématiciens économistes, David Gale et Lloyd Shapley. Le mécanisme fondé sur la théorie des mariages a tenu un rôle prépondérant dans la résolution des problèmes d'appariement sous préférences. Ce dernier représente un problème d'affectation. Le problème des colocataires stables représente une généralisation du problème du mariage stable qui consiste en la partition d'un ensemble de 2n personnes en paires stable des colocataires. Comme réalisation pratique on a programmé l'algorithme de Gale-Shapey à l'aide du langage de programmation python