2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Теорема Холла (Hall's marriage theorem)
Сообщение17.06.2018, 15:22 


03/04/14
303
Теорема гласит:
"Если у любых $k$ юношей $(1 \leq k \leq n)$ имеется не меннее $k$ знакомых девушек, то их можно так поженить, что каждому юноше достанется по знакомой девушке."

Тут доказательство:
https://www.mccme.ru/s43/math/uroki/2009_2010/9mat_0910/spec/59_hall_lect.pdf
Как-то сложно мне кажется.

Разве нельзя так, например:

Рассмотрим случай, когда у $k$ юношей ровно $k$ знакомых девушки.
Покажем как сопоставить каждому юноше по знакомой девушке.
Выберем произвольного первого юношу. По условию ( для $k = 1$) у него есть одна знакомая девушка. Получается пара которую можно поженить.
Теперь возьмем второго юношу. Теперь ($k = 2$). У них вместе с первым ровно $2$ занкомых дувушки. Если даже у второго юноше среди знакомых девушка первого - то остается еще одна. То есть двоих тоже можно поженить. И так рассуждение можно продолжить далее до $n$.

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

Что не так в таком доказательстве?

 Профиль  
                  
 
 Re: Теорема Холла (Hall's marriage theorem)
Сообщение17.06.2018, 16:15 
Заслуженный участник
Аватара пользователя


09/09/14
6328
bayah в сообщении #1320578 писал(а):
Если даже у второго юноше среди знакомых девушка первого - то остается еще одна.
Эта одна тоже может быть знакомой первого. Тогда у двоих есть две знакомых, но Вы пару не сосватали.

 Профиль  
                  
 
 Re: Теорема Холла (Hall's marriage theorem)
Сообщение17.06.2018, 17:58 


03/04/14
303
grizzly в сообщении #1320593 писал(а):
Эта одна тоже может быть знакомой первого. Тогда у двоих есть две знакомых, но Вы пару не сосватали.

Мм... Ну да, может. Это я не верно, да. Даже в случае если две девушки обе девушки только второго юноши то тоже не верно, так как тогда получается что у первого нет девушки.

Тогда так:
Так как первого юношу мы выбираем произвольно, то условие, что у $k$ юношей есть $k$ девушек верно для любого из юношей. То есть когда мы берем второго юношу в добавок к первому, то для него справедливо то же рассуждение что и для первого - то есть для него одного так же есть одна знакомая. Таким образом для них двоих две девушки не могут быть все девушками первого или второго. Одна непременно второго, а другая - второго.

 Профиль  
                  
 
 Re: Теорема Холла (Hall's marriage theorem)
Сообщение17.06.2018, 18:17 
Заслуженный участник
Аватара пользователя


09/09/14
6328
bayah в сообщении #1320617 писал(а):
Тогда так:...
Рассуждение не очень, но для случая $n=2$ я с натяжкой мог бы его засчитать. Теперь попытайтесь очень аккуратно перейти к случаю $n=3$ и дальше -- потому как голословное "и т.д." совсем не выглядит очевидным.

-- 17.06.2018, 18:21 --

(Оффтоп)

bayah в сообщении #1320617 писал(а):
Одна непременно второго, а другая - второго.
Чем-то напомнило момент из "По семейным обстоятельствам":
-- Одна живёт на Ки'евской, а другая -- на Киевской.
-- На одной улице, получается?
-- Как 'аз на 'азных!

Сорри, не удержался :D

 Профиль  
                  
 
 Re: Теорема Холла (Hall's marriage theorem)
Сообщение17.06.2018, 19:44 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
В поисках "простого доказательства" можно вот что обдумать. Можно ли составлять пары начиная с произвольной, или надо учитывать всю структуру знакомств? Не думала пока, но кажется, что второе.

 Профиль  
                  
 
 Re: Теорема Холла (Hall's marriage theorem)
Сообщение17.06.2018, 20:23 


03/04/14
303
grizzly в сообщении #1320624 писал(а):
Одна непременно второго, а другая - второго.

Ну ды)
Одна непременно первого, а другая - второго.

grizzly в сообщении #1320624 писал(а):
Рассуждение не очень, но для случая $n=2$ я с натяжкой мог бы его засчитать. Теперь попытайтесь очень аккуратно перейти к случаю $n=3$ и дальше -- потому как голословное "и т.д." совсем не выглядит очевидным.

Так, ну дальше добавляем третьего юношу. И так как для любых двух юношей есть разные девушки, то они есть и для любых двух юношей из этих трех. А это значит что и у каждого из них своя девушка.
Далее для случая $n+1$ рассуждаем так же. Так как для случая $n$ верно, что у каждого из $n$ юношей своя девушка, то это верно для всех возможных случаев выбрать $n$ юношей из $n+1$. Но тогда и для $n+1$ юноши верно что у каждого из них своя девушка.

 Профиль  
                  
 
 Re: Теорема Холла (Hall's marriage theorem)
Сообщение17.06.2018, 20:33 
Заслуженный участник
Аватара пользователя


09/09/14
6328
bayah в сообщении #1320649 писал(а):
И так как для любых двух юношей есть разные девушки, то они есть и для любых двух юношей из этих трех. А это значит что и у каждого из них своя девушка.
В общем, у Вас ничего не получается. Вы размахиваете словами, не понимая рассуждения. Посмотрите на рисунок 1 по Вашей ссылке -- там для любых двух юношей есть пара разных девушек, но сосватать всех нельзя.

Если Вы собираетесь латать своё "доказательство" под каждый контрпример, который я буду приводить, увольте. Ваше рассуждение можно спасти и для $n=3$ и даже дальше, но количество текста в аккуратном доказательстве Вашим способом будет расти по экспоненте.

 Профиль  
                  
 
 Re: Теорема Холла (Hall's marriage theorem)
Сообщение17.06.2018, 21:07 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
provincialka в сообщении #1320640 писал(а):
Можно ли составлять пары начиная с произвольной, или надо учитывать всю структуру знакомств?
Не каждая возможная пара участвует в каком-то наибольшем паросочетании. Например, если у нас есть ребра $(a_1, b_1), (a_1, b_2), (a_2, b_1)$ (и всё), то пару $(a_1, b_1)$ брать нельзя. Или вопрос не про это?

 Профиль  
                  
 
 Re: Теорема Холла (Hall's marriage theorem)
Сообщение17.06.2018, 22:25 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
mihaild
Про это, конечно! Но вроде ТС уже отказался от составления паросочетания "наращиванием"... Правда, я не очень поняла, чем он его заменил!

 Профиль  
                  
 
 Re: Теорема Холла (Hall's marriage theorem)
Сообщение18.06.2018, 07:46 


03/04/14
303
grizzly в сообщении #1320651 писал(а):
Посмотрите на рисунок 1 по Вашей ссылке -- там для любых двух юношей есть пара разных девушек, но сосватать всех нельзя.

При переходе от $2$ к $3$ я, конечно, еще учитываю и то что для $3$ юношей есть $3$ девушки.
В примере по ссылке, для любых двух - есть, а для трех - уже нет (Kai, Piter, Edmund).
То есть, так как любых двух парней можно переженить и в частности можно пережинить любых двух парней из трех, то добавляя условие для трех парней ( что они знают как минимум трех дувушек) женим любого из парней который знаком с третьей девушкой, остаются двое - которых поженить можно.

 Профиль  
                  
 
 Re: Теорема Холла (Hall's marriage theorem)
Сообщение18.06.2018, 09:06 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Вы используете кусочно-непрерывную логику, а этого делать нельзя.
bayah в сообщении #1320717 писал(а):
То есть, так как любых двух парней можно переженить и в частности можно пережинить любых двух парней из трех, то добавляя условие для трех парней ( что они знают как минимум трех дувушек) женим любого из парней который знаком с третьей девушкой, остаются двое - которых поженить можно.
Выше mihaild объяснял на примере, почему нельзя просто взять и поженить "любого из парней который знаком с третьей девушкой". Потому что оставшиеся две пары парней и девушек вовсе не обязаны удовлетворять условию задачи для $n=2$. Так просто здесь индукцию применить не получится.

 Профиль  
                  
 
 Re: Теорема Холла (Hall's marriage theorem)
Сообщение18.06.2018, 12:29 


03/04/14
303
grizzly в сообщении #1320728 писал(а):
Выше mihaild объяснял на примере, почему нельзя просто взять и поженить "любого из парней который знаком с третьей девушкой". Потому что оставшиеся две пары парней и девушек вовсе не обязаны удовлетворять условию задачи для $n=2$. Так просто здесь индукцию применить не получится.

Ну да, любого не получится, но тогда заменим "любого" на "найдется такой что"?)

 Профиль  
                  
 
 Re: Теорема Холла (Hall's marriage theorem)
Сообщение18.06.2018, 12:35 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
bayah в сообщении #1320774 писал(а):
Ну да, любого не получится, но тогда заменим "любого" на "найдется такой что"?)
А почему найдется?

Вообще, для всех известных на практике алгоритмов поиска паросочетания доказательство корректности сложнее стандартного доказательства теоремы. Так что вряд ли получится найти простой эффективный метод его нахождения.

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

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



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

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


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

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