Теорема Татта о паросочетаниях

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

Утверждение теоремы: граф $G=(V,E)$ имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества вершин $U\subseteq V$ подграф, индуцированный $V\setminus U$ , имеет не более $|U|$ связных компонент с нечётным числом вершин.

Установлена Уильямом Таттом.

Литература

Bondy, J. A. Graph theory with applications (неопр.). — New York: American Elsevier Pub. Co., 1976. — ISBN 0-444-19451-7.
Lovász, László. Matching theory (неопр.). — Amsterdam: North-Holland, 1986. — ISBN 0-444-87916-1.

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

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

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

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

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

Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.

Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.

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

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

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

Полный двудольный граф (биклика) — специальный вид двудольного графа, у которого любая вершина первой доли соединена со всеми вершинами второй доли вершин.

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

Куби́ческий граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.

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

<span class="mw-page-title-main">Формула Татта — Бержа</span>

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

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

FKT — алгоритм, подсчитывающий число совершенных паросочетаний в планарном графе за полиномиальное время. Та же задача является #P-полной для общих графов. Вычисление числа паросочетаний даже для планарных графов является также #P-полной задачей. Ключевой идеей является сведение задачи к вычислению пфаффиана кососимметричной матрицы, полученной из планарного вложения графа. Пфаффиан этой матрицы вычисляется тогда эффективно с помощью стандартных алгоритмов вычисления определителя.

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

Число паросочетания графа $\text{[math]}$ — размер наибольшего паросочетания в нём.

Число вершинного покрытия графа $\text{[math]}$ — размер наименьшего вершинного покрытия в нём.

Число рёберного покрытия графа $\text{[math]}$ — размер наименьшего рёберного покрытия в нём.

Число независимости графа $\text{[math]}$ — это размер наибольшего независимого множества вершин в нём.

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

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

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

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