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

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

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

Теорема утверждает, что размер наибольшего паросочетания в графе равен:

,

где  — число связных компонент графа , имеющих нечётное число вершин.

Объяснение

[править | править код]

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

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

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

[править | править код]

Теорема Татта о паросочетаниях описывает графы с совершенными паросочетаниями как графы, для которых удаление любого подмножества вершин создаёт максимум нечётных компонент. (Подмножество , которое содержит по меньшей мере нечётных компонент, может быть всегда найдено в виде пустого множества). В этом случае по формуле Татта — Бержа размер паросочетания равен /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.