Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях — различия между версиями
Leugenea (обсуждение | вклад) м (Поправил корявое определение) |
(см также) |
||
(не показаны 23 промежуточные версии 8 участников) | |||
Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
− | |definition= '''Паросочетание''' <tex>M</tex> в двудольном графе — произвольное множество | + | |id=matching_def |
+ | |definition= '''Паросочетание''' (англ. ''matсhing'') <tex>M</tex> в двудольном графе — произвольное множество рёбер двудольного графа, такое что никакие два ребра не имеют общей вершины.}} | ||
{{Определение | {{Определение | ||
− | |definition= Вершины двудольного графа, инцидентные | + | |definition= Вершины двудольного графа, инцидентные рёбрам паросочетания <tex>M</tex>, называются '''покрытыми''' (англ. ''matched''), а неинцидентные — '''свободными''' (англ. ''unmatched'').}} |
{{Определение | {{Определение | ||
− | |definition= ''' | + | |definition= '''Числом рёберного покрытия''' (англ. ''edge covering number'') называется размер минимального рёберного покрытии графа <tex>G</tex> и обозначается через <tex>\rho(G)</tex>.}} |
{{Определение | {{Определение | ||
− | |definition= '''Дополняющая цепь''' — чередующаяся цепь, у которой оба конца свободны.}} | + | |definition= Число рёбер в наибольшем паросочетании графа <tex>G</tex> называется '''числом паросочетания''' (англ. ''matching number'').}} |
+ | {{Определение | ||
+ | |id = maximal_matching | ||
+ | |definition= '''Максимальное паросочетание''' (англ. ''maximal matching'') — это такое паросочетание <tex>M</tex> в графе <tex>G</tex>, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания.}} | ||
+ | Другими словами, паросочетание <tex>M</tex> графа <tex>G</tex> является максимальным, если любое ребро в <tex>G</tex> имеет непустое пересечение по крайней мере с одним ребром из <tex>M</tex>. | ||
+ | |||
+ | {{Определение | ||
+ | |id = perfect_matching | ||
+ | |definition= Паросочетание <tex>M</tex> графа <tex>G</tex> называется '''совершенным (или полным)''' (англ. ''perfect matching''), если оно покрывает все вершины графа.}} | ||
+ | {{Определение | ||
+ | |definition= '''Чередующаяся цепь''' (англ. ''alternating path'') — путь в двудольном графе, для любых двух соседних рёбер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}} | ||
+ | {{Определение | ||
+ | |definition= '''Дополняющая цепь (или увеличивающая цепь)''' (англ. ''augmenting path'') — чередующаяся цепь, у которой оба конца свободны.}} | ||
+ | {{Определение | ||
+ | |definition= '''Уменьшающая цепь''' (англ. ''reduce path'') — чередующаяся цепь, у которой оба конца покрыты.}} | ||
+ | {{Определение | ||
+ | |definition= '''Сбалансированная цепь''' (англ. ''balanced path'') — чередующаяся цепь, у которой один конец свободен, а другой покрыт.}} | ||
+ | |||
+ | == Свойства == | ||
+ | |||
+ | В любом графе без изолированных вершин, число паросочетания и число рёберного покрытия в сумме дают число вершин. Если существует совершенное паросочетание, то оба числа равны <tex>|V|/2</tex>. | ||
+ | |||
+ | == Пример максимального и полного паросочетания, чередующейся цепи == | ||
+ | |||
+ | {|align="center" | ||
+ | |-valign="center" | ||
+ | |[[Файл: Maximal matching.jpg|thumb|210px|<font color=red>красные рёбра</font> являются рёбрами максимального паросочетания]] | ||
+ | |[[Файл: Perfect_matching.jpg|thumb|245px|<font color=red>красные рёбра</font> являются рёбрами полного паросочетания.]] | ||
+ | |[[Файл: Alternating_path.jpg|thumb|210px|Пусть <font color=red>красные рёбра</font> принадлежат паросочетанию <tex>M</tex>, а <font color=blue>синие</font> не принадлежат, тогда чередующаяся цепь: <tex>1-8-4-6-3-7</tex>]] | ||
+ | |} | ||
== Теорема о максимальном паросочетании и дополняющих цепях == | == Теорема о максимальном паросочетании и дополняющих цепях == | ||
{{Теорема | {{Теорема | ||
+ | |id=theorem1 | ||
|statement= | |statement= | ||
Паросочетание <tex>M</tex> в двудольном графе <tex>G</tex> является максимальным тогда и только тогда, когда в <tex>G</tex> нет дополняющей цепи. | Паросочетание <tex>M</tex> в двудольном графе <tex>G</tex> является максимальным тогда и только тогда, когда в <tex>G</tex> нет дополняющей цепи. | ||
Строка 18: | Строка 49: | ||
<tex>\Rightarrow</tex> | <tex>\Rightarrow</tex> | ||
− | Пусть в двудольном графе <tex>G</tex> с максимальным паросочетанием <tex>M</tex> существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль | + | Пусть в двудольном графе <tex>G</tex> с максимальным паросочетанием <tex>M</tex> существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль неё все рёбра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть <tex>M</tex> не являлось максимальным. Противоречие. |
<tex>\Leftarrow</tex> | <tex>\Leftarrow</tex> | ||
− | + | Рассмотрим паросочетание <tex>M</tex> в графе <tex>G</tex> и предположим, что <tex>M</tex> {{---}} не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно <tex>M</tex>. Пусть <tex>M'</tex> {{---}} другое паросочетание и <tex>|M'|>|M|</tex>. Рассмотрим подграф <tex>H</tex> графа <tex>G</tex>, образованный теми рёбрами, которые входят в одно и только в одно из паросочетаний <tex>M</tex>, <tex>M'</tex>. Иначе говоря, множеством рёбер графа <tex>H</tex> является симметрическая разность <tex>M\oplus M'</tex>. В графе <tex>H</tex> каждая вершина инцидентна не более чем двум рёбрам (одному из <tex>M</tex> и одному из <tex>M'</tex> ), т.е. имеет степень не более двух. В таком графе каждая компонента связности {{---}} путь или цикл. В каждом из этих путей и циклов чередуются рёбра из <tex>M</tex> и <tex>M'</tex>. Так как <tex>|M'|>|M|</tex>, имеется компонента, в которой рёбер из <tex>M'</tex> содержится больше, чем рёбер из <tex>M</tex>. Это может быть только путь, у которого оба концевых ребра принадлежат <tex>M'</tex>. Заметим, что относительно <tex>M</tex> этот путь является увеличивающей (дополняющей) цепью. | |
− | {{ | + | }} |
− | |||
− | |||
− | | | ||
− | |||
− | | | ||
− | + | ==См. также== | |
− | + | * [[Теорема Холла]] | |
+ | * [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] | ||
+ | * [[Связь вершинного покрытия и независимого множества]] | ||
− | == | + | == Источники информации == |
− | * Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' | + | * [http://en.wikipedia.org/wiki/Matching_%28graph_theory%29 Wikipedia {{---}} Matching] |
+ | * [https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 Википедия {{---}} Паросочетание] | ||
+ | * Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. стр. 227-232 '''ISBN 978-5-8114-1068-2''' | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Задача о паросочетании]] | [[Категория: Задача о паросочетании]] |
Версия 22:24, 22 ноября 2018
Содержание
Паросочетание в двудольном графе
Определение: |
Паросочетание (англ. matсhing) | в двудольном графе — произвольное множество рёбер двудольного графа, такое что никакие два ребра не имеют общей вершины.
Определение: |
Вершины двудольного графа, инцидентные рёбрам паросочетания | , называются покрытыми (англ. matched), а неинцидентные — свободными (англ. unmatched).
Определение: |
Числом рёберного покрытия (англ. edge covering number) называется размер минимального рёберного покрытии графа | и обозначается через .
Определение: |
Число рёбер в наибольшем паросочетании графа | называется числом паросочетания (англ. matching number).
Определение: |
Максимальное паросочетание (англ. maximal matching) — это такое паросочетание | в графе , которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания.
Другими словами, паросочетание
графа является максимальным, если любое ребро в имеет непустое пересечение по крайней мере с одним ребром из .
Определение: |
Паросочетание | графа называется совершенным (или полным) (англ. perfect matching), если оно покрывает все вершины графа.
Определение: |
Чередующаяся цепь (англ. alternating path) — путь в двудольном графе, для любых двух соседних рёбер которого верно, что одно из них принадлежит паросочетанию | , а другое нет.
Определение: |
Дополняющая цепь (или увеличивающая цепь) (англ. augmenting path) — чередующаяся цепь, у которой оба конца свободны. |
Определение: |
Уменьшающая цепь (англ. reduce path) — чередующаяся цепь, у которой оба конца покрыты. |
Определение: |
Сбалансированная цепь (англ. balanced path) — чередующаяся цепь, у которой один конец свободен, а другой покрыт. |
Свойства
В любом графе без изолированных вершин, число паросочетания и число рёберного покрытия в сумме дают число вершин. Если существует совершенное паросочетание, то оба числа равны
.Пример максимального и полного паросочетания, чередующейся цепи
Теорема о максимальном паросочетании и дополняющих цепях
Теорема: |
Паросочетание в двудольном графе является максимальным тогда и только тогда, когда в нет дополняющей цепи. |
Доказательство: |
Пусть в двудольном графе с максимальным паросочетанием существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль неё все рёбра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть не являлось максимальным. Противоречие.Рассмотрим паросочетание в графе и предположим, что — не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно . Пусть — другое паросочетание и . Рассмотрим подграф графа , образованный теми рёбрами, которые входят в одно и только в одно из паросочетаний , . Иначе говоря, множеством рёбер графа является симметрическая разность . В графе каждая вершина инцидентна не более чем двум рёбрам (одному из и одному из ), т.е. имеет степень не более двух. В таком графе каждая компонента связности — путь или цикл. В каждом из этих путей и циклов чередуются рёбра из и . Так как , имеется компонента, в которой рёбер из содержится больше, чем рёбер из . Это может быть только путь, у которого оба концевых ребра принадлежат . Заметим, что относительно этот путь является увеличивающей (дополняющей) цепью. |
См. также
- Теорема Холла
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
Источники информации
- Wikipedia — Matching
- Википедия — Паросочетание
- Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. стр. 227-232 ISBN 978-5-8114-1068-2