37
правок
Изменения
добавлены примеры для определений
В любом графе без изолированных вершин, число паросочетания и число рёберного покрытия в сумме дают число вершин. Если существует совершенное паросочетание, то оба числа равны <tex>|V|/2</tex>.
== Пример максимального и полного паросочетания , чередующейся цепи ==
{|align="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>]]
|}
