Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах — различия между версиями
(Новая страница: «==Определения== {{Определение|definition= Паросочетанием <tex>M</tex> в графе <tex>G</tex> называется такое …») |
|||
| Строка 1: | Строка 1: | ||
==Определения== | ==Определения== | ||
{{Определение|definition= | {{Определение|definition= | ||
| − | Паросочетанием <tex>M</tex> в графе <tex>G</tex> называется такое подмножество | + | Паросочетанием <tex>M</tex> <tex>(matching)</tex> в графе <tex>G</tex> называется такое подмножество множества ребер графа <tex>Е</tex>, что каждая вершина <tex>G</tex> инцидентна не более чем одному ребру из <tex>M</tex>. |
| − | множества ребер графа <tex>Е</tex>, что каждая вершина <tex>G</tex> инцидентна | ||
| − | не более чем одному ребру из <tex>M</tex>. | ||
}} | }} | ||
{{Определение|definition= | {{Определение|definition= | ||
| − | Максимальным паросочетанием <tex> | + | Максимальным паросочетанием <tex>MM</tex> <tex>(maximum</tex> <tex>matching)</tex> в графе <tex>G</tex> называется паросочетание максимальной мощности. |
| − | паросочетание максимальной мощности. | ||
}} | }} | ||
{{Определение|definition= | {{Определение|definition= | ||
| − | Вершинным покрытием <tex> | + | Вершинным покрытием <tex>VC</tex> <tex>(vertex</tex> <tex>covering)</tex> графа <tex>G</tex> называется такое подмножество множества вершин графа <tex>V</tex>, что каждому ребру <tex>G</tex> инцидентна хотя бы одна вершина из <tex>VС</tex>. |
| − | множества вершин графа <tex>V</tex>, что каждому ребру <tex>G</tex> инцидентна | ||
| − | хотя бы одна вершина из <tex> | ||
}} | }} | ||
{{Определение|definition= | {{Определение|definition= | ||
| − | Минимальным вершинным покрытием <tex> | + | Минимальным вершинным покрытием <tex>MVС</tex> <tex>(minimum</tex> <tex>vertex</tex><tex>covering)</tex> графа <tex>G</tex> называется вершинное покрытие минимальной мощности. |
| − | вершинное покрытие минимальной мощности. | ||
}} | }} | ||
Версия 01:27, 9 декабря 2010
Определения
| Определение: |
| Паросочетанием в графе называется такое подмножество множества ребер графа , что каждая вершина инцидентна не более чем одному ребру из . |
| Определение: |
| Максимальным паросочетанием в графе называется паросочетание максимальной мощности. |
| Определение: |
| Вершинным покрытием графа называется такое подмножество множества вершин графа , что каждому ребру инцидентна хотя бы одна вершина из . |
| Определение: |
| Минимальным вершинным покрытием графа называется вершинное покрытие минимальной мощности. |
