Matchings · Bipartite Graphs

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

  1. A school has four job openings, and there are four applicants for them. Is it possible to fill all the positions? Try it!

  2. Six friends are preparing a party. There are five tasks, each needs to be assigned to one person. The squares below show which tasks each person can do. Is it possible to assign each task to a different person?

  3. Is it possible to assign each student to a room they like (one student per room)?

Problem.

5 points

  1. In the first case, it's possible

  2. In the second case, it's possible

  3. In the third case, it's possible