Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 12 промежуточных версий 6 участников) | |||
Строка 1: | Строка 1: | ||
− | + | ==Минимальное вершинное покрытие== | |
− | + | {{Определение|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|Множество вершин красного цвета — минимальное вершинное покрытие.]] | |
− | + | <br clear="all"/> | |
− | [[Файл:Cover.jpg|300px | + | ===Теорема о мощности минимального вершинного покрытия и максимального паросочетания=== |
− | |||
− | Множество вершин красного цвета — минимальное вершинное покрытие. | ||
− | <br/> | ||
− | |||
− | |||
− | |||
− | == | ||
− | |||
{{Определение|definition= | {{Определение|definition= | ||
− | '''Максимальным''' [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|'''паросочетанием''']] (англ. | + | '''Максимальным''' [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|'''паросочетанием''']] ''(англ. maximum matching)'' в [[Двудольные графы и раскраска в 2 цвета|двудольном графе]] <tex>G</tex> называется паросочетание максимальной мощности. |
}} | }} | ||
− | + | ||
− | {{Теорема|neat = neat|statement= | + | {{Теорема |
+ | |author=Кёниг | ||
+ | |neat = neat|statement= | ||
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия. | В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия. | ||
|proof= | |proof= | ||
Строка 40: | Строка 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>|L^- \cup R^+|</tex> равна мощности максимального паросочетания. Множество вершин <tex>L^- \cup R^+</tex> является минимальным вершинным покрытием. Значит мощность максимального паросочетания равна мощности минимального вершинного покрытия. |
}} | }} | ||
===Алгоритм построения минимального вершинного покрытия=== | ===Алгоритм построения минимального вершинного покрытия=== | ||
Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа: | Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа: | ||
− | + | #Построить максимальное паросочетание. | |
− | + | #Ориентировать ребра: | |
− | + | #*Из паросочетания — из правой доли в левую. | |
− | + | #*Не из паросочетания — из левой доли в правую. | |
− | + | #Запустить обход в глубину из всех свободных вершин левой доли, построить множества <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) в двудольном графе называется паросочетание максимальной мощности. |
Теорема (Кёниг): |
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия. |
Доказательство: |
Пусть в обход в глубину из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода. Тогда , , где — правая и левая доли соответственно, — вершины правой и левой доли, посещенные обходом, — не посещенные обходом вершины. Тогда в могут быть следующие ребра: построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания — так, чтобы они шли из левой доли в правую. Запустим
Очевидно, что ребер из в и из в быть не может. Ребер из в быть не может, т.к. если такое ребро существует, то оно — ребро паросочетания. Тогда вершина насыщена паросочетанием. Но т.к. , то в нее можно дойти из какой-то ненасыщенной вершины левой доли. Значит, существует ребро . Но тогда инцидентны два ребра из паросочетания. Противоречие.Заметим, что минимальным вершинным покрытием Тогда является либо , либо , либо . В не насыщенных паросочетанием вершин быть не может, т.к. иначе в существует дополняющая цепь, что противоречит максимальности построенного паросочетания. В свободных вершин быть не может, т.к. все они должны находиться в . Тогда т.к. ребер из паросочетания между и нет, то каждому ребру максимального паросочетания инцидентна ровно одна вершина из . равна мощности максимального паросочетания. Множество вершин является минимальным вершинным покрытием. Значит мощность максимального паросочетания равна мощности минимального вершинного покрытия. |
Алгоритм построения минимального вершинного покрытия
Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа:
- Построить максимальное паросочетание.
- Ориентировать ребра:
- Из паросочетания — из правой доли в левую.
- Не из паросочетания — из левой доли в правую.
- Запустить обход в глубину из всех свободных вершин левой доли, построить множества .
- В качестве результата взять .
См. также
- Теорема о максимальном паросочетании и дополняющих цепях
- Связь вершинного покрытия и независимого множества