Изменения

|id=matching_def|definition= '''Паросочетание ''' (англ. ''matсhing'') <tex>M</tex> в двудольном графе - — произвольное множество ребер рёбер двудольного графа, такое что никакие два ребра не имеют общей вершины. Обозначается как <tex>M</tex>.}}

|definition= Вершины двудольного графа, инцидентные ребрам рёбрам паросочетания <tex>M</tex>, называются '''покрытыми''' (англ. ''matched''), а неинцидентные - — '''свободными''' (англ. ''unmatched'').}}

|definition= Чередующаяся цепь - путь составленный из ребер двудольного '''Числом рёберного покрытия''' (англ. ''edge covering number'') называется размер минимального рёберного покрытии графа, в котором для любых двух соседних ребер выполняется, что одно из них принадлежит паросочетанию <tex>MG</tex> и обозначается через <tex>\rho(G)</tex>, а другое нет.}}

|definition= Число рёбер в наибольшем паросочетании графа <tex>G</tex> называется '''числом паросочетания''' (англ. ''matching number'').}}{{Определение|id = maximal_matching|definition= '''Максимальное паросочетание (по включению)''' (англ. ''maximal matching'') — это такое паросочетание <tex>M</tex> в графе <tex>G</tex>, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания.}}Другими словами, паросочетание <tex>M</tex> графа <tex>G</tex> является максимальным, если любое ребро в <tex>G</tex> имеет непустое пересечение по крайней мере с одним ребром из <tex>M</tex>.{{Определение|id = maximal_matching_size|definition= '''Максимальное паросочетание (по мощности)''' (англ. ''maximum cardinality matching'') — это паросочетание <tex>M</tex> в графе <tex>G</tex> максимальное по мощности.}} {{Определение|id = perfect_matching|definition= Паросочетание <tex>M</tex> графа <tex>G</tex> называется '''совершенным (или полным)''' (англ. ''perfect matching''), если оно покрывает все вершины графа.}}{{Определение|definition= '''Чередующаяся цепь''' (англ. ''alternating path'') — путь в двудольном графе, для любых двух соседних рёбер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}{{Определение|definition= '''Дополняющая цепь - (или увеличивающая цепь)''' (англ. ''augmenting path'') — чередующаяся цепь, у которой оба конца свободны.}}{{Определение|definition= '''Уменьшающая цепь''' (англ. ''reduce path'') — чередующаяся цепь, у которой оба конца покрыты.}}{{Определение|definition= '''Сбалансированная цепь''' (англ. ''balanced path'') — чередующаяся цепь, у которой один конец свободен, а другой покрыт.}} == Свойства == В любом графе без изолированных вершин, число паросочетания и число рёберного покрытия в сумме дают число вершин. Если существует совершенное паросочетание, то оба числа равны <tex>|V|/2</tex>. == Пример максимального и полного паросочетания, чередующейся цепи == {|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>]] |} 

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

В доказательстве используются несколько новых понятий:Рассмотрим паросочетание <tex>M</tex> в графе <tex>G</tex> и предположим, что <tex>M</tex> {{Определение|definition= Увеличивающая цепь - чередующаяся --}} не наибольшее. Докажем, что тогда имеется увеличивающая цепь, у которой оба конца свободныотносительно <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|definition= Уменьшающая цепь - чередующаяся цепь</tex>, имеется компонента, в которой рёбер из <tex>M'</tex> содержится больше, чем рёбер из <tex>M</tex>. Это может быть только путь, у которой которого оба конца покрытыконцевых ребра принадлежат <tex>M'</tex>. Заметим, что относительно <tex>M</tex> этот путь является увеличивающей (дополняющей) цепью.}} ==См. также==* [[Теорема Холла]]* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]* [[Связь вершинного покрытия и независимого множества]] == Источники информации ==* [http://en.wikipedia.org/wiki/Matching_%28graph_theory%29 Wikipedia {{Определение---}} Matching]|definition= Сбалансированная цепь * [https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 Википедия {{--- чередующаяся цепь}} Паросочетание]* Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, у которой один конец свободенматроиды, а другой покрыт}}алгоритмы. стр. 227-232 '''ISBN 978-5-8114-1068-2''' 

Рассмотрим паросочетание <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\otimes 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> этот путь является увеличивающей цепью.}}==Литература==структуры данных]]* Асанов М., Баранский В., Расин В. — Дискретная математика — Графы, матроиды, алгоритмы[[Категория: Задача о паросочетании]]