Теорема Бержа

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

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

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

Для доказательства теоремы Бержа нам сначала понадобится лемма . Возьмем граф G и пусть M и M ′ — два паросочетания в G . Пусть G ′ будет результирующим графом , полученным из симметричной разности M и M ′ ; то есть ( M - M ′ ) ∪ ( 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 , которые появляются ровно в одном П ) и М . Следовательно, следует обратное направление.

Для прямого направления пусть M ′ будет паросочетанием в G, большим, чем M . Рассмотрим D , симметричную разность M и M ' . Обратите внимание, что D состоит из путей и даже циклов (как было замечено в предыдущей лемме). Поскольку M ′ больше M , D содержит компонент, который имеет больше ребер из M ′, чем из M . Такой компонент — это путь в G , который начинается и заканчивается ребром из M ′ , поэтому это дополняющий путь.

Следствия

Следствие 1

Пусть M в которой ребра пути попеременно то находятся, то не находятся в M. — максимальное паросочетание, и рассмотрим цепочку переменных , Если чередующаяся цепочка представляет собой цикл или путь четной длины, начинающийся в несовпадающей вершине, то новое максимальное паросочетание M ′ можно найти, меняя местами ребра, найденные в M , а не в M . Например, если чередующаяся цепочка равна ( m ₁ , n ₁ , m ₂ , n ₂ , ...), где m _i ∈ M и n _i ∉ M , их замена сделает все n _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 не может принадлежать какому-либо компоненту пути нечетной длины, он должен находиться либо в чередующемся цикле, либо в чередующемся пути четной длины.

Ссылки

Берже, Клод (15 сентября 1957 г.), «Две теоремы теории графов» (PDF) , Proceedings of the National Academy of Sciences of the United States of America , 43 (9): 842–844, Bibcode : 1957PNAS... 43..842B , дои : 10.1073/pnas.43.9.842 , PMC 534337 , PMID 16590096 .
Уэст, Дуглас Б. (2001), Введение в теорию графов (2-е изд.), Pearson Education, Inc., стр. 109–110, ISBN 81-7808-830-4 .
Берге, Клод (1973), Графики и гиперграфы , Издательство Северной Голландии, стр. 122–125, ISBN 0-444-10399-6 .