Изменения

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

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

|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> / 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\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> этот путь является увеличивающей (дополняющей) цепью.

* [http://en.wikipedia.org/wiki/Matching_%28graph_theory%29 Wikipedia {{---}} Matching]* [https://ru.wikipedia.org — Matching (graph theory)/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'''