В теории графов , теорема Турана ограничивает число ребер , которые могут быть включены в неориентированный граф , который не имеет полного подграфа заданного размера. Это один из центральных результатов экстремальной теории графов , области, изучающей наибольший или наименьший граф с заданными свойствами, и частный случай проблемы запрещенного подграфа на максимальном количестве ребер в графе, не имеющем данного подграфа. .
Пример - граф вершин , не содержащий-вертекс клика может быть сформирован путем разбиения множества вершины в части равного или почти равного размера и соединяющие две вершины ребром, если они принадлежат двум разным частям. Полученный граф является графом Турана . Теорема утверждает Туран , что граф Турана имеет наибольшее число ребер среди всех К г +1 -свободных п графов -vertex.
Теорему Турана, и графики ТУРАН давая ее крайний случай, впервые были описаны и изучены венгерский математик Пал Туран в 1941 году [1] частный случай теоремы для треугольника свободных графов известен как теорема Mantel в ; это было высказано в 1907 году голландским математиком Виллемом Мантелом. [2]
Заявление
Теорема Турана утверждает, что каждый граф с участием вершины, не содержащие поскольку у подграфа количество ребер не более
Эта же формула дает количество ребер в графе Турана , так что это эквивалентно формулировке теоремы Турана в форме, что среди -вершинные простые графы без -клики, имеет максимальное количество ребер. [3]
Доказательства
Айгнер и Зиглер (2018) перечисляют пять различных доказательств теоремы Турана. [3]
Оригинальное доказательство Турана использует индукцию по количеству вершин. Учитывая-вертекс -свободный граф с более чем вершин и максимального числа ребер, доказательство находит клику (который должен существовать по максимальности), удаляет его и применяет индукцию к оставшимся -вершинный подграф. Каждая вершина оставшегося подграфа может быть смежной не более чем с клика по вершинам и суммирование числа полученных таким образом ребер с индуктивным числом ребер в -вершинный подграф дает результат. [1] [3]
Другое доказательство Пола Эрдеша находит вершину максимальной степени из -свободный граф и использует его для построения нового графа на том же наборе вершин, удаляя ребра между любой парой несоседей и добавление ребер между всеми парами соседа и не-соседа. Новый график остается-свободен и имеет как минимум столько же ребер. Рекурсивно повторяя ту же конструкцию на подграфе соседей в конечном итоге производит граф в той же форме, что и граф Турана (набор независимых множеств, с ребрами между каждыми двумя вершинами из разных независимых множеств), и простой расчет показывает, что количество ребер этого графа максимизируется, когда размеры всех независимых множеств максимально близки к равным. [3] [4]
Моцкин и Страус (1965) доказывают теорему Турана, используя вероятностный метод , ища дискретное распределение вероятностей в вершинах заданного-свободный граф, который максимизирует ожидаемое количество ребер в случайно выбранном индуцированном подграфе , причем каждая вершина включается в подграф независимо с заданной вероятностью. Для распределения с вероятностью для вершины , это ожидаемое число . Любое такое распределение может быть изменено путем многократного сдвига вероятности между парами несмежных вершин так, чтобы ожидаемое значение не уменьшалось, а единственные вершины с ненулевой вероятностью принадлежали клике, из чего следует, что максимальное ожидаемое значение равно наиболее. Следовательно, ожидаемое значение для равномерного распределения, которое в точности равно количеству ребер, деленному на, также не более , а само количество ребер не более . [3] [5]
Доказательство Ноги Алон и Джоэла Спенсера из их книги Вероятностный метод рассматривает случайную перестановку вершин-свободный граф, и наибольшая клика, образованная префиксом этой перестановки. Вычислив вероятность того, что любая данная вершина будет включена, как функцию ее степени, можно показать, что ожидаемый размер этой клики равен, где степень вершины . Должна существовать клика не менее этого размера, поэтому. Некоторые алгебраические манипуляции с этим неравенством с использованием неравенства Коши – Шварца и леммы о подтверждении связи доказывают результат. [3] Подробнее см. Метод условных вероятностей § Теорема Турана .
Айгнер и Зиглер называют последнее из пяти доказательств «самым прекрасным из всех»; его происхождение неясно. Он основан на лемме о том, что для максимального-свободный граф, несмежность - транзитивное отношение , иначе а также были несмежными и были смежными, можно было построить -свободный граф с большим количеством ребер, удалив одну или две из этих трех вершин и заменив их копиями одной из оставшихся вершин. Поскольку несмежность также является симметричной и рефлексивной (никакая вершина не смежна сама с собой), она образует отношение эквивалентности, классы эквивалентности которого придают любому максимальному графу ту же форму, что и граф Турана. Как и во втором доказательстве, простой расчет показывает, что количество ребер максимизируется, когда размеры всех независимых множеств максимально близки к равным. [3]
Теорема Мантеля
Частный случай теоремы Турана для это теорема Мантеля: максимальное количество ребер в -vertex граф без треугольников является[2] Другими словами, нужно удалить почти половину ребер в чтобы получить граф без треугольников.
Усиленная форма теоремы Мантеля утверждает, что любой гамильтонов граф с как минимум ребра должны быть либо полным двудольным графом или он должен быть панциклическим : он не только содержит треугольник, но также должен содержать циклы всех других возможных длин до количества вершин в графе. [6]
Еще одно усиление теоремы Мантеля утверждает, что ребра каждого -вершинный граф может быть покрыт не более чем клики, которые являются ребрами или треугольниками. Как следствие, число пересечений графа (минимальное количество клик, необходимых для покрытия всех его ребер) не превосходит. [7]
Смотрите также
- Теорема Эрдеша – Стоуна , обобщение теоремы Турана от запрещенных клик до запрещенных графов Турана
Рекомендации
- ^ a b Turán, Paul (1941), "Об одной экстремальной задаче в теории графов", Matematikai és Fizikai Lapok (на венгерском языке), 48 : 436–452
- ^ а б Мантел, В. (1907), «Проблема 28 (Решение Х. Гувентака, В. Мантела, Дж. Тейшейра де Маттес, Ф. Шу и В. А. Витхофф)», Вискундиге Опгавен , 10 : 60–61
- ^ Б с д е е г Айгнер, Мартин ; Циглера, Гюнтер М. (2018), "Глава 41: теорема графа Турана", Доказательства из книги (6 - й изд.), Springer-Verlag, стр. 285-289, DOI : 10.1007 / 978-3-662-57265- 8_41 , ISBN 978-3-662-57265-8
- ^ Эрдеш, Пал (1970), «Turán Pál gráf tételéről» [О теореме Турана о графах] (PDF) , Matematikai Lapok (на венгерском языке), 21 : 249–251, MR 0307975
- ^ Моцкин, Т.С .; Страус, Е. (1965), "Maxima для графов и новое доказательство теоремы Турана", Canadian Journal математики , 17 : 533-540, DOI : 10,4153 / CJM-1965-053-6 , MR 0175813
- ^ Бонди, Дж. А. (1971), «Панциклические графы I», Журнал комбинаторной теории , серия B , 11 (1): 80–84, DOI : 10.1016 / 0095-8956 (71) 90016-5
- ^ Эрдеш, Пол ; Гудман, AW ; Posa, Луи (1966), "Представление графа множества пересечений" (PDF) , Канадский журнал математика , 18 (1): 106-112, DOI : 10,4153 / CJM-1966-014-3 , МР 0186575