Лемма Бержа утверждает, что паросочетание M в графе G является наибольшим (содержит наибольшее возможное число рёбер) тогда и только тогда, когда не существует расширяющего пути (пути, который начинается и завершается на свободных, то есть не принадлежащих паросочетаниям, вершинах и поочерёдно проходит по рёбрам, принадлежащих и не принадлежащих паросочетанию) в M.
Лемму доказал французский математик Клауди Берж в 1957 году (хотя её уже обсуждали Петерсен в 1891 и Кёниг в 1931).
Доказательство
Для доказательства леммы Берж нам сначала нужна другая лемма. Возьмём граф G и пусть M и M′ будут двумя паросочетаниями в G. Пусть G′ будет результатом взятия симметрической разности M и M′. То есть . G′ будет состоять из компонент, которые принадлежат следующим группам:
- Изолированная вершина.
- Чётный цикл, рёбра которого поочерёдно принадлежат M и M′.
- Путь с различными конечными точками, рёбра которого поочерёдно принадлежат M и M′.
Лемму можно доказать, если заметить, что любая вершина из G′ может быть инцидентна максимум двум рёбрам — одно из M и одно из M′. Графы, в которых любая вершина имеет степень, не превосходящую 2, должны состоять из изолированных вершин, циклов и путей. Более того, каждый путь и цикл в G′ должен поочерёдно содержаться в M и M′. Чтобы цикл мог так себя вести, он должен иметь равное число рёбер из M и M′, а потому чётную длину.
Теперь мы можем доказать лемму Бержа от противного — граф G имеет паросочетание, большее чем у M тогда и только тогда, когда G имеет расширяющий путь. Ясно, что расширяющий путь P графа G может быть использован для получения паросочетания M′, которое больше паросочетания M — просто возьмём в качестве M′ симметрическую разность пути P и M (M′ состоит в точности из тех рёбер графа G, которые появляются ровно раз в пути P, либо в паросочетании M). Отсюда следует доказательство в обратную сторону.
Для доказательства в прямом направлении положим, что M′ является паросочетанием графа G, большим паросочетания M. Рассмотрим в качестве D симметрическую разность M и M′. Заметим, что D состоит из путей и чётных циклов (как было замечено в более ранней лемме). Поскольку M′ больше M, D содержит компоненту, которая имеет больше рёбер изM′, чем из M. Такая компонента является путём в G, который начинается и кончается ребром из M′, так что он является расширяющим.
Следствия
Следствие 1
Пусть M является наибольшим паросочетанием и рассмотрим чередующуюся цепь, такую что рёбра в пути чередуются между принадлежащими и не принадлежащими M. Если чередующаяся цепь является циклом или путём чётной длины, то может быть найдено новое наибольшее паросочетание M′ путём обмена рёбер между M и не из M. Например, если чередующаяся цепь — это , где , а . Обмен этих рёбер сделает все ni частью нового паросочетания и все mi в паросочетание не войдут.
Следствие 2
Ребро считается «свободным», если оно принадлежит наибольшему паросочетанию, но не всем наибольшим паросочетаниям. Ребро e является свободным тогда и только тогда, когда в произвольном наибольшем паросочетнии M ребро e принадлежит чётному чередующемуся пути, который начинается в непокрытой вершине или принадлежит чередующемуся циклу. По первому следствию, если ребро e является частью такой чередующейся цепи, то должно существовать новое наибольшее паросочетание M′ и e будет принадлежать либо M, либо M′, а потому является свободным. В обратную сторону, если ребро e свободно, то e находится в некотором наибольшем паросочетании M, но не в M′. Поскольку ребро e не принадлежит одновременно M и M′, оно должно присутствовать в симметрической разности M и M′. Симметрическая разность M и M′ даёт граф, состоящий из изолированных вершин, чётных чередующихся циклов и чередующихся путей чётной длины. Предположим, что это не так и e принадлежит некоторому пути нечётной длины. Но тогда одно из паросочетаний M или M′ должно иметь меньше рёбер в этой компоненте, что означает, что эта компонента в целом является расширяющим путём для этого паросочетания. По исходной лемме тогда это паросочетание (M или M′) не может быть наибольшим, что противоречит предположению о том, что оба паросочетания M и M′ являются наибольшими. Таким образом, поскольку e не может принадлежать какой либо компоненте-пути нечётной длины, оно должно быть либо лежать в цикле чётной длины, либо на чередующемся пути чётной длины.
Примечания
Литература
- Claude Berge. Two theorems in graph theory // Proceedings of the National Academy of Sciences of the United States of America. — 1957. — September 15 (т. 43, вып. 9). — С. 842–844. — DOI:10.1073/pnas.43.9.842.
- Douglas B. West. Introduction to Graph Theory. — 2nd. — Pearson Education, Inc., 2001. — С. 109–110. — ISBN 81-7808-830-4.
- Claude Berge. Graphs and Hypergraphs. — North-Holland Publishing Company, 1973. — С. 122–125. — ISBN 0-444-10399-6.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .