105
правок
Изменения
Нет описания правки
==Определения==
{{Определение|definition=
Паросочетанием <tex>M</tex> <tex>(matching)</tex> в графе <tex>G</tex> называется такое подмножествомножества ребер графа <tex>Е</tex>, что каждая вершина <tex>G</tex> инцидентнане более чем одному ребру из <tex>M</tex>.
}}
{{Определение|definition=
Максимальным паросочетанием <tex>MMM</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>СVС</tex>.
}}
{{Определение|definition=
Минимальным вершинным покрытием <tex>СMVС</tex> <tex>(minimum</tex> <tex>vertex</tex><tex>covering)</tex> графа <tex>G</tex> называетсявершинное покрытие минимальной мощности.
}}
