Изменения

== Основная задача Паросочетание в двудольном графе==

Есть N мужчин и N женщин. Они обладают следующими особенностями:{{Определение|id=matching_def# Каждый человек оценивает лишь людей противоположного пола |definition= '''Паросочетание''' (все гетеросексуальныангл. ''matсhing'')<tex>M</tex> в двудольном графе — произвольное множество рёбер двудольного графа, такое что никакие два ребра не имеют общей вершины.}}# Каждый мужчина может отсортировать женщин от "наименее привлекательной" к "наиболее привлекательной"{{Определение|definition= Вершины двудольного графа, инцидентные рёбрам паросочетания <tex>M</tex>, причем его предпочтения не меняются называются '''покрытыми''' (у каждого мужчины своя функция оценкиангл. ''matched'')# Каждая женщина может отсортировать мужчин от "наименее привлекательного" к "наиболее привлекательному", причем её предпочтения не меняются а неинцидентные — '''свободными''' (у каждой женщины своя функция оценкиангл. ''unmatched'').}} {{Определение Очевидным образом по такому определению строится полный двудольный граф |definition= '''Числом рёберного покрытия''' (англ. ''edge covering number'') называется размер минимального рёберного покрытии графа <tex>G</tex> и обозначается через <tex>\rho(левая доля - мужчины, правая - женщиныG), назовем его МЖ</tex>.}}{{ОпределениеРассмотрим некоторое [http:|definition= Число рёбер в наибольшем паросочетании графа <tex>G<//neerctex> называется '''числом паросочетания''' (англ.ifmo''matching number'').ru/wiki/index.php?title}}{{Определение|id = maximal_matching|definition=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%BC_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B8_%D0%B8_%D0%B4%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D1%8F%D1%8E%D1%89%D0%B8%D1%85_%D1%86%D0%B5%D0%BF%D1%8F%D1%85#matching_def '''Максимальное паросочетание] в МЖ''' (англ. Пара A-b называется неустойчивой (unstable pair''maximal matching'')— это такое паросочетание <tex>M</tex> в графе <tex>G</tex>, если:# В которое не содержится ни в каком другом паросочетании этого графа, то есть пары A-a и B-b (A женат на aк нему невозможно добавить ни одно ребро, B женат на b)которое бы являлось несмежным ко всем рёбрам паросочетания.}}# A считает b привлекательнейДругими словами, чем a# b считает A привлекательнейпаросочетание <tex>M</tex> графа <tex>G</tex> является максимальным, чем B(неформально это означает потенциальную возможность измены)если любое ребро в <tex>G</tex> имеет непустое пересечение по крайней мере с одним ребром из <tex>M</tex>.

|definitionid =Устойчивое паросочетание (stable matching) - паросочетание без неустойчивых пар.}} Задача заключается в нахождении полного устойчивого паросочетания по данным спискам предпочтений.perfect_matching|definition== Агоритм Гейла-Шепли == Решение задачи было описано в 1962 году математиками Девидом Гейлом Паросочетание <tex>M</tex> графа <tex>G</tex> называется '''совершенным (Университета Браунаили полным) и Ллойдом Шепли ''' (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthlyангл. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи). === Интуитивное описание === # мужчины делают предложение наиболее предпочитаемой женщине;# каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка''perfect matching''), на если оно покрывает все остальные отвечает «нет» (отказ)# мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;# если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;# шаги 1-4 повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий моментвершины графа.}}{{Определение|definition=== Описание в псевдокоде ===  Изначально все мужчины и все женщины не женаты (не замужем) '''whileЧередующаяся цепь''' Существует m <- некоторый свободный мужчина, не делавший предложения всем женщинам w <- первая женщина из списка m, которой m еще не делал предложения (англ. ''alternating path'if''' w свободна) — путь в двудольном графе, для любых двух соседних рёбер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}} помечаем m и w помолвленными{{Определение |definition= '''else ifДополняющая цепь (или увеличивающая цепь)''' w предпочитает m своему "текущему" жениху m' помечаем m и w помолвленными, m(англ. ' - свободным 'augmenting path''else''' w отказывает m === Доказательство корректности === {{Утверждение|id=observation1|about=Наблюдение 1|statement=Мужчины делают предложения женщинам в порядке убывания симпатии}} {{Утверждение|id=observation2|about=Наблюдение 2|statement=Как только женщина была помолвлена) — чередующаяся цепь, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату)у которой оба конца свободны.}} Для начала покажем, что алгоритм завершит свою работу. {{ЛеммаОпределение|iddefinition=lemma1|about=Лемма 1|statement= Алгоритм завершается после максимум n^2 итераций цикла '''whileУменьшающая цепь'''|proof= На каждой итерации мужчина делает предложение очередной женщине(англ. Но всего может быть не более n^2 предложений''reduce path'') — чередующаяся цепь, у которой оба конца покрыты.}} Теперь покажем, что по завершении алгоритма задача будет решена. {{ЛеммаОпределение|iddefinition=lemma2|about=Лемма 2|statement= Все мужчины и женщины будут заняты'''Сбалансированная цепь''' (англ.|proof= 1. Предположим''balanced path'') — чередующаяся цепь, что некоторый мужчинау которой один конец свободен, Ян, не женат по завершении алгоритмаа другой покрыт.}}

3В любом графе без изолированных вершин, число паросочетания и число рёберного покрытия в сумме дают число вершин. По [[#observation2Если существует совершенное паросочетание, то оба числа равны <tex>|наблюдению V|/2]], Антонине никто не делал предложения</tex>.

4. Но Ян сделал предложения всем женщинам== Пример максимального и полного паросочетания, т.к. он остался не женатчередующейся цепи ==

5{|align="center" |-valign="center" |[[Файл: Maximal matching. Получаем противоречиеjpg|thumb|210px|<font color=red>красные рёбра</font> являются рёбрами максимального паросочетания]] |[[Файл: Perfect_matching.jpg|thumb|245px|<font color=red>красные рёбра</font> являются рёбрами полного паросочетания.]] 6 |[[Файл: Alternating_path. Аналогичные утверждения можно повторить и отталкиваясь от тогоjpg|thumb|210px|Пусть <font color=red>красные рёбра</font> принадлежат паросочетанию <tex>M</tex>, что а <font color=blue>синие</font> не занята некоторая девушкапринадлежат, поэтому предложение доказанотогда чередующаяся цепь: <tex>1-8-4-6-3-7</tex>]]} |}

{{ЛеммаТеорема|id=lemma3|about=Лемма 3theorem1

Нет неустойчивых парПаросочетание <tex>M</tex> в двудольном графе <tex>G</tex> является максимальным тогда и только тогда, когда в <tex>G</tex> нет дополняющей цепи.

1. Предположим A-b (A, B - мужчины; a, b - женщины; A женат на a, B женат на b) - нестабильная пара в паросочетнаии, найденном алгоритмом Гейла-Шепли  2. Рассмотрим два случая:  2.1. A не делал предложения b  => A находит a более привлекательной, чем b  => A-b - устойчивая пара  2.2. A делал предложение b  => b отказала A (сразу или на одной из последующих итераций)  => b находит B более привлекательным, чем A  => A-b - устойчивая пара}}  === Асимптотика алгоритма === Покажем, как реализовать внутреннюю часть цикла while за <tex>O(1)</tex> с предпроцессингом не более, чем за <tex>O(n^2)</tex>, тогда итоговая ассимптотика очевидно будет <tex>O(n^2)</tex>. Все мужчины и женщины нумеруются числами от 1 до N. Будем поддерживать два одномерных массива: wife, husband (wife[m] - id жены мужчины m или 0, если мужчина не женат; husband[w] - id мужа женщины w или 0, если женщина не замужем) Также нам нужен список свободных мужчин free, для этого можно использовать и, например, очередь или стек. Предпочтения каждого мужчины будем хранить списком, в котором женщины отсортированы от самой привлекательной к наименее привлекательной (такой список можно построить из любого другого представления не более чем за <tex>O(n^2)\Rightarrow</tex>, при необходимости сортировать можно сортировкой подсчетом). Соответствующий двумерный массив обозначим за mp (men preference). Для навигации по спискам предпочтений нам понадобится массив count, count[m] - количество женщин, которым делал предложение мужчина m.

Для женщин создадим массив wp (women preference), который аналогичен инверсии аналогичной структуры для мужчинПусть в двудольном графе <tex>G</tex> с максимальным паросочетанием <tex>M</tex> существует дополняющая цепь. В частностиТогда пройдя по ней и заменив вдоль неё все рёбра, wp[w][m] - индекс мужчины m входящие в списке предпочтений женщины w. Очевиднопаросочетание, такой массив может быть построен за время не болеена невходящие и наоборот, чем мы получим большее паросочетание. То есть <tex>O(n^2)M</tex>не являлось максимальным. Противоречие.

'''while''' not freeРассмотрим паросочетание <tex>M</tex> в графе <tex>G</tex> и предположим, что <tex>M</tex> {{---}} не наибольшее.isEmpty() m = freeДокажем, что тогда имеется увеличивающая цепь относительно <tex>M</tex>.pop() w = mp[m][count[m]++] mПусть <tex>M' = husband[w] '''if''' m' == 0 husband[w] = m wife[m] = w '''else if</tex> {{---}} другое паросочетание и <tex>|M'|>|M|</tex>. Рассмотрим подграф <tex>H</tex> графа <tex>G</tex>, образованный теми рёбрами, которые входят в одно и только в одно из паросочетаний <tex>M</tex>, <tex>M'</tex>. Иначе говоря, множеством рёбер графа <tex>H</tex> является симметрическая разность <tex>M\oplus M' wp[w][m] < wp[w][m'] husband[w] = m wife[m] = w wife[m'] = 0 free/tex>.pushВ графе <tex>H</tex> каждая вершина инцидентна не более чем двум рёбрам (mодному из <tex>M</tex> и одному из <tex>M'</tex> ) '''else''' free, т.push(m) === Анализ полученного алгоритмом паросочетания === Агоритм Гейла-Шепли гарантирует, что будет найдено некоторое решение задачие. Но решений может быть имеет степень не более одногодвух. Зададимся вопросом, какими свойствами обладает решение, найденное алгоритмом. В таком графе каждая компонента связности {{Лемма---}} путь или цикл. В каждом из этих путей и циклов чередуются рёбра из <tex>M</tex> и <tex>M'</tex>. Так как <tex>|M'|id=lemma4>|about=Лемма 4 (man-optimality)M|statement= Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение</tex>, имеется компонента, наилучшее для мужчин (каждый мужчина получает в жены женщинукоторой рёбер из <tex>M'</tex> содержится больше, наилучшую чем рёбер из всех возможных при условии корректности решения<tex>M</tex>. Это может быть только путь, у которого оба концевых ребра принадлежат <tex>M'</tex>. Заметим, что относительно <tex>M</tex> этот путь является увеличивающей (дополняющей)цепью.

{{Лемма|id=lemma5|about=Лемма 5 (woman-pessimality)|statement= Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наихудшее для женщинСм.}} Эти две леммы оставим без доказательства, интересющиеся могут обратится к документу http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-matching.pdf (с.5) == Обобщения задачи также== Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть). (см. * [[http://ru.wikipedia.org/wiki/Задача_о_соседях_по_комнате Задача о соседях по комнатеТеорема Холла]]) Случай же, когда у нас есть <tex>N</tex> мужчин и <tex>M</tex> женщин (<tex>N \neq M</tex>) легко сводится к описанной выше задаче. Рассмотрим <tex>M > N</tex> (<tex>M < N</tex> аналогично). Добавим <tex>M - N</tex> фиктивных мужчин, которые являются наименее привлекательными с точки зрения каждой из женщин. Тогда если в найденном алгоритмом Гейла-Шепли паросочетании некоторая женщина будет замужем за таким фиктивным мужчиной, это будет де-факто означать, что она осталась не замужем. Также интересна задача о выборе учебного заведения: вместо множества мужчин введем множество университетов, а вместо множества женщин - множество кандидатов, подающих заявления на поступление. Причем в каждом университете есть квота на количество студентов, которое университет может принять. Задача очевидно сводится к основной добавлением <tex>(K-1)</tex> "филиалов" для каждого университета (<tex>K</tex> - квота). И добавлением фиктивного университета (поступление в который означает, что кандидату придется попробовать поступить через год). == Применения в реальной жизни == Задача о нахождении устойчивого * [[Связь максимального паросочетания и её решение имеют множество применений в реальной жизни, лишь некоторые из них:* Распределение студентов по коллеждам в США* Распределение интернов по больницам* Распределение донорских органов по нуждающимся в них людям Решение данной задачи было отмечено при вручении Нобелевской премии по экономике в 2012 году за «теорию стабильного распределения и практическое применение рыночных моделей». Её получили один из создателей алгоритма, Ллойд Шепли, а также Элвин Рот, во многом развивший исследования Ллойда Шепли и Дэвида Гейла. Сам Гейл не был удостоен премии, вероятно, лишь в силу того, что умер минимального вершинного покрытия в 2008 году. == Ссылки == * [http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-matching.pdf Stable matching, Prinston lecture's presentationдвудольных графах]* [http://en.wikipedia.org/wiki/Stable_marriage_problem Stable marriage problem]* [http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BC%D0%B0%D1%80%D1%8C%D1%8F%D0%B6%D0%B5 Задача о марьяже]* [http://ge.tt/api/1/files/4LU3zaD1/0/blob?download Устойчивость супружеских пар Связь вершинного покрытия и другие комбинаторные задачи (Статья Дональда Кнута)независимого множества]]