Формула Татта — Бержа

В этом графе удаление одной вершины в центре даёт три нечётные компоненты, три подграфа по пять вершин. Таким образом, по формуле Татта — Бержа граф имеет не более (1−3+16)/2 = 7 рёбер в любом паросочетании.

Формула Татта — Бержа — теоретико-графовая формула, определяющая размер наибольшего паросочетания в графе. Является обобщением теоремы Татта о паросочетаниях; установлена и доказана Клодом Бержем^[англ.].

Теорема утверждает, что размер наибольшего паросочетания в графе ${\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}$, имеющих нечётное число вершин.

Объяснение

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

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

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

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

Примечания

1. Чередующимся путём называется путь, в котором чередуются рёбра из паросочетания и не входят в паросочетание (Берж 1962, С. 186 Теория чередующихся цепей)
2. Теорема: Паросочетание графа является наибольшим тогда и только тогда, когда не существует чередующейся цепи, соединяющей две различные непокрытые паросочетанием вершины. (Берж 1962, С. 195)

Литература

• C. Berge^[англ.]. The Theory of Graphs. — Methuen, 1962. Репринт Dover Publications, 2001.
• К. Берж. Теория графов и её применение. — Москва: Издательство иностранной литературы, 1962.
• J. A. Bondy, U. S. R. Murty. Graph theory: an advanced course. — Springer-Verlag, 2007. — С. 428. — (Graduate Texts in Mathematics). — ISBN 1-84628-969-6.
• J. A. Bondy, U. S. R. Murty. Exercise 5.3.4, p. 80 // Graph Theory with Applications. — New York: North Holland, 1976. — ISBN 0-444-19451-7. Архивная копия от 13 апреля 2010 на Wayback Machine
• Richard A. Brualdi. Combinatorial matrix classes. — Cambridge: Cambridge University Press, 2006. — Т. 108. — С. 360. — (Encyclopedia of Mathematics and Its Applications). — ISBN 0-521-86565-4.
• László Lovász, M. D. Plummer. Matching theory. — Amsterdam: North-Holland, 1986. — С. 90—91. — ISBN 0-444-87916-1.
• Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency. — Springer-Verlag, 2003. — С. 413. — ISBN 3-540-44389-4.

Ссылки

• C. Berge^[англ.]. Sur le couplage maximum d'un graphe // Comptes rendus hebdomadaires des séances de l'Académie des sciences. — 1958. — Т. 247. — С. 258—259.
• W. T. Tutte. The factorization of linear graphs // The Journal of the London Mathematical Society, Ser. 1. — 1947. — Т. 22. — С. 107—111. — doi:10.1112/jlms/s1-22.2.107.