Задачи о свадьбах и о гареме

[Гость]

Пожалуйста, помогите решить задачи.

1. Задача о свадьбах.
Пусть имеется конечное множество юношей, каждый из которых знаком с некоторым подмножеством множества девушек. В каком случае всех юношей можно женить так, чтобы каждый женился на знакомой девушке?

2. "Задача о гареме".

Имеется конечное множество юношей, каждый из которых знаком с некоторым конечным подмножеством множества девушек. Каждый юноша желает взять в жены более чем одну знакомую девушку. Найти необходимое и достаточное условия решения этой задачи.

[garri_spbsu]

А к Лемме Кэли (она же Лемма о девушках) это никак не свести?

[Гость]

А что это за лемма?

[bekas]

Ваша первая задача дословно рассмотрена в книге:
Ф.А. Новиков "Дискретная математика для программистов", пункт 8.4.1. Задача о свадьбах

Для решения используется теорема Холла.