Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
Версия от 02:01, 22 января 2011; 192.168.0.2 (обсуждение) (→Теорема о максимальном паросочетании и дополняющих цепях)
Паросочетание в двудольном графе
Определение: |
Паросочетание в двудольном графе - произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины. Обозначается паросочетание как | .
Определение: |
Вершины двудольного графа, инцидентные ребрам | , называются покрытыми, а неинцидентные - свободными.
Определение: |
Чередующаяся цепь - путь в двудольном графе, для любых двух соседних ребер которого выполняется, что одно из них принадлежит паросочетанию | , а другое нет.
Определение: |
Дополняющая цепь - чередующаяся цепь, у которой оба конца свободны. |
Теорема о максимальном паросочетании и дополняющих цепях
Теорема: |
Паросочетание в двудольном графе является максимальным тогда и только тогда, когда в нет дополняющей цепи. |
Доказательство: |
Пусть в двудольном графе с максимальным паросочетанием существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее все ребра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть не являлось максимальным. Противоречие.Рассмотрим паросочетание в графе и предположим, что - не наибольшее. Докажем, что тогда имеется дополняющая цепь относительно . Пусть - другое паросочетание и . Рассмотрим подграф графа , образованный теми ребрами, которые входят в одно и только в одно из паросочетаний , . Иначе говоря, множеством ребер графа является симметрическая разность . В графе каждая вершина инцидентна не более чем двум ребрам (одному из и одному из ), т.е. имеет степень не более двух. В таком графе каждая компонента связности - путь или цикл. В каждом из этих путей и циклов чередуются ребра из и . Так как , имеется компонента, в которой ребер из содержится больше, чем ребер из . Это может быть только путь, у которого оба концевых ребра принадлежат . Заметим, что относительно этот путь является дополняющей цепью. |
Литература
- Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2