2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задачи о свадьбах и о гареме
Сообщение20.11.2005, 19:54 
Пожалуйста, помогите решить задачи.

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

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

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

  
                  
 
 
Сообщение21.11.2005, 15:11 
А к Лемме Кэли (она же Лемма о девушках) это никак не свести?

  
                  
 
 Про лемму
Сообщение23.11.2005, 16:05 
А что это за лемма?

  
                  
 
 
Сообщение30.11.2005, 01:31 


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group