Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах — различия между версиями
(→Минимальное вершинное покрытие) |
м (rollbackEdits.php mass rollback) |
||
(не показано 16 промежуточных версий 7 участников) | |||
Строка 1: | Строка 1: | ||
− | == | + | ==Минимальное вершинное покрытие== |
− | |||
{{Определение|definition= | {{Определение|definition= | ||
− | ''' | + | '''Вершинным покрытием''' ''(англ. vertex covering)'' графа <tex>G=(V,E)</tex> называется такое подмножество <tex>S</tex> множества вершин графа <tex>V</tex>, что любое ребро этого графа инцидентно хотя бы одной вершине из множества <tex>S</tex>. |
+ | }} | ||
+ | {{Определение|definition= | ||
+ | '''Минимальным вершинным покрытием''' ''(англ. minimum vertex covering)'' графа <tex>G=(V,E)</tex> называется вершинное покрытие, состоящее из наименьшего числа вершин. | ||
}} | }} | ||
− | + | [[Файл:Cover.jpg|left|thumb|300px|Множество вершин красного цвета — минимальное вершинное покрытие.]] | |
− | [[Файл:Cover.jpg|thumb| | + | <br clear="all"/> |
− | + | ===Теорема о мощности минимального вершинного покрытия и максимального паросочетания=== | |
− | + | {{Определение|definition= | |
− | + | '''Максимальным''' [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|'''паросочетанием''']] ''(англ. maximum matching)'' в [[Двудольные графы и раскраска в 2 цвета|двудольном графе]] <tex>G</tex> называется паросочетание максимальной мощности. | |
− | {{Определение | ||
− | ''' | ||
}} | }} | ||
− | + | {{Теорема | |
− | + | |author=Кёниг | |
− | + | |neat = neat|statement= | |
− | |||
− | |||
− | = | ||
− | |||
− | |||
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия. | В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия. | ||
|proof= | |proof= | ||
− | Пусть в <tex>G</tex> построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания | + | Пусть в <tex>G</tex> построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания — так, чтобы они шли из левой доли в правую. Запустим [[Обход_в_глубину,_цвета_вершин|обход в глубину]] из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода. |
− | Тогда <tex>L = L^+ \cup L^-</tex>, <tex>R = R^+ \cup R^-</tex>, где <tex>L, R</tex> | + | Тогда <tex>L = L^+ \cup L^-</tex>, <tex>R = R^+ \cup R^-</tex>, где <tex>L, R</tex> — правая и левая доли соответственно, <tex>L^+, R^+</tex> — вершины правой и левой доли, посещенные обходом, <tex>L^-, R^-</tex> — не посещенные обходом вершины. |
Тогда в <tex>G</tex> могут быть следующие ребра: | Тогда в <tex>G</tex> могут быть следующие ребра: | ||
− | [[Файл:bipartdfs_right.jpg|thumb| | + | [[Файл:bipartdfs_right.jpg|thumb|center|300px|Доли <tex>L^+, L^-, R^+, R^-</tex> и ребра между ними.]] |
*Из вершин <tex>L^+</tex> в вершины <tex>R^+</tex> и из вершин <tex>R^+</tex> в вершины <tex>L^+</tex>. | *Из вершин <tex>L^+</tex> в вершины <tex>R^+</tex> и из вершин <tex>R^+</tex> в вершины <tex>L^+</tex>. | ||
*Из вершин <tex>L^-</tex> в вершины <tex>R^-</tex> и из вершин <tex>R^-</tex> в вершины <tex>L^-</tex>. | *Из вершин <tex>L^-</tex> в вершины <tex>R^-</tex> и из вершин <tex>R^-</tex> в вершины <tex>L^-</tex>. | ||
*Из вершин <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>L^+,L^-,R^+,R^-</tex>. | |
− | + | #В качестве результата взять <tex>L^- \cup R^+</tex>. | |
+ | |||
+ | ==См. также == | ||
+ | *[[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]] | ||
+ | *[[Связь_вершинного_покрытия_и_независимого_множества|Связь вершинного покрытия и независимого множества]] | ||
− | == Источники == | + | ==Источники информации== |
− | + | * [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) Википедия {{---}} Теорема Кёнига] | |
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Задача о паросочетании]] | [[Категория: Задача о паросочетании]] |
Текущая версия на 19:25, 4 сентября 2022
Минимальное вершинное покрытие
Определение: |
Вершинным покрытием (англ. vertex covering) графа | называется такое подмножество множества вершин графа , что любое ребро этого графа инцидентно хотя бы одной вершине из множества .
Определение: |
Минимальным вершинным покрытием (англ. minimum vertex covering) графа | называется вершинное покрытие, состоящее из наименьшего числа вершин.
Теорема о мощности минимального вершинного покрытия и максимального паросочетания
Определение: |
Максимальным паросочетанием (англ. maximum matching) в двудольном графе называется паросочетание максимальной мощности. |
Теорема (Кёниг): |
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия. |
Доказательство: |
Пусть в обход в глубину из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода. Тогда , , где — правая и левая доли соответственно, — вершины правой и левой доли, посещенные обходом, — не посещенные обходом вершины. Тогда в могут быть следующие ребра: построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания — так, чтобы они шли из левой доли в правую. Запустим
Очевидно, что ребер из в и из в быть не может. Ребер из в быть не может, т.к. если такое ребро существует, то оно — ребро паросочетания. Тогда вершина насыщена паросочетанием. Но т.к. , то в нее можно дойти из какой-то ненасыщенной вершины левой доли. Значит, существует ребро . Но тогда инцидентны два ребра из паросочетания. Противоречие.Заметим, что минимальным вершинным покрытием Тогда является либо , либо , либо . В не насыщенных паросочетанием вершин быть не может, т.к. иначе в существует дополняющая цепь, что противоречит максимальности построенного паросочетания. В свободных вершин быть не может, т.к. все они должны находиться в . Тогда т.к. ребер из паросочетания между и нет, то каждому ребру максимального паросочетания инцидентна ровно одна вершина из . равна мощности максимального паросочетания. Множество вершин является минимальным вершинным покрытием. Значит мощность максимального паросочетания равна мощности минимального вершинного покрытия. |
Алгоритм построения минимального вершинного покрытия
Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа:
- Построить максимальное паросочетание.
- Ориентировать ребра:
- Из паросочетания — из правой доли в левую.
- Не из паросочетания — из левой доли в правую.
- Запустить обход в глубину из всех свободных вершин левой доли, построить множества .
- В качестве результата взять .