|
Гость |
|
|
|
Пожалуйста, помогите решить задачи.
1. Задача о свадьбах.
Пусть имеется конечное множество юношей, каждый из которых знаком с некоторым подмножеством множества девушек. В каком случае всех юношей можно женить так, чтобы каждый женился на знакомой девушке?
2. "Задача о гареме".
Имеется конечное множество юношей, каждый из которых знаком с некоторым конечным подмножеством множества девушек. Каждый юноша желает взять в жены более чем одну знакомую девушку. Найти необходимое и достаточное условия решения этой задачи.
|
|
|
|
 |
|
garri_spbsu |
|
|
|
А к Лемме Кэли (она же Лемма о девушках) это никак не свести?
|
|
|
|
|
|
bekas |
|
|
Ваша первая задача дословно рассмотрена в книге:
Ф.А. Новиков "Дискретная математика для программистов", пункт 8.4.1. Задача о свадьбах
Для решения используется теорема Холла.
|
|
|
|
|
