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

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

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

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

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

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

Объяснение

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

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

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

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

Литература

• 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.