37
правок
Изменения
→Пример максимального паросочетания
В любом графе без изолированных вершин, число паросочетания и число рёберного покрытия в сумме дают число вершин. Если существует совершенное паросочетание, то оба числа равны <tex>|V|/2</tex>.
== Пример максимального и полного паросочетания ==
{|align="center" |-valign="center" |[[Файл: Maximal matching.jpg|thumb|210px|center<font color=red>красные ребра</font> являются ребрами максимального паросочетания]] |[[Файл: Perfect_matching.jpg|thumb|245px|<font color=red>красные ребра</font> являются ребрами максимального полного паросочетания.]] |}
== Теорема о максимальном паросочетании и дополняющих цепях ==
