Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах — различия между версиями
Maksnov (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показано 9 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
− | == | + | ==Минимальное вершинное покрытие== |
{{Определение|definition= | {{Определение|definition= | ||
'''Вершинным покрытием''' ''(англ. vertex covering)'' графа <tex>G=(V,E)</tex> называется такое подмножество <tex>S</tex> множества вершин графа <tex>V</tex>, что любое ребро этого графа инцидентно хотя бы одной вершине из множества <tex>S</tex>. | '''Вершинным покрытием''' ''(англ. vertex covering)'' графа <tex>G=(V,E)</tex> называется такое подмножество <tex>S</tex> множества вершин графа <tex>V</tex>, что любое ребро этого графа инцидентно хотя бы одной вершине из множества <tex>S</tex>. | ||
Строка 27: | Строка 27: | ||
*Из вершин <tex>L^-</tex> в вершины <tex>R^+</tex>. | *Из вершин <tex>L^-</tex> в вершины <tex>R^+</tex>. | ||
− | Очевидно, что ребер из <tex>L^+</tex> в <tex>R^-</tex> и | + | Очевидно, что ребер из <tex>L^+</tex> в <tex>R^-</tex> и из <tex>R^+</tex> в <tex>L^-</tex> быть не может. |
− | Ребер | + | Ребер из <tex>R^-</tex> в <tex>L^+</tex> быть не может, т.к. если такое ребро <tex>uv</tex> существует, то оно — ребро паросочетания. Тогда вершина <tex>v</tex> насыщена паросочетанием. Но т.к. <tex>v \in L^+</tex>, то в нее можно дойти из какой-то ненасыщенной вершины левой доли. Значит, существует ребро <tex>wv, w \in R^+</tex>. Но тогда <tex>v</tex> инцидентны два ребра из паросочетания. Противоречие. |
Заметим, что минимальным вершинным покрытием <tex>G</tex> является либо <tex>L</tex>, либо <tex>R</tex>, либо <tex>L^- \cup R^+</tex>. | Заметим, что минимальным вершинным покрытием <tex>G</tex> является либо <tex>L</tex>, либо <tex>R</tex>, либо <tex>L^- \cup R^+</tex>. | ||
В <tex>R^+</tex> не насыщенных паросочетанием вершин быть не может, т.к. иначе в <tex>G</tex> существует дополняющая цепь, что противоречит максимальности построенного паросочетания. | В <tex>R^+</tex> не насыщенных паросочетанием вершин быть не может, т.к. иначе в <tex>G</tex> существует дополняющая цепь, что противоречит максимальности построенного паросочетания. | ||
В <tex>L^-</tex> свободных вершин быть не может, т.к. все они должны находиться в <tex>L^+</tex>. Тогда т.к. ребер из паросочетания между <tex>R^+</tex> | В <tex>L^-</tex> свободных вершин быть не может, т.к. все они должны находиться в <tex>L^+</tex>. Тогда т.к. ребер из паросочетания между <tex>R^+</tex> | ||
− | и <tex>L^-</tex> нет, то каждому ребру | + | и <tex>L^-</tex> нет, то каждому ребру максимального паросочетания инцидентна ровно одна вершина из <tex>L^- \cup R^+</tex>. |
Тогда <tex>|L^- \cup R^+|</tex> равна мощности максимального паросочетания. Множество вершин <tex>L^- \cup R^+</tex> является минимальным вершинным покрытием. Значит мощность максимального паросочетания равна мощности минимального вершинного покрытия. | Тогда <tex>|L^- \cup R^+|</tex> равна мощности максимального паросочетания. Множество вершин <tex>L^- \cup R^+</tex> является минимальным вершинным покрытием. Значит мощность максимального паросочетания равна мощности минимального вершинного покрытия. | ||
}} | }} | ||
Строка 43: | Строка 43: | ||
#*Из паросочетания — из правой доли в левую. | #*Из паросочетания — из правой доли в левую. | ||
#*Не из паросочетания — из левой доли в правую. | #*Не из паросочетания — из левой доли в правую. | ||
− | #Запустить обход в глубину из всех свободных вершин левой доли, построить множества <tex>L^+,L^-,R^+,R^- | + | #Запустить обход в глубину из всех свободных вершин левой доли, построить множества <tex>L^+,L^-,R^+,R^-</tex>. |
#В качестве результата взять <tex>L^- \cup R^+</tex>. | #В качестве результата взять <tex>L^- \cup R^+</tex>. | ||
==См. также == | ==См. также == | ||
− | [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]] | + | *[[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]] |
− | + | *[[Связь_вершинного_покрытия_и_независимого_множества|Связь вершинного покрытия и независимого множества]] | |
− | [[Связь_вершинного_покрытия_и_независимого_множества|Связь вершинного покрытия и независимого множества]] | ||
==Источники информации== | ==Источники информации== | ||
− | * [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) Теорема Кёнига] | + | * [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) Википедия {{---}} Теорема Кёнига] |
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Задача о паросочетании]] | [[Категория: Задача о паросочетании]] |
Текущая версия на 19:25, 4 сентября 2022
Содержание
Минимальное вершинное покрытие
Определение: |
Вершинным покрытием (англ. vertex covering) графа | называется такое подмножество множества вершин графа , что любое ребро этого графа инцидентно хотя бы одной вершине из множества .
Определение: |
Минимальным вершинным покрытием (англ. minimum vertex covering) графа | называется вершинное покрытие, состоящее из наименьшего числа вершин.
Теорема о мощности минимального вершинного покрытия и максимального паросочетания
Определение: |
Максимальным паросочетанием (англ. maximum matching) в двудольном графе называется паросочетание максимальной мощности. |
Теорема (Кёниг): |
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия. |
Доказательство: |
Пусть в обход в глубину из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода. Тогда , , где — правая и левая доли соответственно, — вершины правой и левой доли, посещенные обходом, — не посещенные обходом вершины. Тогда в могут быть следующие ребра: построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания — так, чтобы они шли из левой доли в правую. Запустим
Очевидно, что ребер из в и из в быть не может. Ребер из в быть не может, т.к. если такое ребро существует, то оно — ребро паросочетания. Тогда вершина насыщена паросочетанием. Но т.к. , то в нее можно дойти из какой-то ненасыщенной вершины левой доли. Значит, существует ребро . Но тогда инцидентны два ребра из паросочетания. Противоречие.Заметим, что минимальным вершинным покрытием Тогда является либо , либо , либо . В не насыщенных паросочетанием вершин быть не может, т.к. иначе в существует дополняющая цепь, что противоречит максимальности построенного паросочетания. В свободных вершин быть не может, т.к. все они должны находиться в . Тогда т.к. ребер из паросочетания между и нет, то каждому ребру максимального паросочетания инцидентна ровно одна вершина из . равна мощности максимального паросочетания. Множество вершин является минимальным вершинным покрытием. Значит мощность максимального паросочетания равна мощности минимального вершинного покрытия. |
Алгоритм построения минимального вершинного покрытия
Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа:
- Построить максимальное паросочетание.
- Ориентировать ребра:
- Из паросочетания — из правой доли в левую.
- Не из паросочетания — из левой доли в правую.
- Запустить обход в глубину из всех свободных вершин левой доли, построить множества .
- В качестве результата взять .
См. также
- Теорема о максимальном паросочетании и дополняющих цепях
- Связь вершинного покрытия и независимого множества