Изменения

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

Есть 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 привлекательнейДругими словами, паросочетание <tex>M</tex> графа <tex>G</tex> является максимальным, чем aесли любое ребро в <tex>G</tex> имеет непустое пересечение по крайней мере с одним ребром из <tex>M</tex>.# b считает A привлекательней, чем B{{Определение|id = maximal_matching_size|definition= '''Максимальное паросочетание (неформально по мощности)''' (англ. ''maximum cardinality matching'') — это означает потенциальную возможность измены)паросочетание <tex>M</tex> в графе <tex>G</tex> максимальное по мощности.}}

|id = perfect_matching|definition=Устойчивое паросочетание Паросочетание <tex>M</tex> графа <tex>G</tex> называется '''совершенным (stable или полным)''' (англ. ''perfect matching''), если оно покрывает все вершины графа.}}{{Определение|definition= '''Чередующаяся цепь''' (англ. ''alternating path'') — путь в двудольном графе, для любых двух соседних рёбер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}{{Определение|definition= '''Дополняющая цепь (или увеличивающая цепь) - паросочетание без неустойчивых пар''' (англ.''augmenting path'') — чередующаяся цепь, у которой оба конца свободны.}}{{Определение|definition= '''Уменьшающая цепь''' (англ. ''reduce path'') — чередующаяся цепь, у которой оба конца покрыты.}}{{Определение|definition= '''Сбалансированная цепь''' (англ. ''balanced path'') — чередующаяся цепь, у которой один конец свободен, а другой покрыт.}}

Решение задачи было описано в 1962 году математиками Девидом Гейлом (Университета Брауна) == Пример максимального и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthly. Набор правилполного паросочетания, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).чередующейся цепи ==

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

# мужчины делают предложение наиболее предпочитаемой женщине;# каждая женщина из всех поступивших предложений выбирает наилучшее == Теорема о максимальном паросочетании и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ)# мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;# если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;# шаги 1-4 повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.дополняющих цепях ==

=== Описание в псевдокоде ===  Изначально все мужчины и все женщины не женаты (не замужем) '''while''' Существует m <- некоторый свободный мужчина, не делавший предложения всем женщинам w <- первая женщина из списка m, которой m еще не делал предложения '''if''' w свободна помечаем m и w помолвленными '''else if''' w предпочитает m своему "текущему" жениху m' помечаем m и w помолвленными, m' - свободным '''else''' w отказывает m === Доказательство корректности === {{УтверждениеТеорема|id=observation1|about=Наблюдение 1|statement=Мужчины делают предложения женщинам в порядке убывания симпатии}} {{Утверждение|id=observation2|about=Наблюдение 2|statement=Как только женщина была помолвлена, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату)}} Для начала покажем, что алгоритм завершит свою работу. {{Лемма|id=lemma1|about=Лемма 1theorem1

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

{{Лемма|id=lemma2|about=Лемма 2|statement= Все мужчины и женщины будут заняты.|proof= 1. Предположим, что некоторый мужчина, Ян, не женат по завершении алгоритма.  2. Тогда некоторая женщина, Антонина не замужем<tex>\Leftarrow</tex>

3Рассмотрим паросочетание <tex>M</tex> в графе <tex>G</tex> и предположим, что <tex>M</tex> {{---}} не наибольшее. По [[#observation2Докажем, что тогда имеется увеличивающая цепь относительно <tex>M</tex>. Пусть <tex>M'</tex> {{---}} другое паросочетание и <tex>|M'|>|наблюдению 2]]M|</tex>. Рассмотрим подграф <tex>H</tex> графа <tex>G</tex>, Антонине никто образованный теми рёбрами, которые входят в одно и только в одно из паросочетаний <tex>M</tex>, <tex>M'</tex>. Иначе говоря, множеством рёбер графа <tex>H</tex> является симметрическая разность <tex>M\oplus M'</tex>. В графе <tex>H</tex> каждая вершина инцидентна не делал предложения  4. Но Ян сделал предложения всем женщинамболее чем двум рёбрам (одному из <tex>M</tex> и одному из <tex>M'</tex> ), т.ке. он остался имеет степень не женат  5более двух. Получаем противоречие 6В таком графе каждая компонента связности {{---}} путь или цикл. Аналогичные утверждения можно повторить В каждом из этих путей и отталкиваясь от тогоциклов чередуются рёбра из <tex>M</tex> и <tex>M'</tex>. Так как <tex>|M'|>|M|</tex>, имеется компонента, в которой рёбер из <tex>M'</tex> содержится больше, чем рёбер из <tex>M</tex>. Это может быть только путь, у которого оба концевых ребра принадлежат <tex>M'</tex>. Заметим, что не занята некоторая девушка, поэтому предложение доказаноотносительно <tex>M</tex> этот путь является увеличивающей (дополняющей) цепью.

{{Лемма|id=lemma3|about=Лемма 3|statementИсточники информации = Нет неустойчивых пар.|proof= 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)</tex>, при необходимости сортировать можно сортировкой подсчетом). Соответствующий двумерный массив обозначим за mp (men preference). Для навигации по спискам предпочтений нам понадобится массив count, count[m] - количество женщин, которым делал предложение мужчина m. Для женщин создадим массив wp (women preference), который аналогичен инверсии аналогичной структуры для мужчин. В частности, wp[w][m] - индекс мужчины m в списке предпочтений женщины w. Очевидно, такой массив может быть построен за время не более, чем <tex>O(n^2)</tex>. Тогда цикл while может быть реализован следующим образом:  '''while''' not free.isEmpty() m = free.pop() w = mp[m][count[m]++] m' = husband[w] '''if''' m' == 0 husband[w] = m wife[m] = w '''else if''' wp[w][m] < wp[w][m'] husband[w] = m wife[m] = w wife[m'] = 0 free.push(m') '''else''' free.push(m) === Анализ полученного алгоритмом паросочетания === Агоритм Гейла-Шепли гарантирует, что будет найдено некоторое решение задачи. Но решений может быть более одного. Зададимся вопросом, какими свойствами обладает решение, найденное алгоритмом. {{Лемма|id=lemma4|about=Лемма 4 (man-optimality)|statement= Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).}} {{Лемма|id=lemma5|about=Лемма 5 (woman-pessimality)|statement= Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наихудшее для женщин.}} Эти две леммы оставим без доказательства, интересющиеся могут обратится к документу http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-matching.pdf (с.5) == Обобщения задачи == Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть). (см. [* [http://ruen.wikipedia.org/wiki/Задача_о_соседях_по_комнате|Задача о соседях по комнате]]) Случай же, когда у нас есть <tex>N</tex> мужчин и <tex>M</tex> женщин (<tex>N \neq M</tex>) легко сводится к описанной выше задаче. Рассмотрим <tex>M > N</tex> (<tex>M < N</tex> аналогично). Добавим <tex>M Matching_%28graph_theory%29 Wikipedia {{- 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}} Matching]* [httphttps://ru.wikipedia.org/wiki/%D0%979F%D0%B0%D0D1%B480%D0%B0BE%D1%87%D0%B0_81%D0%BE_BE%D0D1%BC87%D0%B0B5%D1%8082%D1D0%8CB0%D1D0%8FBD%D0%B6B8%D0%B5 Задача о марьяжеВикипедия {{---}} Паросочетание]* [http Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика://geГрафы, матроиды, алгоритмы. стр.tt/api/1/files/4LU3zaD1/0/blob?download Устойчивость супружеских пар и другие комбинаторные задачи (Статья Дональда Кнута)]227-232 '''ISBN 978-5-8114-1068-2'''