25
правок
Изменения
Нет описания правки
|definition= Вершины двудольного графа, инцидентные ребрам паросочетания <tex>M</tex>, называются '''покрытыми''' (англ. ''matched''), а неинцидентные — '''свободными''' (англ. ''unmatched'').}}
{{Определение
|definition= Число вершин в наименьшем покрытии графа <tex>G</tex> называется '''числом покрытия (или числом вершинного Числом реберного покрытия)''' (англ. ''edge covering number'') называется размер минимального реберного покрытии графа <tex>G</tex> и обозначается через <tex>\rho(G)</tex>.}}
{{Определение
|definition= Число ребер в наибольшем паросочетании графа <tex>G</tex> называется '''числом паросочетания''' (англ. ''matching number'').}}
В любом графе без изолированных вершин, число паросочетания и число рёберного покрытия в сумме дают число вершин. Если существует совершенное паросочетание, то оба числа равны <tex>|V|/2</tex>.
== Пример максимального паросочетания ==
[[Файл: Maximal matching.jpg|thumb|210px|center|<font color=red>красные ребра</font> являются ребрами максимального паросочетания]]
== Теорема о максимальном паросочетании и дополняющих цепях ==
