Chapitre V - Une employée mécontente

Pour que Cindy puisse retrouver le sourire dans le cinquième chapitre, Manori utilise le concept de « couplage » dans un graphe. Un couplage est simplement un ensemble d’arêtes n’ayant aucune extrémité en commun. Étant donné le tableau des préférences des employées de l’hôtel, Manori construit un graphe dans lequel les employées et les tâches sont représentées par des sommets. Le sommet représentant une employée est relié par une arête à tous les sommets « tâches » qui correspondent à ses préférences. Un couplage dans ce graphe est donc une affectation des employées aux tâches telle que chaque employée n’effectue qu’une tâche et chaque tâche est réalisée par exactement une personne. Le graphe déduit du tableau des préférences des employées a la particularité que tous les couplages ayant neuf arêtes contiennent nécessairement l’arête qui relie Cindy au nettoyage du bar. Les couplages dans les graphes ont fait l’objet de nombreuses études. Le livre de Lovász et Plummer [Lov86] constitue un excellent ouvrage de référence.

Notes pédagogiques - Couplages et colorations d’arêtes

 

• Accueil
• Chapitre I
  Le respect des règles
• Chapitre II
  Les villas du Bellevue
• Chapitre III
  Vol aux archives cantonales
• Chapitre IV
  La course à l'héritage
• Chapitre V
  Une employée mécontente
• Chapitre VI
  La souris et la puce
• Chapitre VII
  L'homme à la cagoule
• Chapitre VIII
  Une voiture nous attend
• Chapitre IX
  L'apprentie sudokiste
• Références bibliographiques

Accueil :: Chapitre I Le respect des règles :: Chapitre II Les villas du Bellevue :: Chapitre III Vol aux archives cantonales :: Chapitre IV La course à l'héritage :: Chapitre V Une employée mécontente :: Chapitre VI La souris et la puce :: Chapitre VII L'homme à la cagoule :: Chapitre VIII Une voiture nous attend :: Chapitre IX L'apprentie sudokiste :: Références bibliographiques