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.

This problem can only be submitted at Cogniterra.

  1. In the first case, it's possible

  2. In the second case, it's possible

  3. In the third case, it's possible