Давайте я немножко с другого бока ещё посмотрю на эту теорему,
ещё разок её по-другому прокомментирую.
Для того чтобы может быть кто-то, кто уже что-то слышал о подобного рода
утверждениях, узнал, углядел в этой теореме некий факт, с которым он,
возможно, был знаком чуть-чуть по-другому, чуть-чуть с другой стороны.
Давайте например, например,
предположим, что
в графе G нет треугольников,
нет треугольников.
Ну что такое треугольник, понятно.
Это полный граф на 3 вершинах, то есть таких троек вершин,
которые попарно соединены рёбрами.
Вот давайте возьмём любой граф, у которого нет треугольников.
Вот что про него интуитивно хочется сказать?
Наверное, по аналогии с тем, что мы только что получили, хочется сказать,
что наоборот, у этого графа не может быть слишком много рёбер.
Потому что едва у него будет много рёбер, треугольники возникнут.
То есть это как бы двойственная постановка вопроса.
Если до сих пор мы говорили о том, что граф, в котором маленькие
независимые множества, должен иметь много рёбер, то теперь мы наоборот,
пытаемся, пытаемся что-нибудь сказать про граф, в котором нет треугольников,
и предполагаем, что скорее всего, в нём как раз много рёбер быть не может.
Иначе много-много рёбер завяжут все-таки треугольник где-нибудь.
Ну хорошо, давайте предположим, что в графе G нет треугольников.
Рассмотрим тот самый граф G с чертой, о котором я говорил в начале лекции.
То есть граф, повторяю,
который получается из нашего исходного графа G путём такой нехитрой операции.
Мы берём все рёбра исходного графа, их стираем, все эти рёбра удаляем из графа,
а те рёбра, которых, напротив, в этом графе изначально не было, проводим.
Такой вот двойственный граф G с чертой.
Рассмотрим этот граф.
Мы помним с вами, что любое независимое множество вершин исходного графа,
превращается в полный подграф в графе G с чертой.
И наоборот — любой полный граф, находившийся в графе G,
превращается в независимое множество внутри графа G с чертой.
Это понятно.
Мы те рёбра, которые были, удалили, а те, которых не было, мы те провели.
Ну хорошо.
Вот рассмотрим граф G с чертой.
Что означает,
что в графе G нет треугольников, с точки зрения графа G с чертой?
Ну естественно, это означает, что в G с чертой нет
независимых множеств на 3 вершинах.
На 3 вершинах.
Повторяю, треугольник превращается в независимое множество мощности 3.
Но если у нас нету треугольников,
то значит в двойственном графе нету независимых множеств на 3 вершинах.
То есть α(G с чертой) ≤ 2.
Вот давайте, это и есть наша α маленькая.
Мы знаем, что число независимости графа G с чертой точно не превосходит 2,
потому что в нём нету больших независимых множеств.
Ну соответственно, по теореме, которую мы только что доказали,
в G с чертой, внимание,
в G с чертой, именно в G с чертой достаточно много рёбер.
Не менее...
Давайте сообразим нежели сколько рёбер.
Ну что, надо вместо α подставить 2.
Давайте напишем.
У нас получится n * [n/2] − [n/2]
* ( [n/2] + 1 ) рёбер.
Ну я вот здесь вот 2, которая равняется α,
сократил с 2, которая находилась в знаменателе у арифметической прогрессии.
В данном случае я поступил таким макаром.
Значит, вот мы знаем по нашей теореме, что не меньше чем столько рёбер.
Ну давайте я, чтобы было максимально понятно, немножко нестрого сейчас скажу.
Смотрите вот на эту величину.
Ну понятно, что примерно,
ну в каком бы то ни было смысле, например, в смысле асимптотики, по n,
стремящемся к бесконечности, примерно эта величина чему равна?
n* [n/2] ≈ n²/2.
Разница там очень невелика.
Ну и здесь тоже, в общем, эта единичка, она к n/2 почти ничего, по сути,
не добавляет.
Поэтому примерно у нас получается −n²/4 то есть n²/4 штуки рёбер.
Получается, что если мы предполагаем отсутствие треугольников в графе G,
то в графе G с чертой у нас получается не меньше, чем n²/4 рёбер.
Но тогда в исходном графе
G без черты (если в графе G чертой не меньше чем n²/4 рёбер),
то в исходном графе G не более Cn по 2
− n²/4 рёбер.
Ну потому что, ещё раз, ну как получается G из графа G с чертой?
Мы берём все рёбра полного графа, и из них удаляем те рёбра,
которые есть в графе G с чертой.
Вот их не меньше чем n²/4, значит, в результате их удаления получается граф G,
и вот в этом графе не больше чем Cn по 2 − n²/4 рёбер.
В свою очередь, Cn по 2 — это, конечно, n* (n−1) / 2 − n²/4.
Ну и здесь я могу просто сказать, что это не превосходит
n²/2 − n²/4, то есть опять же n²/4.
Получается, что в исходном графе, про который мы предположили,
что в нём нету треугольников, точно не больше, чем n²/4 рёбер.
Это классический результат, который многие слушатели могли когда-то слышать,
в каком-нибудь контексте, это называется теоремой Турана.
И на самом деле, та теорема, которую мы с вами доказали,
будучи полным аналогом вот этого результата,
она и называется в честь своего автора, который доказал её при произвольном α.
Здесь α = 2, а Туран доказал её при произвольном α.
Ну вот давайте, я напишу его имя.
Тут важный такой филологический, что ли, момент состоит в том, что он именно ТурАн,
а не ТУран, как многие считают.
Это фамилия венгерская, и её действительно правильно произносить так,
как я её сейчас произношу.
И даже вот этот акцентик, который я сейчас нарисовал, имея в виду просто обычное
ударение, его рисуют в оригинальном написании фамилии.
Это выдающийся венгерский математик, который очень много всего
интересного и важного в экстремальной теории графов придумал в своё время.
И вот, в частности,
он доказал этот совершенно классический результат ещё в 40-е годы XX века.
Результат о том, что вот, если граф не содержит больших полных подграфов,
то у него достаточно мало рёбер.
Или наоборот, если граф не содержит достаточно больших
независимых множеств вершин, то у него достаточно много рёбер.
Достаточно мало, а там достаточно много.
Ну это одно и то же по сути.
Вот то, что мы сейчас доказали, повторяю,
это называется замечательной теоремой Турана.