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

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

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

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

$\frac{1}{2}\underset{U\subseteq V}{\min }(|U|-\mathrm{odd}(G-U)+|V|)$,

где $\mathrm{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. То есть наибольшее паросочетание является совершенным и теорема Татта может быть получена как следствие формулы Татта — Бержа, а саму формулу можно рассматривать как обобщение теоремы Татта.

Литература

• Шаблон:Книга Репринт Dover Publications, 2001.
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга Шаблон:Wayback
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Шаблон:Статья
• Шаблон:Статья