Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях — различия между версиями
Leugenea (обсуждение | вклад) м (Поправил корявое определение) |
|||
Строка 6: | Строка 6: | ||
|definition= Вершины двудольного графа, инцидентные ребрам паросочетания <tex>M</tex>, называются '''покрытыми''', а неинцидентные — '''свободными'''.}} | |definition= Вершины двудольного графа, инцидентные ребрам паросочетания <tex>M</tex>, называются '''покрытыми''', а неинцидентные — '''свободными'''.}} | ||
{{Определение | {{Определение | ||
− | |definition= '''Чередующаяся цепь''' — путь в двудольном графе, для любых двух соседних ребер которого | + | |definition= '''Чередующаяся цепь''' — путь в двудольном графе, для любых двух соседних ребер которого верно, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}} |
{{Определение | {{Определение | ||
|definition= '''Дополняющая цепь''' — чередующаяся цепь, у которой оба конца свободны.}} | |definition= '''Дополняющая цепь''' — чередующаяся цепь, у которой оба конца свободны.}} |
Версия 22:18, 10 июня 2013
Паросочетание в двудольном графе
Определение: |
Паросочетание | в двудольном графе — произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины.
Определение: |
Вершины двудольного графа, инцидентные ребрам паросочетания | , называются покрытыми, а неинцидентные — свободными.
Определение: |
Чередующаяся цепь — путь в двудольном графе, для любых двух соседних ребер которого верно, что одно из них принадлежит паросочетанию | , а другое нет.
Определение: |
Дополняющая цепь — чередующаяся цепь, у которой оба конца свободны. |
Теорема о максимальном паросочетании и дополняющих цепях
Теорема: | ||||||
Паросочетание в двудольном графе является максимальным тогда и только тогда, когда в нет дополняющей цепи. | ||||||
Доказательство: | ||||||
Пусть в двудольном графе с максимальным паросочетанием существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее все ребра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть не являлось максимальным. Противоречие.
В доказательстве используются несколько новых понятий:
| ||||||
Литература
- Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2