105
правок
Изменения
Нет описания правки
==Определения==
===Максимальное паросочетание===
{{Определение|definition=
Паросочетанием <tex>M</tex> <tex>(matching)</tex> в графе <tex>G</tex> называется такое подмножество множества ребер графа <tex>Е</tex>,
Максимальным паросочетанием <tex>MM</tex> <tex>(maximum</tex> <tex>matching)</tex> в графе <tex>G</tex> называется паросочетание максимальной мощности.
}}
===Минимальное вершинное покрытие===
{{Определение|definition=
Вершинным покрытием <tex>VC</tex> <tex>(vertex</tex> <tex>covering)</tex> графа <tex>G</tex> называется такое подмножество множества вершин графа <tex>V</tex>, что каждому ребру <tex>G</tex> инцидентна хотя бы одна вершина из <tex>VC</tex>.
