Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Обобщения задачи)
(Товарищ Georgeee видимо торопился перед экзаменом и переписал конспект "Задача об устойчивом паросочетании" поверх существующего.)
Строка 1: Строка 1:
== Основная задача ==
+
== Паросочетание в двудольном графе==
 
 
Есть N мужчин и N женщин. Они обладают следующими особенностями:
 
# Каждый человек оценивает лишь людей противоположного пола (все гетеросексуальны)
 
# Каждый мужчина может отсортировать женщин от "наименее привлекательной" к "наиболее привлекательной", причем его предпочтения не меняются (у каждого мужчины своя функция оценки)
 
# Каждая женщина может отсортировать мужчин от "наименее привлекательного" к "наиболее привлекательному", причем её предпочтения не меняются (у каждой женщины своя функция оценки)
 
 
 
 
 
Очевидным образом по такому определению строится полный двудольный граф (левая доля - мужчины, правая - женщины), назовем его МЖ.
 
 
 
Рассмотрим некоторое [http://neerc.ifmo.ru/wiki/index.php?title=%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), если:
 
# В паросочетании есть пары A-a и B-b (A женат на a, B женат на b)
 
# A считает b привлекательней, чем a
 
# b считает A привлекательней, чем B
 
(неформально это означает потенциальную возможность измены)
 
  
 
{{Определение
 
{{Определение
|definition=Устойчивое паросочетание (stable matching) - паросочетание без неустойчивых пар.
+
|id=matching_def
}}
+
|definition= '''Паросочетание''' <tex>M</tex> в двудольном графе — произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины.}}
 
+
{{Определение
Задача заключается в нахождении полного устойчивого паросочетания по данным спискам предпочтений.
+
|definition= Вершины двудольного графа, инцидентные ребрам паросочетания <tex>M</tex>, называются '''покрытыми''', а неинцидентные — '''свободными'''.}}  
 
+
{{Определение
== Агоритм Гейла-Шепли ==
+
|definition= '''Чередующаяся цепь''' — путь в двудольном графе, для любых двух соседних ребер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}
 +
{{Определение
 +
|definition= '''Дополняющая цепь''' — чередующаяся цепь, у которой оба конца свободны.}}
  
Решение задачи было описано в 1962 году математиками Девидом Гейлом (Университета Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthly. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).
+
== Теорема о максимальном паросочетании и дополняющих цепях ==
  
=== Интуитивное описание ===
+
{{Теорема
 
+
|id=theorem1
# мужчины делают предложение наиболее предпочитаемой женщине;
 
# каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ)
 
# мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
 
# если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
 
# шаги 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=Лемма 1
 
 
|statement=
 
|statement=
Алгоритм завершается после максимум n^2 итераций цикла '''while'''
+
Паросочетание <tex>M</tex> в двудольном графе <tex>G</tex> является максимальным тогда и только тогда, когда в <tex>G</tex> нет дополняющей цепи.
 
|proof=
 
|proof=
На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более n^2 предложений.
+
<tex>\Rightarrow</tex>
}}
 
  
Теперь покажем, что по завершении алгоритма задача будет решена.
+
Пусть в двудольном графе <tex>G</tex> с максимальным паросочетанием <tex>M</tex> существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее все ребра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть <tex>M</tex> не являлось максимальным. Противоречие.
  
{{Лемма
+
<tex>\Leftarrow</tex>
|id=lemma2
 
|about=Лемма 2
 
|statement=
 
Все мужчины и женщины будут заняты.
 
|proof=
 
1. Предположим, что некоторый мужчина, Ян, не женат по завершении алгоритма.
 
  
2. Тогда некоторая женщина, Антонина не замужем
+
В доказательстве используются несколько новых понятий:
 
+
{{Определение
3. По [[#observation2|наблюдению 2]], Антонине никто не делал предложения
+
|definition= '''Увеличивающая цепь''' — чередующаяся цепь, у которой оба конца свободны.}}
 
+
{{Определение
4. Но Ян сделал предложения всем женщинам, т.к. он остался не женат
+
|definition= '''Уменьшающая цепь''' — чередующаяся цепь, у которой оба конца покрыты.}}
 
+
{{Определение
5. Получаем противоречие
+
|definition= '''Сбалансированная цепь''' — чередующаяся цепь, у которой один конец свободен, а другой покрыт}}
 
6. Аналогичные утверждения можно повторить и отталкиваясь от того, что не занята некоторая девушка, поэтому предложение доказано
 
}}
 
 
 
 
 
{{Лемма
 
|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
+
Рассмотрим паросочетание <tex>M</tex> в графе <tex>G</tex> и предположим, что <tex>M</tex> - не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно <tex>M</tex>. Пусть <tex>M'</tex> - другое паросочетание и <tex>|M'|>|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> каждая вершина инцидентна не более чем двум ребрам (одному из <tex>M</tex> и одному из <tex>M'</tex> ), т.е. имеет степень не более двух. В таком графе каждая компонента связности - путь или цикл. В каждом из этих путей и циклов чередуются ребра из <tex>M</tex> и <tex>M'</tex>. Так как <tex>|M'|>|M|</tex>, имеется компонента, в которой ребер из <tex>M'</tex> содержится больше, чем ребер из <tex>M</tex>. Это может быть только путь, у которого оба концевых ребра принадлежат <tex>M'</tex>. Заметим, что относительно <tex>M</tex> этот путь является увеличивающей (дополняющей) цепью.
 
 
=> A-b - устойчивая пара
 
 
 
2.2. A делал предложение b
 
 
 
=> b отказала A (сразу или на одной из последующих итераций)
 
 
 
=> b находит B более привлекательным, чем A
 
 
 
=> A-b - устойчивая пара
 
 
}}
 
}}
  
 
+
==Литература==
=== Асимптотика алгоритма ===
+
*  Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''
 
 
Покажем, как реализовать внутреннюю часть цикла 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://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 Устойчивость супружеских пар и другие комбинаторные задачи (Статья Дональда Кнута)]
 
 
 
  
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о паросочетании]]
 
[[Категория: Задача о паросочетании]]

Версия 23:44, 17 ноября 2014

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

Определение:
Паросочетание [math]M[/math] в двудольном графе — произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины.


Определение:
Вершины двудольного графа, инцидентные ребрам паросочетания [math]M[/math], называются покрытыми, а неинцидентные — свободными.


Определение:
Чередующаяся цепь — путь в двудольном графе, для любых двух соседних ребер которого верно, что одно из них принадлежит паросочетанию [math]M[/math], а другое нет.


Определение:
Дополняющая цепь — чередующаяся цепь, у которой оба конца свободны.


Теорема о максимальном паросочетании и дополняющих цепях

Теорема:
Паросочетание [math]M[/math] в двудольном графе [math]G[/math] является максимальным тогда и только тогда, когда в [math]G[/math] нет дополняющей цепи.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]

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

[math]\Leftarrow[/math]

В доказательстве используются несколько новых понятий:

Определение:
Увеличивающая цепь — чередующаяся цепь, у которой оба конца свободны.


Определение:
Уменьшающая цепь — чередующаяся цепь, у которой оба конца покрыты.


Определение:
Сбалансированная цепь — чередующаяся цепь, у которой один конец свободен, а другой покрыт


Рассмотрим паросочетание [math]M[/math] в графе [math]G[/math] и предположим, что [math]M[/math] - не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно [math]M[/math]. Пусть [math]M'[/math] - другое паросочетание и [math]|M'|\gt |M|[/math]. Рассмотрим подграф [math]H[/math] графа [math]G[/math], образованный теми ребрами, которые входят в одно и только в одно из паросочетаний [math]M[/math], [math]M'[/math]. Иначе говоря, множеством ребер графа [math]H[/math] является симметрическая разность [math]M\oplus M'[/math]. В графе [math]H[/math] каждая вершина инцидентна не более чем двум ребрам (одному из [math]M[/math] и одному из [math]M'[/math] ), т.е. имеет степень не более двух. В таком графе каждая компонента связности - путь или цикл. В каждом из этих путей и циклов чередуются ребра из [math]M[/math] и [math]M'[/math]. Так как [math]|M'|\gt |M|[/math], имеется компонента, в которой ребер из [math]M'[/math] содержится больше, чем ребер из [math]M[/math]. Это может быть только путь, у которого оба концевых ребра принадлежат [math]M'[/math]. Заметим, что относительно [math]M[/math] этот путь является увеличивающей (дополняющей) цепью.
[math]\triangleleft[/math]

Литература

  • Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2