Теорема Бараньяи

Разбиение полного графа с 8 вершинами на 7 цветов (совершенные паросочетания), случай r = 2 теоремы Бараньяи

Теорема Бараньяи — теорема о разбиениях полных гиперграфов. Доказана Жолтом Бараньяи и названа его именем.

Формулировка

Если $2\leqslant r<k$ являются натуральными числами и r делит k, то полный гиперграф $K_{r}^{k}$ можно разложить на 1-факторы.

Замечания

$K_{r}^{k}$ — это гиперграф с k вершинами, в котором каждое подмножество из r вершин образует гиперребро.
1-фактор этого гиперграфа — это набор гиперрёбер, которые содержат каждую вершину в рёбрах ровно раз, что эквивалентно разбиению вершин на подмножества размера r.

Таким образом, теорема утверждает, что k вершин гиперграфа могут быть разбиты на подмножества r вершин ${\binom {k}{r}}{\frac {r}{k}}={\binom {k-1}{r-1}}$ различными способами таким образом, что каждое r-элементное подмножество появляется ровно раз в разбиении.

Случай $r=2$

В специальном случае $r=2$ мы имеем полный граф $K_{n}$ с $n$ вершинами и хотим раскрасить рёбра в ${\binom {n}{2}}{\frac {2}{n}}=n-1$ цветов так, что рёбра каждого цвета образуют совершенное паросочетание. Теорема Бараньяи утверждает, что мы можем это сделать, если $n$ чётно.

История

Случай r = 2 можно переформулировать как утверждение, что любой полный граф с чётным числом вершин имеет рёберную раскраску, число цветов которой равно его степени, или, эквивалентно, что рёбра могут быть разбиты на совершенные паросочетания. Это можно использовать для создания круговых турниров и решение было известно в 19-м веке. Случай k = 2r также прост.

Случай r = 3 рассмотрел в 1963 году Р. Пелтесон. Общий случай доказал в 1975 году Жолт Бараньяи.

Литература

Zsolt Baranyai. On the factorization of the complete uniform hypergraph // Infinite and Finite Sets, Proc. Coll. Keszthely, 1973 / András Hajnal, Richard Rado, Vera T. Sós. — North-Holland, 1975. — Т. 10. — С. 91–107. — (Colloquia Math. Soc. János Bolyai)..
Jack van Lint, R. M. Wilson. A Course in Combinatorics. — 2nd. — Cambridge University Press, 2001.
Peltesohn R. Das Turnierproblem für Spiele zu je dreien. — Berlin, 1936. — (Inaugural dissertation).

Похожие исследовательские статьи

Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:

как и геометрия, обладает наглядностью;
как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
не имеет громоздкого математического аппарата ;
имеет выраженный прикладной характер.

Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.

<span class="mw-page-title-main">Теорема Кёнига (комбинаторика)</span>

В теории графов теорема Кёнига , доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.

Теорема Рамсея — теорема комбинаторики о разбиениях множеств, сформулированная и доказанная английским математиком Фрэнком Рамсеем в 1930 году. Встречается в литературе в разных формулировках. Эта теорема положила начало теории Рамсея.

Система Штейнера — вариант блок-схем, точнее, t-схемы с λ = 1 и t ≥ 2.

В теории графов паросочетание, или независимое множество рёбер в графе, — это набор попарно несмежных рёбер.

Теорема Дилуорса — комбинаторное утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств: конечное частично упорядоченное множество $\text{[math]}$ может быть разбито на $\text{[math]}$ попарно непересекающихся цепей, где $\text{[math]}$ — количество элементов наибольшей антицепи множества $\text{[math]}$ .

В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.

В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин u_i и v_i и рёбрами между u_i и v_j, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера H_n,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом.

Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в $\text{[math]}$ различных цветов для заданного значения $\text{[math]}$ или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.

<span class="mw-page-title-main">Граф гиперкуба</span> регулярный граф с 2^n вершинами, 2^(n−1)n рёбрами и n рёбрами, сходящимися в одной вершине

В теории графов графом гиперкуба Q_n называется регулярный граф с 2ⁿ вершинами, 2ⁿ⁻¹n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q₃ — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества отличаются только одним элементом.

Граф Турана T(n,r) — это граф, образованный разложением n вершин на r подмножеств, с как можно близким размером, и вершины в этом графе соединены ребром, если они принадлежат разным подмножествам. Граф будет иметь $\text{[math]}$ подмножеств размером $\text{[math]}$ и $\text{[math]}$ подмножеств размером $\text{[math]}$ . Таким образом, это полный r-дольный граф

\text{[math]}

Кнезеровский граф $\text{[math]}$ — это неориентированный граф, описывающий отношение непересекаемости $\text{[math]}$ -элементных подмножеств $\text{[math]}$ -элементного множества друг с другом.

Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.

В комбинаторике разбиений ацтекским бриллиантом порядка $\text{[math]}$ называется фигура, состоящая из клеток, наведённых плоской целочисленной решёткой, центры которых удовлетворяют неравенству $\text{[math]}$ .

Двенадцатеричный путь или двенадцать сценариев — это систематическая классификация 12 связанных перечислительных задач, касающихся двух конечных множеств, которые включают классические задачи подсчёта перестановок, сочетаний, мультимножеств и разбиений либо множества, либо числа. Идею классификации приписывают Джиану-Карло Роту, а название двенадцатеричный путь предложил Джоэл Спенсер по аналогии с термином восьмеричный путь из физики, который в свою очередь произошел от понятия восьмеричный путь в буддизме. Название намекает, что используя те же подходы в 12 случаях, но с небольшими изменениями в условиях, мы получаем 12 разных результатов.

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

Кососимметрический граф — ориентированный граф, изоморфный своему собственному транспонированному графу. Этот граф образуется путём обращения всех дуг с изоморфизмом и является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям двунаправленных графов.

<span class="mw-page-title-main">Зоногон</span>

Зоногон — центрально-симметричный выпуклый многоугольник.

<span class="mw-page-title-main">Теорема Петерсена</span> теорема теории графов

Теорема Петерсена — одна из самых ранних теорем теории графов, названная в честь Юлиуса Петерсена. Определение теоремы может быть сформулировано следующим образом:

Теорема Петерсена. Любой кубический двусвязный граф содержит в себе совершенное паросочетание.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.