Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
Версия от 23:44, 17 ноября 2014; Dmitriy D. (обсуждение | вклад) (Товарищ Georgeee видимо торопился перед экзаменом и переписал конспект "Задача об устойчивом паросочетании" поверх существующего.)
Паросочетание в двудольном графе
Определение: |
Паросочетание | в двудольном графе — произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины.
Определение: |
Вершины двудольного графа, инцидентные ребрам паросочетания | , называются покрытыми, а неинцидентные — свободными.
Определение: |
Чередующаяся цепь — путь в двудольном графе, для любых двух соседних ребер которого верно, что одно из них принадлежит паросочетанию | , а другое нет.
Определение: |
Дополняющая цепь — чередующаяся цепь, у которой оба конца свободны. |
Теорема о максимальном паросочетании и дополняющих цепях
Теорема: | ||||||
Паросочетание в двудольном графе является максимальным тогда и только тогда, когда в нет дополняющей цепи. | ||||||
Доказательство: | ||||||
Пусть в двудольном графе с максимальным паросочетанием существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее все ребра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть не являлось максимальным. Противоречие.
В доказательстве используются несколько новых понятий:
| ||||||
Литература
- Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2