WikiSort.ru - Не сортированное

Формула Тата — Бержа определяет размер наибольшего паросочетания в графе. Формула является обобщением Теорема Тата о паросочетаниях и названа именами У. Т. Тата (доказавшего теорему своего имени) и К. Бержа^[en] (доказавшего обобщение).

Утверждение теоремы

Теорема утверждает, что размер наибольшего паросочетания в графе ${\displaystyle G=(V,E)}$ равен

${\displaystyle {\frac {1}{2}}\min _{U\subseteq V}\left(|U|-\operatorname {odd} (G-U)+|V|\right),}$

где ${\displaystyle \operatorname {odd} (H)}$ даёт число связных компонент графа ${\displaystyle H}$ , имеющих нечётное число вершин.

Объяснение

Интуитивно ясно, что для любого подмножества вершин U единственным способом полностью покрыть компоненту G − U с нечётным числом вершин — это выбрать в паросочетание ребро, соединяющее одну из вершин G − U с U. Если в компоненте с нечётным числом вершин такого ребра в паросочетании нет, часть паросочетания покроет вершины компоненты, но, поскольку число вершин нечётно, по меньшей мере одна вершина останется непокрытой. Таким образом, если некоторое подмножество вершин U имеет малый размер, но при его удалении создаётся большое число нечётных компонент, то останется много непокрытых паросочетанием вершин, из чего следует, что и паросочетание будет малым. Это рассуждение можно сделать строгим, если принять во внимание, что размер наибольшего паросочетания не превосходит значения, которое даёт формула Тата – Бержа.

Формула Тата и Бержа показывает, что данное ограничение является единственным препятствием для получения большего паросочетания — размер оптимального паросочетания определяется подмножеством U, имеющим наибольшую разность между числом нечётных компонент вне U и вершинами внутри U. То есть всегда существует точное подмножество U, удаление которого создаёт правильное число нечётных компонент, удовлетворяющих формуле. Один из способов получить такое множество U — выбрать любое наибольшее паросочетание M и включить в X вершины, которые либо не покрыты паросочетанием M, либо могут быть достигнуты из непокрытой вершины чередующейся цепью^[1], которая завершается ребром из паросочетания. Теперь определим U как множество вершин, которые соединяются паросочетанием M с вершинами из X. Никакие две вершины из X не могут быть смежны, в противном случае можно соединить две непокрытые вершины альтернирующим путём, что противоречит максимальности M^[2]. Любой сосед вершины x из X должен принадлежать U, в противном случае мы можем расширить альтернирующий путь к x на пару рёбер к соседям, что приводит к тому, что соседи становятся частью U. Таким образом, в G − U, любая вершина X образует компоненту из одной вершины, то есть имеет нечётное число вершин. Не может быть других нечётных компонент, поскольку все другие вершины остаются покрытыми паросочетанием после удаления U.

Связь с теоремой Тата

Теорема Тата о паросочетаниях описывает графы с совершенными паросочетаниями как графы, для которых удаление любого подмножества U вершин создаёт максимум |U | нечётных компонент. (Подмножество U, которое содержит по меньшей мере |U| нечётных компонент, может быть всегда найдено в виде пустого множества). В этом случае по формуле Тата — Бержа размер паросочетания равен |V|/2. То есть наибольшее паросочетание является совершенным и теорема Тата может быть получена как следствие формулы Тата — Бержа, а саму формулу можно рассматривать как обобщение теоремы Тата.

См. также

• Жёсткость графа, задача создания многих компонент путём удаления малого числа вершин без учёта чётности числа вершин в компонентах
• Теорема о свадьбах
• Теорема Тата^[en]

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.