Devoir en temps libre d’algorithmique à rendre le mardi 24 octobre 2000

À rédiger soigneusement.

Mariage maximum

Soit G = (X, Y, E) un graphe biparti construit sur deux ensembles indépendants X (les femmes) et Y (les hommes) (toute arête e ∈ E relie donc une femme à un homme qu’elle aime et il n’y a pas d’hermaphrodite).

Un mariage est un sous-ensemble M ⊆ E tel que chaque femme soit mariée à un homme qu’elle aime (chaque sommet de G est une extrémité d’une arête de M au plus).

1. On dit que M est un mariage maximal s’il n’est inclus strictement dans aucun autre mariage. Donnez un algorithme de construction d’un mariage maximal.

2. On dit que M est un mariage maximum s’il n’existe pas de mariage de cardinalité strictement supérieure. Tout mariage maximal est il maximum ?

3. Un chemin est une suite de sommets distincts telle que deux sommets consécutifs sont reliés par une arête. Soit M un mariage. Un chemin Malterné est un chemin qui alterne entre arêtes de de M et arêtes de E −M, et un chemin M-augmentant est un chemin M-alterné qui commence et finit par des sommets M-insaturés, c’est-à-dire des sommets qui ne sont extrémité d’aucune arête de M. Montrez que s’il existe un chemin M-augmentant alors M n’est pas maximum.

4. On appelle couverture un ensemble C de sommets de G telle que toute arête du graphe a au moins l’une de ses deux extrémités dans C. Soit C une couverture et M un mariage. Comparez |C| et |M|.

5. On considère l’algorithme suivant, qui construit deux ensembles de sommets S ⊆ X et T ⊆ Y. U dénote l’ensemble des sommets M-insaturés de X. Au départ tous les sommets de U sont non marqués.

S = U T = ∅ tant qu’il y a dans S des sommets non marqués faire :

Choisir un sommet x ∈ S non marqué.

Pour chaque voisin y de x tel que y∉T et xy∉M faire : Si y est insaturé, arrêter en répondant «M n’est pas maximum». Sinon, soit w ∈ x tel que yw ∈ M. Ajouter y à T. Ajouter w à S.

Marquer x. Arrêter en répondant «T ∪ (X − S) est une couverture».

Montrez que l’algorithme termine toujours, et qu’il est correct.

6. Dans le cas où l’algorithme retourne une couverture, comparez la taille de cette couverture à celle de M. Qu’en déduisez vous sur M ?

7. Comment modifier l’algorithme pour construire un mariage maximum ?

8. On a vu que s’il existe un chemin M-augmentant, M n’est pas maximum. Que dire de la réciproque ?

Mariages stables

1. Le problème de l’internat stable : Il y a 2n internes et on doit mettre deux internes par chambre. Chaque interne a une liste de préférences qui ordonne totalement l’ensemble des 2n − 1 autres internes. On dit que l’internat est instable s’il existe deux internes a et b (appelés éléments perturbateurs) tels que a préfère b à son camarade de chambre, et b préfère a à son camarade de chambre. Montrez que dans le cas suivant il n’y a pas d’internat stable :

\begin{matrix}a : b > c > d \\ b : c > a > d \\ c : a > b > d \\ d : a > b > c \end{matrix}

2. Dans la suite du problème on cherche à marier n hommes à n femmes. Un mariage est donc une bijection de l’ensemble des hommes dans l’ensemble des femmes. Chaque homme a une liste de préférences qui ordonne totalement l’ensemble des femmes, et réciproquement. On dit qu’un mariage est stable s’il n’existe pas une femme f et un homme h′ tels que f préfère h′ à son conjoint, et réciproquement h′ préfère f à son conjoint (autrement dit, on veut éviter tout risque d’adultère).

On considère l’algorithme de mariage suivant.

Répéter

Chaque femme demande en mariage l’homme le plus haut sur sa liste

qui ne l’a pas déjà rejetée. Tou homme qui reçoit k ≥ 2 demandes en mariage rejette les demandes

émanant des k − 1 femmes les plus basses sur sa liste. Jusqu’à ce que chaque homme reçoive exactement une demande. On marie alors chaque homme à la femme qui l’a demandé.

Quel est le mariage produit par l’algorithme sur l’exemple suivant ?

\begin{matrix}F emmes : \{x, y, z, w\} & Hommes : \{a, b, c, d\} \\ x : a > b > c > d & a : z > x > y > w \\ y : a > c > b > d & b : y > w > x > z \\ z : c > d > a > b & c : w > x > y > z \\ w : c > b > a > d & d : x > y > z > w \end{matrix}

3. Montrez que cet algorithme termine toujours et produit un mariage stable.

4. Montrez que cet algorithme produit toujours un mariage M qui est optimal du point de vue des femmes. C’est-à-dire que si M′ est un autre mariage stable, aucune femme n’est mariée dans M′ à un homme qu’elle préfère à son époux dans M. Réciproquement, montrez que ce mariage stable est le plus mauvais du point de vue des hommes.

5. On ne suppose plus qu’il y a autant d’hommes que de femmes. Définir une notion de stabilité (on supposera que tout le monde préfère être marié plutôt que célibataire). Proposez un algorithme de mariage. Propriétés de cet algorithme.

6. Avec les hypothèses de la question précédente, montrez que l’ensemble des personnes qui restent célibataires est le même dans tous les mariages stables.

7. Si une personne reste célibataire dans un mariage stable, aurait-il pu en aller autrement si elle avait une liste de préférences différente ?