105
правок
Изменения
Новая страница: «==Определения== {{Определение|definition= Паросочетанием <tex>M</tex> в графе <tex>G</tex> называется такое …»
==Определения==
{{Определение|definition=
Паросочетанием <tex>M</tex> в графе <tex>G</tex> называется такое подмножество
множества ребер графа <tex>Е</tex>, что каждая вершина <tex>G</tex> инцидентна
не более чем одному ребру из <tex>M</tex>.
}}
{{Определение|definition=
Максимальным паросочетанием <tex>M</tex> в графе <tex>G</tex> называется
паросочетание максимальной мощности.
}}
{{Определение|definition=
Вершинным покрытием <tex>С</tex> графа <tex>G</tex> называется такое подмножество
множества вершин графа <tex>V</tex>, что каждому ребру <tex>G</tex> инцидентна
хотя бы одна вершина из <tex>С</tex>.
}}
{{Определение|definition=
Минимальным вершинным покрытием <tex>С</tex> графа <tex>G</tex> называется
вершинное покрытие минимальной мощности.
}}
{{Определение|definition=
Паросочетанием <tex>M</tex> в графе <tex>G</tex> называется такое подмножество
множества ребер графа <tex>Е</tex>, что каждая вершина <tex>G</tex> инцидентна
не более чем одному ребру из <tex>M</tex>.
}}
{{Определение|definition=
Максимальным паросочетанием <tex>M</tex> в графе <tex>G</tex> называется
паросочетание максимальной мощности.
}}
{{Определение|definition=
Вершинным покрытием <tex>С</tex> графа <tex>G</tex> называется такое подмножество
множества вершин графа <tex>V</tex>, что каждому ребру <tex>G</tex> инцидентна
хотя бы одна вершина из <tex>С</tex>.
}}
{{Определение|definition=
Минимальным вершинным покрытием <tex>С</tex> графа <tex>G</tex> называется
вершинное покрытие минимальной мощности.
}}
