Chapter V - An Unhappy Employee

To help Cindy get her smile back in the fifth chapter, Manori uses the concept of "matching" in a graph. A match is simply a set of edges that have no ends in common. When he considers the table of hotel employees' preferences, Manori builds a graph in which the employees and tasks are represented by vertices. Each vertex representing an employee is linked by an edge to all the "task" vertices that correspond to that person's preferences. A match, in this graph, is therefore an assignment of employees to tasks such that each employee carries out only one task, and each task is performed by exactly one person. The graph deduced from the table of employee preferences has the particular feature that all the matches with nine edges necessarily contain the edge that links Cindy to cleaning the bar. Matches have been the subject of many studies. Lovász and Plummer's book is an excellent reference work.

Teaching notes - Matches and Edge Colouring

 

• Home
• Chapter I
  Respecting the Rules
• Chapter II
  The Villas of the Bellevue
• Chapter III
  The Case of the Missing Files
• Chapter IV
  The Case of the Hidden Inheritance
• Chapter V
  An Unhappy Employee
• Chapter VI
  The Case of the Runaway Mouse
• Chapter VII
  The Case of the Hooded Man
• Chapter VIII
  The Getaway Car
• Chapter IX
  The Sudoku Apprentice
• Bibliography

Home :: Chapter I Respecting the Rules :: Chapter II The Villas of the Bellevue :: Chapter III The Case of the Missing Files :: Chapter IV The Case of the Hidden Inheritance :: Chapter V An Unhappy Employee :: Chapter VI The Case of the Runaway Mouse :: Chapter VII The Case of the Hooded Man :: Chapter VIII The Getaway Car :: Chapter IX The Sudoku Apprentice :: Bibliography