Represent and solve a small bipartite matching problem

Bipartite matching

A bipartite relation has two disjoint classes of vertices. A complete matching pairs every required left vertex with a different allowed right vertex

1. Keep the two classes separate Every selected pair joins one left label to one right label \(\displaystyle L_1\leftrightarrow R_1\)
2. Use only allowed pairs A relation entry of 1 permits a pair; an entry of 0 does not \(\displaystyle R(L_2,R_3)=1\Rightarrow L_2\text{ may use }R_3\)
3. Do not reuse a right label Once a right label has been assigned, remove it from the remaining choices \(\displaystyle L_1\leftrightarrow R_1,\quad L_2\leftrightarrow R_1\text{ is not one-to-one}\)
4. Assign every required left label A complete matching has one selected pair for each required left label \(\displaystyle L_1\leftrightarrow R_1,\quad L_2\leftrightarrow R_2,\quad L_3\leftrightarrow R_3\)

Worked example

Each technician row lists jobs J₁, J₂, J₃ and J₄ in that order; 1 means allowed and 0 means not allowed. Find the complete matching

1. \(\displaystyle T_2\leftrightarrow J_2\)T_2 has only one allowed job, so this pair is forced
2. \(\displaystyle T_3\leftrightarrow J_1\)T_3 has only one allowed job, so J_1 is now used
3. \(\displaystyle T_1\leftrightarrow J_3\)T_1 can use J_1 or J_3, but J_1 has already been used
4. \(\displaystyle T_4\leftrightarrow J_4\)T_4 can use J_3 or J_4, but J_3 has already been used

Common mistakes

Difficulty levels

Questions about this topic

In this chapter