\Section{Marriage Problem, покраска рёбер графа}{25 марта}{Илья Ольховский}
\Subsection{Marriage Problem (stable matching)}

 Хоть это и не всем нравится, я буду придерживаться терминологии ``девушек/юношей''. Имеется $n$ юношей и $m$ девушек. У каждого юноши и у каждой девушки есть список нравящихся им представителей противоположного пола, причём список упорядочен по приоритету. Необходимо их стабильно поженить.
 \begin{MyItemize}
 	\item $x.List$ -- список нравящихся $x$
 	\item $x.Pair$ -- выбранный в пару $x$
 	\item $x.charm(y)$ -- привлекательность $y$ с точки зрения $x$ (позиция в списке)
 \end{MyItemize}
 
 Паросочетание $M$ называется стабильным, если не существует ребра 
 $(boy,girl)\notin M \colon boy.charm(girl)>boy.charm(boy.Pair) \wedge girl.charm(boy)>girl.charm(girl.Pair)$, 
 то есть, нет эдаких Гурова и Анны Сергеевны, которым хочется быть друг с другом больше, 
 чем со своими супругами (при этом мы считаем, что если юноша ни на ком не женат, то он женат на девушке с нулевой привлекательностью)
 
  Задача -- собственно найти стабильное паросочетание.
  
  \Subsection{Технические моменты}
  
   Нам потребуется быстро понимать, кто из двух юношей больше интересует девушку. 
   Для этого можно завести хеш-таблицу, которая по паре $(x, y)$ возвращает $x.charm(y)$. 
   Ещё можно просто отсортировать подсчётом все тройки (наши рёбра) $(boy, girl, c):\; boy \in girl.List, c = girl.charm(boy)$, 
   а затем пробежаться по всем спискам юношей и для каждой девушки $x$ в списке юноши $y$ запомнить $x.charm(y)$.
   
   \Subsection{Алгоритм}
   
    Так называемый ``алгоритм отложенного согласия''.
    \begin{enumerate}
    	\item  Сначала юноши предлагают себя самым привлекательным с их точки зрения девушкам. Девушки среди всех юношей выбирают наиболее предпочтительных и говорят им ``я подумаю'', остальным говорят ``нет''.
    
       \item Далее все отвергнутые юноши выкидывают из своих списков соответствующих девушек и пробуют удачу со следующими девушками (в их списках). При этом если некоторой девушке поступило более заманчивое предложение, она говорит ``нет'' своему текущему кандидату (и он переходит в мн-во отвергнутых) и ``я подумаю'' -- новому.
	   \item Процесс продолжается пока не закончатся отвергнутые юноши с непустыми списками.
	 \end{enumerate}
	 
	  Это образно и на пальцах. В нашей реализации мы будем женить юношей по одному.
	  \begin{code}
GetPair(boy):
  while !boy.List.empty():
    girl = boy.List.top(), boy.List.delete(girl) //`достаём топовую девушку`
    if girl.Pair == -1: //`если мы первые, кто делает ей предложение, то выходим`
      girl.Pair = boy, break;
    else:
      if girl.charm(girl.Pair) < girl.charm(boy): //`если мы лучше текущего кандидата`
        swap(girl.Pair, boy) //`продолжаем искать пару уже для него`
FOR boy = 1..n
  GetPair(boy)
	 \end{code}
	 
	 \Subsection{Доказательство корректности}
	 
	  Докажем, что получившееся паросочетание (все пары $(girl, girl.Pair)$) стабильно. Пусть
	  $$\exists (boy,girl)\notin M \colon boy.charm(girl)>boy.charm(boy.Pair) \wedge girl.charm(boy)>girl.charm(girl.Pair)$$
	   В некоторый момент $boy$ делал предложение $girl$, так как в итоге ему досталась девушка с меньшим приоритетом, а юноши предлагают себя девушкам в порядке убывания приоритета.
	   
	    Однако в итоге $girl$ достался юноша с меньшим приоритетом, чем $boy$. Это невозможно, потому что по алгоритму:
	    \begin{MyItemize}
	    	\item Юноша отвергается только если у текущего кандидата приоритет не меньше.
	    	\item Для каждой девушки $girl$ приоритет $girl.Pair$ может только увеличиваться в процессе алгоритма.
	    \end{MyItemize}
	    
	    \Subsection{Замечания}
	     \begin{MyItemize}
	     	\item В графе может быть несколько стабильных паросочетаний
	     	\item Несмотря на то, что выбирают у нас девушки, алгоритм получает паросочетание, наилучшее для юношей. 
	     	  Соответственно, если обменять доли местами, получится паросочетание, наилучшее для девушек.
	     \end{MyItemize}
	 
	 \Subsection{Покраска рёбер графа}
	 
	   Задача правильной покраска рёбер графа состоит в том, чтобы каждое ребро покрасить в некоторый цвет так,
	   чтобы для каждой вершины все инцидентные рёбра были разных цветов, то есть, чтобы не было одноцветных рёбер с общими концами.
	   Нам, естественно, интересно минимизировать число цветов.
	   Эквивалентная переформулировка: разбить рёбра графа на минимальное число паросочетаний (каждый цвет порождает паросочетание и наоборот 
	   любое паросочетание можно покрасить в один цет).
	   
	   Пусть $D$ -- максимальная степень вершины графа.
	    
	   \begin{Thm}\emph{Визинга}.
	    Существует правильная раскраска рёбер в $D$ или в $D+1$ цвет.
	   \end{Thm}
    
       \emph{Без доказательства.}

       \vspace*{0.5em}
       Понятно, что меньшим числом цветов, чем $D$, не обойтись. 
       Теорема Визинга так же даёт конструктивный алгоритм, красящий любой граф в $D+1$ цвет. 
       Вопрос же о том, можно ли покрасить граф в $D$ цветов в общем случае является \t{NP}-трудной задачей.
	     
	     \Subsection{Двудольные графы}
	     
	      Тем не менее, двудольные графы графы несложно красятся в $D$ цветов:
	      \begin{enumerate}
	      	\item Сделаем из графа $D$-регулярный. 
	      	  Для этого просто добавим несколько вершин, чтобы сделать доли равными и соединим рёбрами вершины степени меньше $D$. 
	      	  Так как из левой доли выходит столько же рёбер, сколько входит в правую долю, если в левой доле есть вершина степени меньше $D$,
	      	  то и в правой доли есть вершина степени меньше $D$.
	      	\item В $D$ регулярном графе обязательно найдётся совершенное паросочетание. 
%	      	(посмотрим на мин. контролирующее мн-во. 
%  	      	  Если его размер меньше $n$, то в него входит слишком много рёбер). 
 			\item Найдём совершенное паросочетание и удалим из графа, покрасив все удалённые рёбра в первый цвет. У нас остался ($D{-}1$)-регулярный граф.
	      	\item Повторяем, на каждом шаге крася рёбра в новый цвет, пока не закончатся рёбра. 
	      	\item Очевидно, мы сделаем $D$ итераций, то есть задействуем ровно $D$ цветов. Happy End.
	      \end{enumerate}
 