Лемма Бержа

Лемма Бержа утверждает, что паросочетание M в графе G является наибольшим (содержит наибольшее возможное число рёбер) тогда и только тогда, когда не существует дополняющего пути (пути, который начинается и завершается на свободных, то есть не принадлежащих паросочетаниям, вершинах и поочерёдно проходит по рёбрам, принадлежащим и не принадлежащим паросочетанию) в M.

Лемму доказал французский математик Клод Берж в 1957 году (хотя её уже обсуждали Петерсен в 1891 и Кёниг в 1931).

Доказательство

Для доказательства леммы Бержа нам сначала нужна другая лемма. Возьмём граф G, и пусть M и M′ будут двумя паросочетаниями в G. Пусть G′ будет результатом взятия симметрической разности M и M′. То есть $(M\setminus M')\cup (M'\setminus M)$. G′ будет состоять из компонент, которые принадлежат следующим группам:

1. Изолированная вершина.
2. Чётный цикл, рёбра которого поочерёдно принадлежат M и M′.
3. Путь с различными конечными точками, рёбра которого поочерёдно принадлежат 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. Например, если чередующаяся цепь — это $(m_{1},n_{1},m_{2},n_{2},\dots )$, где $m_{i}\in M$, а $n_{i}\notin M$. Обмен этих рёбер сделает все n_i частью нового паросочетания, и все m_i в паросочетание не войдут.

Следствие 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 не может принадлежать какой-либо компоненте-пути нечётной длины, оно должно быть либо лежащим в цикле чётной длины, либо на чередующемся пути чётной длины.