Изменения

Перейти к: навигация, поиск
м
ё
{{Определение
|id=matching_def
|definition= '''Паросочетание''' (англ. ''matсhing'') <tex>M</tex> в двудольном графе — произвольное множество ребер рёбер двудольного графа, такое что никакие два ребра не имеют общей вершины.}}
{{Определение
|definition= Вершины двудольного графа, инцидентные ребрам рёбрам паросочетания <tex>M</tex>, называются '''покрытыми''' (англ. ''matched''), а неинцидентные — '''свободными''' (англ. ''unmatched'').}}
{{Определение
|definition= '''Числом реберного рёберного покрытия''' (англ. ''edge covering number'') называется размер минимального реберного рёберного покрытии графа <tex>G</tex> и обозначается через <tex>\rho(G)</tex>.}}
{{Определение
|definition= Число ребер рёбер в наибольшем паросочетании графа <tex>G</tex> называется '''числом паросочетания''' (англ. ''matching number'').}}
{{Определение
|definition= '''Максимальное паросочетание''' (англ. ''maximal matching'') — это такое паросочетание <tex>M</tex> в графе <tex>G</tex>, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем ребрам рёбрам паросочетания.}}
Другими словами, паросочетание <tex>M</tex> графа <tex>G</tex> является максимальным, если любое ребро в <tex>G</tex> имеет непустое пересечение по крайней мере с одним ребром из <tex>M</tex>.
|definition= Паросочетание <tex>M</tex> графа <tex>G</tex> называется '''совершенным (или полным)''' (англ.''perfect matching''), если оно покрывает все вершины графа.}}
{{Определение
|definition= '''Чередующаяся цепь''' (англ. ''alternating path'') — путь в двудольном графе, для любых двух соседних ребер рёбер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}
{{Определение
|definition= '''Дополняющая цепь (или увеличивающая цепь)''' (англ. ''augmenting path'') — чередующаяся цепь, у которой оба конца свободны.}}
{|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>\Rightarrow</tex>
Пусть в двудольном графе <tex>G</tex> с максимальным паросочетанием <tex>M</tex> существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее неё все ребрарёбра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть <tex>M</tex> не являлось максимальным. Противоречие.
<tex>\Leftarrow</tex>
Рассмотрим паросочетание <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> этот путь является увеличивающей (дополняющей) цепью.
}}

Навигация