Use a bipartite graph and its tabular or matrix form to represent possible assignments for an allocation problem.

Five project managers (Aya, Bree, Chen, Devi, Ethan) are being assigned to five work sites (W1, W2, W3, W4, W5). The table shows which managers are qualified to work at each site. Which bipartite graph correctly represents the possible manager–site assignments?

A workshop manager needs to assign four technicians — Keiko (K), Leon (L), Maya (M) and Nico (N) — to four tasks: calibration (C), diagnostics (D), installation (I) and repair (R). The table below shows which tasks each technician is qualified to perform. **(a)** Construct an allocation matrix for this assignment problem. Use rows for technicians and columns for tasks. Enter 1 if the technician is qualified for the task, and 0 otherwise. **(2 marks)** **(b)** Draw the bipartite graph representing the possible assignments. Place technicians on the left and tasks on the right, and draw an edge whenever a technician is qualified for a task. **(2 marks)**

A community theatre is allocating five volunteers — Bella (B), Carlos (C), Daria (D), Eric (E), and Fiona (F) — to work on three production roles: lighting (L), props (P), and sound (S). The table below shows which roles each volunteer is qualified to perform. (a) Construct a bipartite graph representing the possible assignments between volunteers and roles. Label each vertex clearly. **(2 marks)** (b) Write down the adjacency matrix for this bipartite graph, with volunteers as rows and roles as columns. Use 1 to indicate a possible assignment and 0 otherwise. **(2 marks)**

A company has five drivers (Amara, Bayo, Chen, Devi, Ella) who are qualified to operate different vehicle types. The table below shows which drivers are qualified for each vehicle type. Which bipartite graph correctly represents this information?

A community centre needs to assign three instructors (Amira, Blake, Chen) to three classes (Dance, Music, Painting). The table below shows which instructors are qualified to teach each class. (a) Construct a bipartite graph showing all possible assignments. (1 mark) (b) Express the assignment possibilities as a matrix, with instructors as rows and classes as columns. Use 1 to indicate a possible assignment and 0 to indicate an impossible assignment. (1 mark) (c) Use your bipartite graph or matrix to determine how many edges connect Blake to the classes. (1 mark)