Matching and Job assignments
Definition : A matching M in a graph is a set of edges , no two of which are incident with one another.
Ex :
** {(v1, v2),(v5, v6),(v3, v4)}
is a matching.
** {(v2, v6),(v3, v4)}
is a matching.
** {(v1, v2),(v3, v4)}
is a matching.
** {(v1, v2),(v5, v6),(v2, v4)}
is Not a matching.
Application:Suppose there are several employees in a company and a certain number of tasks .
Each employee can perform a sub collection of these tasks how one can distribute these
tasks to the employees such that each employee is assigned exactly one task.
Ex:
We can think of this to be bipartite graph with vertices
{e1, e2, e3, e4, J1, J2, J3, J4}.
The problem is equivalent to find a matching where each elements of the set
{e1, e2, e3, e4}
is a vertex of one if the edges of this matching .
In general we call these kind of problems “Job assignment problem”.
{(e1, J1),(e2, J4),(e3, J2),(e4, J3)}
Ex:
In this example , we can’t assign the four employee four different Jobs.