Изменения
см также
{{Определение
|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 = 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>]] |} == Теорема о максимальном паросочетании и дополняющих цепях ==
{{Теорема
|aboutid=О максимальном паросочетании и дополняющих цепяхtheorem1
|statement=
Паросочетание <tex>M</tex> в двудольном графе <tex>G</tex> является максимальным тогда и только тогда, когда в <tex>G</tex> нет дополняющей цепи.
<tex>\Rightarrow</tex>
Пусть в двудольном графе <tex>G</tex> с максимальным паросочетанием <tex>M</tex> существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее неё все ребрарёбра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть <tex>M</tex> не являлось максимальным. Противоречие.
<tex>\Leftarrow</tex>