Теорема Турана

редактировать

Не следует путать с методом Турана в аналитической теории чисел.

В теории графов, теорема Турана ограничивает число ребер, которые могут быть включены в неориентированный граф, который не имеет полного подграфа заданного размера. Это один из центральных результатов экстремальной теории графов, области, изучающей наибольший или наименьший граф с заданными свойствами, и частный случай проблемы запрещенного подграфа на максимальном количестве ребер в графе, не имеющем данного подграфа..

Пример графа - вершин, который не содержит клики - вершин, может быть сформирован путем разделения множества вершин на части равного или почти равного размера и соединения двух вершин ребром, если они принадлежат двум разным частям. Полученный граф - это граф Турана. Теорема утверждает Туран, что граф Турана имеет наибольшее число ребер среди всех К г +1 -свободных п графов -vertex. ${\ displaystyle n}$ $п$ ${\ Displaystyle (г + 1)}$ $(г + 1)$ ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle n}$ $п$ ${\ displaystyle r}$ $р$ ${\ Displaystyle Т (п, г)}$ $Т (п, г)$

Теорема Турана и графы Турана, дающие ее крайний случай, были впервые описаны и изучены венгерским математиком Палом Тураном в 1941 году. Частный случай теоремы для графов без треугольников известен как теорема Мантеля ; это было высказано в 1907 году голландским математиком Виллемом Мантелом.

СОДЕРЖАНИЕ

1 Заявление
2 Доказательства
3 Теорема Мантеля
4 См. Также
5 ссылки

Заявление

Теорема Турана утверждает, что каждый граф с вершинами, который не содержит в качестве подграфа, имеет количество ребер, не более ${\ displaystyle G}$ $грамм$ ${\ displaystyle n}$ $п$ ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle K_ {r + 1}}$

{\ displaystyle {\ frac {r-1} {r}} \ cdot {\ frac {n ^ {2}} {2}} = \ left (1 - {\ frac {1} {r}} \ right) \ cdot {\ frac {n ^ {2}} {2}}.}

\ frac {r-1} {r} \ cdot \ frac {n ^ 2} {2} = \ left (1- \ frac {1} {r} \ right) \ cdot \ frac {n ^ 2} {2 }.

Та же формула дает количество ребер в графе Турана, поэтому она эквивалентна формулировке теоремы Турана в форме, которая среди простых графов с -вершинами без -клик имеет максимальное количество ребер. ${\ Displaystyle Т (п, г)}$ $Т (п, г)$ ${\ displaystyle n}$ $п$ ${\ Displaystyle (г + 1)}$ $(г + 1)$ ${\ Displaystyle Т (п, г)}$ $Т (п, г)$

Доказательства

Айгнер и Зиглер (2018) перечисляют пять различных доказательств теоремы Турана.

Оригинальное доказательство Турана использует индукцию по количеству вершин. Для данного графа без -вершинников с более чем вершинами и максимальным числом ребер доказательство находит клику (которая должна существовать по максимальности), удаляет ее и применяет индукцию к оставшемуся -вершинному подграфу. Каждая вершина оставшегося подграфа может быть смежной не более чем с вершинами клики, и суммирование числа ребер, полученных таким образом, с индуктивным числом ребер в подграфе -вершине дает результат. ${\ displaystyle n}$ $п$ ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle r}$ $р$ ${\ displaystyle K_ {r}}$ ${\ displaystyle K_ {r}}$ ${\ displaystyle (nr)}$ ${\ displaystyle (nr)}$ ${\ displaystyle r-1}$ $г-1$ ${\ displaystyle (nr) (r-1)}$ ${\ displaystyle (nr) (r-1)}$ ${\ displaystyle (nr)}$ ${\ displaystyle (nr)}$

Другое доказательство Пола Эрдеша находит вершину максимальной степени из -свободного графа и использует ее для построения нового графа на том же наборе вершин, удаляя ребра между любой парой несоседей и добавляя ребра между всеми парами соседа. и не сосед. Новый граф остается -свободным и имеет по крайней мере столько же ребер. Рекурсивное повторение той же конструкции на подграфе соседей в конечном итоге дает граф в той же форме, что и граф Турана (набор независимых множеств, с ребрами между каждыми двумя вершинами из разных независимых множеств), и простое вычисление показывает, что количество рёбра этого графа максимизируются, когда размеры всех независимых множеств максимально близки к равным. ${\ displaystyle v}$ $v$ ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle v}$ $v$ ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle v}$ $v$ ${\ displaystyle p}$ $п$

Моцкин и Страус (1965) доказывают теорему Турана, используя вероятностный метод, ища дискретное распределение вероятностей на вершинах данного -свободного графа, которое максимизирует ожидаемое количество ребер в случайно выбранном индуцированном подграфе, причем каждая вершина включена в подграф. независимо с заданной вероятностью. Для распределения с вероятностью для вершины это ожидаемое число равно. Любое такое распределение может быть изменено путем многократного сдвига вероятности между парами несмежных вершин, чтобы ожидаемое значение не уменьшалось, а единственные вершины с ненулевой вероятностью принадлежали клике, из чего следует, что максимальное ожидаемое значение равно большинство. Следовательно, ожидаемое значение для равномерного распределения, которое в точности равно количеству ребер, разделенных на, также не больше, а само количество ребер не больше. ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle p_ {i}}$ $Пи}$ ${\ displaystyle v_ {i}}$ $v_ {i}$ ${\ displaystyle \ textstyle \ sum _ {(v_ {i}, v_ {j}) \ in E (G)} p_ {i} p_ {j}}$ ${\ displaystyle \ textstyle \ sum _ {(v_ {i}, v_ {j}) \ in E (G)} p_ {i} p_ {j}}$ ${\ displaystyle (r-1) / 2r}$ ${\ displaystyle (r-1) / 2r}$ ${\ Displaystyle 1 / п ^ {2}}$ $1 / п ^ {2}$ ${\ displaystyle (r-1) / 2r}$ ${\ displaystyle (r-1) / 2r}$ ${\ Displaystyle п ^ {2} (г-1) / 2r}$ ${\ Displaystyle п ^ {2} (г-1) / 2r}$

Доказательство Ноги Алон и Джоэла Спенсера из их книги «Вероятностный метод» рассматривает случайную перестановку вершин -свободного графа и наибольшую клику, образованную префиксом этой перестановки. Вычисляя вероятность включения любой данной вершины в зависимости от ее степени, можно показать, что ожидаемый размер этой клики равен, где - степень вершины. Должна существовать клика хотя бы такого размера, значит. Некоторые алгебраические манипуляции с этим неравенством с использованием неравенства Коши – Шварца и леммы о подтверждении связи доказывают результат. Подробнее см. Метод условных вероятностей § Теорема Турана. ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle K_ {r + 1}}$ ${\ Displaystyle \ textstyle \ сумма 1 / (п-d_ {я})}$ ${\ Displaystyle \ textstyle \ сумма 1 / (п-d_ {я})}$ ${\ displaystyle d_ {i}}$ $d_ {i}$ ${\ displaystyle v_ {i}}$ $v_ {i}$ ${\ Displaystyle \ textstyle г \ geq \ сумма 1 / (п-d_ {я})}$ ${\ Displaystyle \ textstyle г \ geq \ сумма 1 / (п-d_ {я})}$

Айгнер и Зиглер называют последнее из пяти доказательств «самым прекрасным из всех»; его происхождение неясно. Он основан на лемме о том, что для максимально- свободного графа несмежность является транзитивным отношением, так как если бы противное и были несмежными и были смежными, можно было бы построить -свободный граф с большим количеством ребер, удалив одно или две из этих трех вершин и заменяя их копиями одной из оставшихся вершин. Поскольку несмежность также является симметричной и рефлексивной (никакая вершина не смежна сама с собой), она образует отношение эквивалентности, классы эквивалентности которого придают любому максимальному графу ту же форму, что и граф Турана. Как и во втором доказательстве, простой расчет показывает, что количество ребер максимизируется, когда размеры всех независимых множеств максимально близки к равным. ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle K_ {r + 1}}$ ${\ Displaystyle (и, v)}$ $(u, v)$ ${\ displaystyle (v, w)}$ $(v, w)$ ${\ Displaystyle (и, ш)}$ $(u, w)$ ${\ displaystyle K_ {r + 1}}$ ${\ displaystyle K_ {r + 1}}$

Теорема Мантеля

Частным случаем теоремы Турана для является теорема Мантеля: максимальное количество ребер в графе без треугольников-вершин равно. Другими словами, нужно удалить почти половину ребер, чтобы получить граф без треугольников. ${\ displaystyle r = 2}$ $г = 2$ ${\ displaystyle n}$ $п$ ${\ displaystyle \ lfloor n ^ {2} / 4 \ rfloor.}$ $\ lfloor n ^ 2/4 \ rfloor.$ ${\ displaystyle K_ {n}}$ $K_ {n}$

Усиленная форма теоремы Мантеля утверждает, что любой гамильтонов граф с как минимум ребрами должен быть либо полным двудольным графом, либо панциклическим : он не только содержит треугольник, но также должен содержать циклы всех других возможных длин до числа вершин графа. ${\ Displaystyle п ^ {2} / 4}$ $п ^ 2/4$ ${\ displaystyle K_ {n / 2, n / 2}}$ ${\ displaystyle K_ {n / 2, n / 2}}$

Другое усиление теоремы Мантеля утверждает, что ребра любого -вершинного графа могут быть покрыты не более чем кликами, которые являются ребрами или треугольниками. Как следствие, число пересечений графа (минимальное количество клик, необходимых для покрытия всех его ребер) не превосходит. ${\ displaystyle n}$ $п$ ${\ Displaystyle \ lfloor п ^ {2} / 4 \ rfloor}$ $\ lfloor n ^ 2/4 \ rfloor$ ${\ Displaystyle \ lfloor п ^ {2} / 4 \ rfloor}$ $\ lfloor n ^ 2/4 \ rfloor$

Смотрите также

Теорема Эрдеша – Стоуна, обобщение теоремы Турана от запрещенных клик до запрещенных графов Турана

Рекомендации