Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Доказательство теоремы Турана
Loading...
来自 Moscow Institute of Physics and Technology 的课程
Теория графов
266 个评分
从本节课中
Экстремальная теория графов. Теорема Турана
На этой неделе мы начнем разговор про экстремальную теорию графов, которая ставит вопросы про то, с какого момента графы начинают обладать тем или иным свойством. В частности, мы выясним, сколько ребер должен иметь граф, чтобы он гарантированно содержал треугольник. В конце лекции мы узнаем, что графы на плоскости в экстремальных задачах ведут себя несколько по-другому, нежели графы абстрактные.
与讲师见面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
На самом деле доказательство очень-очень простое.
Как водится, если мы хотим изобразить множество вершин графа,
рисуется здоровая-здоровая «сарделька».
Так.
Вот такая вот большая сарделька символизирует собою наше множество вершин.
Ну и давайте я через запятую напишу n, желая подчеркнуть,
что вершин в точности n штук.
Ну это мы с вами знаем.
Теперь давайте в этом множестве вершин выделим какое-нибудь
самое большое по мощности независимое подмножество.
Давайте я еще раз повторю, чтобы не писать это на доске.
Смысл-то очень простой.
Вот в этой сардельке выделим самое большое по мощности независимое подмножество.
Ну вот оно как-то так, допустим, расположено.
И это подмножество состоит из вершин, которые попарно не соединены ребрами.
Оно независимое и при этом оно имеет, как я уже сказал,
максимальную мощность среди всех независимых множеств вершин,
которые живут вот в этой сардельке, то есть в множестве V.
Самая-самая большая.
Ну понятно, что самая большая имеет мощность α.
Я это и напишу.
По определению просто.
Вот у нас есть множество вершин, которые имеют как раз максимальную
возможную мощность среди всех независимых множеств.
Давайте его тоже как-нибудь обозначим, скажем,
буквой A, и α поставим после запятой для единообразия.
Здесь V запятая n, а здесь A запятая α.
То есть вполне одинаковое обозначение получается.
Теперь смотрите,
что вытекает из максимальности этого независимого множества.
Вытекает очень простая вещь.
Смотрите, вот возьмем мы какую-нибудь вершинку,
которая лежит в множестве V, но не лежит в множестве A.
Поскольку A — максимальное,
среди всех независимых, ясно, что вот из этой вершинки хотя бы
одно ребро отправляется внутрь множества A, в какую-то вершину из множества A.
Потому что если бы ни одно ребро вот эту вершину с множеством A не соединяло,
ну тогда мы просто добавили бы эту вершину к множеству A и по-прежнему получили бы
независимое.
Но у нас A максимальное по мощности, то есть мы не можем ничего к нему добавить.
Такая вот тонкость.
Значит, каждая вершина,
которая находится вне множества A, вот в этой огромной сардельке,
она отправляет хотя бы одно ребро внутрь этого множества.
При этом что является целями этих ребер, мы не знаем.
Может быть, для каких-то ребер общая цель, для каких-то цели разные.
То есть целевые вот эти вершины, куда отправляются ребра, они, конечно,
могут быть разными.
Вот. Ну это для нас сейчас совершенно неважно,
важно только то, что каждая вершина из множества V минус
A отправляет хотя бы одно ребро внутрь множества A.
Ну давайте это зафиксируем.
Каждая вершина
из вот такого вот множества V минус A отправляет ребро (свое отдельное,
понятно, что все эти ребра разные), отправляет ребро внутрь множества A.
Повторяю, необязательно одно, может быть, несколько.
Хотя бы одно ребро точно отправляет.
Ну таким образом, сколько у нас уже есть заведомо ребер в нашем графе?
Давайте напишем.
Таким образом, мы уже насчитали
не менее (n – α) ребер.
Понятно, почему (n – α)?
Ну понятно, конечно.
Вершин, которые находятся вот в этом множестве V минус A,
их же в точности (n – α).
И каждая из этих вершин, как мы выяснили, за счет максимальности вот этого
независимого множества отправляет внутрь него свое отдельное ребро.
Может быть, несколько, но хотя бы одно.
Всего вершин, повторяю, (n – α).
Значит, ребер, которые из них выходят внутрь A, тоже (n – α).
И все — вот это ребра нашего графа.
Мы точно знаем, что в нашем графе есть как минимум (n – α) ребер,
которые идут вот таким образом из V минус A внутрь A.
Ну это явно не все.
Ресурс-то не исчерпан.
Да и теорема сформулирована так, что, кажется, должно быть гораздо больше.
(n – α) — это мизер какой-то.
Ага! А давайте сделаем так.
Давайте интерпретировать вот это A,
как подсардельку внутри вот этой большой сардельки.
Возьмем и отгрызем вот эту подсардельку.
Просто выедим ее оттуда, отгрызем.
Ну ладно, отгрызем...
Выкинем!
Хорошо!
Выкинем из множества вершин V множество вершин A.
Множество вершин A.
Разумеется, мы при этом очень сильно «покоцаем» наш исходный граф.
Когда мы будем эту сардельку в маленькую выгрызать подсарделечку, да, мы,
конечно, потеряем не только те вершины, которые туда входят, но и все ребра,
которые в нее идут.
Мы выкинем из V множество вершин A,
а из E (из множества ребер нашего графа) выкинем все ребра,
которые идут внутрь A,
ну то есть которые мы только что перечислили, которых не меньше,
чем (n – α), которые идут внутрь этого множества A.
Итак, у нас получился некий новый граф, который, естественно,
является подграфом в исходном графе.
Внимание!
Вот это очень важный момент, я его еще раз повторю.
После того как мы из V выгрызли вот эту подсардельку A,
а из множества E удалили все ребра, которые смежны с этой подсарделькой,
то есть вот те самые, которых (n – α) или даже больше, вот после этого
на выходе у нас остался некий подграф исходного графа.
Ну правильно же,
подмножество вершин осталось V минус A — это его множество вершин.
И ребра — это те ребра,
которые остались после удаления вот этих как минимум (n – α) штук.
Так.
Ну давайте это зафиксируем.
Возник подграф исходного графа.
Возник подграф исходного графа.
Давайте...
А я давайте так прямо и нарисую.
Вот я сейчас прямо ее выгрызу.
Хоп!
Ну уж как получится.
Рисую я плохо.
Имеется в виду, что я нарисовал V без множества A, вот я ее отгрыз.
Эту вот подсарделечку я ее выгрыз.
Ее больше нет.
Вот осталось только такое множество вершин, которое сейчас нарисовано.
Это множество вершин возникшего подграфа — того подграфа,
который получился в результате выгрызания.
Так.
Сколько у него вершин?
Ну вершин...
Давайте, у него вершины — это множество V минус A.
Вершин у этого графа, разумеется (n – α).
Вот вершин у него (а мы всегда через запятую пишем вершины,
правда же?) вершин у него в точности (n – α).
Видите, вот здесь α вершин было, здесь n.
Выкинули α вершин, осталось (n – α) вершин.
Вот в этой выгрызенной сарделечке в ней уже (n – α) вершин.
Но я занудил, конечно, давайте я теперь скажу самую важную вещь.
Ведь в этой вот подсарделечке,
которую мы получили в результате выгрызания другой подсарделечки,
в ней же тоже есть максимальное по мощности независимое множество вершин.
Ну давайте его где-нибудь нарисуем.
А неважно совершенно, вот так, например, нарисуем.
Вот в этой выгрызенной штуковине, в свою очередь,
есть некоторое множество вершин, которое не порождает никаких ребер,
которое свободно от ребер, независимое множество вершин.
Правда?
Да?
Есть.
А какова его мощность, товарищи?
Мощность-то у него какая?
Ну согласитесь, что если вот в этом уменьшенном графе, который, как мы знаем,
является подграфом исходного, вот в этом уменьшенном графе есть некоторое
независимое множество, то ведь, конечно же, это независимое множество,
в свою очередь, является независимым множеством вершин исходного графа.
Ну мы выкинули часть ребер.
Мы же вот так их выкинули, крест-накрест.
Понятно, что если это независимое множество,
то оно независимое множество и в исходном графе тоже.
Ну то есть количество вершин в нем...
Давайте его как-нибудь обозначим B.
А количество вершин в нем ну точно не больше, чем α,
потому что α — это максимальное количество вершин в независимом множестве,
которое может быть у графа G.
Ну значит, не больше, чем α и в максимальном независимом множестве,
которое может быть у нового графа,
полученного из G выкидыванием первого вот этого вот независимого множества A.
Не больше, чем α.
А дальше рассуждение итерируется.
Смотрите, раз это максимальное по мощности независимое множество,
значит, мы не можем к нему добавить никакой вершины извне его.
А что значит не можем добавить?
Это значит, что она отправляет внутрь B хотя бы одно ребро.
И это касается каждой вершины, которая извне этого B расположена.
Ну то есть я могу взять и дословно повторить всю фразу,
которая у меня сейчас написана вверху доски: «Каждая вершина из множества
V минус A минус B отправляет ребро внутрь B».
Я вот это на картинке нарисовал, и я думаю, что глядя вот на эту фразу,
можно уже успокоиться и второй раз эту фразу не повторять.
Каждая вершина из V минус A минус B извне вот этой вот «подсарделечки»,
она отправляет хотя бы одно ребро внутрь «сардельки».
Ну и вот эту фразу я уж повторю: таким образом,
мы насчитали еще
не менее скольких ребер?
Ну, конечно, n минус 2α.
У нас n – α вершин, и здесь не больше, чем α.
Значит, вот в этом множестве V минус A минус B — в нем же не меньше,
чем n – 2α вершин.
Таким образом, мы насчитали еще не менее n – 2α ребер.
А дальше продолжаем процесс
выгрызания и вот такого вот рассуждения столько раз, сколько это возможно сделать.
То есть выкидываем вот эту вот штуковину.
В оставшемся графе снова находим максимальное независимое подмножество.
Оно опять имеет мощность, не превосходящую величины альфа.
На сей раз каждая вершина, которая извне его,
конечно, тоже отправляет в него хотя бы одно ребро.
Но таких вершин уже n – 3α, ну и так далее.
Давайте так и напишем: и так далее.
[БЕЗ_ЗВУКА] Остается только сообразить,
сколько всего такого рода шагов мы можем совершить.
Ну а сколько таких шагов мы можем совершить?
Да столько, сколько раз можно выгрызать очередную «сарделечку»,
в которой ровно α вершин.
Мы не знаем, сколько.
Поэтому давайте считать,
что мы на худой конец вынуждены выгрызать «подсарделечку» мощности α.
И вот мы каждый раз α, α, α, α удаляем.
Сколько таких шагов мы можем сделать?
Всего было n вершин изначально.
Удалили α вершин, потом удалили еще α вершин, вот эти вот.
Потом удалили еще какие-то α вершин,
которые ничего общего с первыми двумя не имеют.
Еще какие-то α.
Ну и сколько же раз так можно сделать?
Ну, конечно, надо поделить на α.
Было всего 10 вершин.
Вот удалили 3 вершины, потом еще 3 других вершины, и еще 3 других вершины.
Ну понятно, что десять третьих.
Но только вот с округлением до ближайшего целого вниз.
То есть вот если n равняется десяти α равняется тройке, то понятно,
что таких вот выкидываний по 3 вершины мы можем сделать ровно 3 штуки.
Ну вот, значит, так и напишем: всего шагов,
разумеется, целая часть от [n/α].
И как мы видели, на первом шаге мы насчитали сразу n – α ребер,
На втором шаге мы насчитали как минимум n – 2α ребер.
На третьем: n – 3α.
Ну и так далее, вплоть до шага с номером целая часть от [n/α].
То есть давайте прямо так и напишем: (n – α) — это сколько
мы насчитали на первом шаге, плюс (n – 2α) — это на втором шаге,
плюс и так далее, плюс n минус целая часть
от [n/α] помножить на α на шаге с номером целая часть от [n/α].
Ну ясно же: на первом шаге (n – α), на втором (n – 2α), всего шагов столько,
вот на последнем шаге мы добавляем вот такую величину, такое количество ребер.
И эта величина неотрицательная.
Так что здесь всё корректно.
Всё правильно.
Мы так и подобрали количество шагов, чтобы каждый раз хоть что-нибудь добавлялось.
А после этого вот мы уже не можем гарантировать,
что будет хоть что-нибудь добавлено.
Отлично.
Давайте посчитаем...
Ой, равно, конечно.
Давайте посчитаем, чему равняется вся эта замечательная сумма.
Ну смотрите: в ней очевидна целая часть от [n/α] слагаемых.
Целая часть от [n/α].
1, 2, 3, целая часть от [n/α].
При этом есть слагаемое, которое идет со знаком плюс,
оно одно и то же во всех скобках.
Поэтому мы просто его умножаем на количество слагаемых.
И получаем n помножить на целая часть от [n/α].
Ровно то самое, что заявлено в теореме.
Теперь со знаком минус идут слагаемые: α,
2α, 3α, целая часть от [n/α] × α.
Ну то есть мы α можем вынести за скобку, а в скобках у нас останется сумма (1 + 2...
Со знаком минус, всё правильно, я нигде не ошибся.
Плюс и так далее, плюс целая часть от [n/α].
Вот вам и пресловутая арифметическая прогрессия.
Вот она.
Всё получилось.
Полное счастье.
n [n/α] – α [n/α]
([n/α] + 1) пополам.
Так и суммируется арифметическая прогрессия обычно.
Теорема доказана.
