Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах — различия между версиями
| Строка 4: | Строка 4: | ||
что каждая вершина <tex>G</tex> инцидентна<br/> не более чем одному ребру из <tex>M</tex>. | что каждая вершина <tex>G</tex> инцидентна<br/> не более чем одному ребру из <tex>M</tex>. | ||
}} | }} | ||
| − | |||
{{Определение|definition= | {{Определение|definition= | ||
Максимальным паросочетанием <tex>MM</tex> <tex>(maximum</tex> <tex>matching)</tex> в графе <tex>G</tex> называется паросочетание | Максимальным паросочетанием <tex>MM</tex> <tex>(maximum</tex> <tex>matching)</tex> в графе <tex>G</tex> называется паросочетание | ||
максимальной мощности. | максимальной мощности. | ||
}} | }} | ||
| − | |||
| − | |||
{{Определение|definition= | {{Определение|definition= | ||
Вершинным покрытием <tex>VC</tex> <tex>(vertex</tex> <tex>covering)</tex> графа <tex>G</tex> называется такое подмножество множества вершин графа <tex>V</tex>, что каждому ребру <tex>G</tex><br/> инцидентна хотя бы одна вершина из <tex>VC</tex>. | Вершинным покрытием <tex>VC</tex> <tex>(vertex</tex> <tex>covering)</tex> графа <tex>G</tex> называется такое подмножество множества вершин графа <tex>V</tex>, что каждому ребру <tex>G</tex><br/> инцидентна хотя бы одна вершина из <tex>VC</tex>. | ||
| Строка 17: | Строка 14: | ||
Минимальным вершинным покрытием <tex>MVС</tex> <tex>(minimum</tex> <tex>vertex</tex> <tex>covering)</tex> графа <tex>G</tex> называется вершинное покрытие минимальной мощности. | Минимальным вершинным покрытием <tex>MVС</tex> <tex>(minimum</tex> <tex>vertex</tex> <tex>covering)</tex> графа <tex>G</tex> называется вершинное покрытие минимальной мощности. | ||
}} | }} | ||
| + | |||
==Связь MM и MVC в двудольном графе== | ==Связь MM и MVC в двудольном графе== | ||
{{Теорема|statement= | {{Теорема|statement= | ||
Версия 16:10, 15 декабря 2010
Определения
| Определение: |
| Паросочетанием в графе называется такое подмножество множества ребер графа ,
что каждая вершина инцидентна не более чем одному ребру из . |
| Определение: |
| Максимальным паросочетанием в графе называется паросочетание максимальной мощности. |
| Определение: |
| Вершинным покрытием графа называется такое подмножество множества вершин графа , что каждому ребру инцидентна хотя бы одна вершина из . |
| Определение: |
| Минимальным вершинным покрытием графа называется вершинное покрытие минимальной мощности. |
Связь MM и MVC в двудольном графе
| Теорема: |
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия. |
