Лемма Бергеса - Википедия - Berges lemma

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

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

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

Для доказательства леммы Берже нам сначала понадобится еще один лемма. Взять график грамм и разреши M и M ′ быть двумя совпадения в грамм. Позволять ГРАММ' быть результатом график от принятия симметричная разница из M и M ′; т.е. (M - M ′) ∪ (M ′ - M). ГРАММ' будет состоять из связанных компонентов, которые являются одним из следующих:

  1. Изолированный вершина.
  2. Даже цикл чьи края чередуются между M и M ′.
  3. А дорожка чьи края чередуются между M и M ′, с разными конечными точками.

В лемма можно доказать, заметив, что каждый вершина в ГРАММ' может входить не более чем в 2 ребра: одно из M и один из M ′. Графы, в которых каждая вершина имеет степень меньше или равной 2, должны состоять либо из изолированных вершины, циклы, и пути. Кроме того, каждый путь и цикл в ГРАММ' должен чередоваться M и M ′. Для того, чтобы цикл для этого он должен иметь равное количество ребер из M и M ′и, следовательно, иметь одинаковую длину.

Давайте теперь докажем контрапозитивный леммы Берже: грамм имеет соответствие больше, чем M если и только если грамм имеет увеличивающийся путь. Очевидно, что путь расширения п из грамм может использоваться для создания соответствие M ′ это больше, чем M - просто возьми M ′ быть симметричная разница из п и M (M ′ содержит именно те ребра грамм которые появляются ровно в одном из п и M). Отсюда следует обратное направление.

Для прямого направления пусть M ′ быть соответствие в грамм больше, чем M. Учитывать D, симметричная разность M и M ′. Заметьте, что D состоит из дорожек и даже циклы (как отмечалось ранее лемма ). С M ′ больше чем M, D содержит компонент, у которого больше ребер из M ′ чем M. Такой компонент - это путь в грамм который начинается и заканчивается ребром от M ′, так что это дополнительный путь.

Следствия

Следствие 1.

Позволять M быть максимальным соответствием и рассмотрим чередующуюся цепочку, так что ребра на пути чередуются между присутствием и отсутствием M. Если переменная цепь - это цикл или дорожка четной длины, то новое максимальное соответствие M ′ можно найти, поменяв местами края, найденные в M а не в M. Например, если чередующаяся цепочка (м1, п1, м2, п2, ...), куда мя ∈ M и пя ∉ M, поменяв их местами, все пя часть нового сопоставления и сделать все мя не входит в соответствие.

Следствие 2.

Ребро считается «свободным», если оно принадлежит максимальному совпадению, но не принадлежит всем максимальным совпадениям. Край е свободен тогда и только тогда, когда в произвольном максимальном совпадении M, край е принадлежит чётному чередующемуся пути, начинающемуся в несовпадающей вершине, или чередующемуся цикл. По первому следствию, если край е является частью такой чередующейся цепочки, то новое максимальное соответствие, M ′, должен существовать и е будет существовать либо в M или же M ′, а значит, будьте свободны. И наоборот, если край е бесплатно, тогда е находится в некотором максимальном соответствии M но не в M ′. С е не является частью обоих M и M ′, он должен все еще существовать после принятия симметричная разница из M и M ′. В симметричная разница из M и M ′ приводит к график состоящий из изолированных вершин, чередующихся циклов и чередующихся путей. Предположим противное, что е принадлежит некоторому компоненту пути нечетной длины. Но потом один из M и M ′ должен иметь на одно ребро меньше, чем другое в этом компоненте, что означает, что компонент в целом является дополнительным путем по отношению к этому сопоставлению. Следовательно, согласно исходной лемме, это соответствие (независимо от того, M или же M ′) не может быть максимальным согласованием, что противоречит предположению, что оба M и M ′ максимальные. Итак, поскольку е не может принадлежать какому-либо компоненту пути нечетной длины, он должен быть либо в чередующемся цикле, либо в чередующемся пути четной длины.

Рекомендации

  • Берже, Клод (15 сентября 1957 г.), «Две теоремы теории графов» (PDF), Труды Национальной академии наук Соединенных Штатов Америки, 43 (9): 842–844, Дои:10.1073 / пнас.43.9.842, ЧВК  534337, PMID  16590096.
  • Уэст, Дуглас Б. (2001), Введение в теорию графов (2-е изд.), Pearson Education, Inc., стр. 109–110, ISBN  81-7808-830-4.
  • Берже, Клод (1973), Графы и гиперграфы, North-Holland Publishing Company, стр. 122–125, ISBN  0-444-10399-6.