Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Решение задачи
Loading...
來自 Moscow Institute of Physics and Technology 的課程
Теория графов
320 個評分
從本節課中
Экстремальная теория графов. Теорема Турана
На этой неделе мы начнем разговор про экстремальную теорию графов, которая ставит вопросы про то, с какого момента графы начинают обладать тем или иным свойством. В частности, мы выясним, сколько ребер должен иметь граф, чтобы он гарантированно содержал треугольник. В конце лекции мы узнаем, что графы на плоскости в экстремальных задачах ведут себя несколько по-другому, нежели графы абстрактные.
與講師見面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Ну что друзья, давайте доказывать.
Надо рисовать сардельки, понятное дело, то есть мы вернемся сейчас в каком-то смысле
к тому рассуждению, которое было турановским, но немножко его модифицируем,
ориентируясь на свойства как раз такого вот дистанционного графа.
То есть графа, ребра которого, имеют длину единицы на плоскости.
Рисуем сардельку, в ней в нынешних обозначениях
четыре n вершин и у нее число независимости не больше чем n.
Рисуем в точности так же,
как у нас было нарисовано в доказательстве теоремы Турана.
То есть выгрызаем максимальное по мощности подмножество,
состоящее из не более чем n вершин.
Ну вернее пока не выгрызаем,
а только рисуем и которое является независимым в этом графе.
Вроде бы все то же самое и понятно, что если мы возьмем произвольную вершинку,
которая находится вне этого множества, но при этом конечно принадлежит нашему
множеству вершин, то эта вершинка отправит хотя
бы одно ребро внутрь нашего независимого множества.
Ну давайте обозначим его А.
У нас уже такое обозначение было и его вполне можно ввести снова.
Значит понятно, что каждая вершина из вне отправляет хотя бы
одно ребро внутрь нашего независимого, потому что оно максимальное по мощности.
Это я просто в точности повторяю турановское рассуждение.
Но давайте попробуем действовать немножко аккуратнее.
Давайте попробуем выделить в множестве V − A,
вот в этом множестве V − A,
выделим те вершины, которые, внимание,
отправляют ровно одно ребро внутрь множества А.
Значит V − A выделим, отдельно рассмотрим те вершины,
которые отправляют в А
ровно одно ребро.
Ну то есть суть простая — если окажется,
что этих вершин не больше, ну или вернее, сильно меньше,
чем всего есть вершин V − A, тогда есть вершины, каждая из
которых отправляет внутрь А как минимум два ребра и за счет этого мы победим.
Потому что мы учтем каждое ребро не единожды,
как это было в турановском рассуждении, а дважды.
Ну давайте докажем такую замечательную лемму.
Лемма… Лемма говорит нам следующее
— таких вершин
не больше,
чем 2n.
Так, друзья, давайте немножко переведем дыхание,
попробуем осознать, что происходит.
Значит, допустим… Допустим мы уже эту лемму доказали.
Сейчас мы ее докажем, это самая красивая в нашем рассуждении будет.
Ну вот допустим мы эту лемму доказали, то есть доказали, что вершин, которые
отправляют внутрь А ровно одно ребро, не слишком много — не больше чем 2n.
Вот я здесь уже завел такое разграничение, вы, наверное,
на него глядели и думали: «Зачем оно?».
Вот я его завел.
Вот это вершины, до вот этого разграничения,
которые подчиняются определению из леммы,
то есть каждая из которых отправляет внутрь А ровно одно ребро.
Вот допустим, мы доказали, что таких вершин не больше чем 2n штук.
Но что тогда у нас получается?
У нас получается: всего вершин вот в этом множестве V − A,
всего вершин в множестве V − A, их же не меньше чем 3n.
Их 3n штук.
И не больше чем 2n таковы, что они отправляют по одному ребру ровно,
но тогда это означает, что вот здесь вот не меньше чем n вершин.
И каждая из этих не меньше чем n вершин отправляет
внутрь А хотя бы два ребра.
То есть в сумме получается
не менее
4n ребер.
Почему 4n?
Потому что 2n отсюда и удвоенное количество,
не меньше чем 2n, из вот этой части нашего разграничения.
В сумме получается не менее 4n ребер.
Вместо тех
3n, которые были у Турана.
Ну и все.
А дальше действуем по турановски, то есть выгрызаем эту сардельку, просто,
тупо по-турановски находим еще 2n ребер, еще n ребер, и в сумме получаем 7n.
То есть главное вот сейчас — выиграть эту n-ку дополнительную.
На первом шаге турановского рассуждения надыбать, так сказать,
не 3n ребер, как это нам удалось, когда мы рассуждали вслед за Тураном, а 4n.
Тогда в сумме получится не 6n, а 7n.
3n заменилось на 4n и сумма, соответственно,
превратилась не в 6n, а в 7n.
Вот если мы доказываем эту лемму, то вот такое не хитрое рассуждение,
которое вслед за ней идет, оно полностью завершает решение олимпиадной задачи.
Остается лишь доказать, что таких вершин, то есть вершин,
которые отправляют внутрь А ровно одно ребро, действительно не больше чем 2n.
Так, доказательство леммы.
Давайте вопреки утверждению, которое здесь написано, предположим противное.
Предположим противное и в итоге придем очень красиво к противоречию.
Значит предположим, таких вершин
не больше чем 2n, то есть не меньше чем 2n + 1.
Не меньше чем 2n + 1.
Вот таких вот вершин, каждая из которых отправляет сюда ровно одно ребро,
не меньше чем 2n + 1.
Я утверждаю, что в этом случае,
то есть если наше предположение противного верно… Я утверждаю,
что в этом случае… Надо очень внимательно слушать, чтобы понять, что происходит.
Я утверждаю, что в этом случае, внутри А, в свою очередь… Вот внутри этого множества
А есть хотя бы одна вершина, которая имеет
не менее 3 соседей внутри вот этого множества.
Не менее 3 соседей внутри вот этого множества.
Так… Следовательно,
есть в А вершина, ну скажем,
y, которая имеет не
менее 3
соседей вот в этом множестве вершин, в нашем множестве вершин.
Мощность которого, как мы предположили, не меньше чем 2n + 1.
В нашем множестве вершин.
Ну почему это так?
Ну это какой-то принцип Дирихле очевидно.
Надо как-то по принципу Дирихле действовать.
Ну рассуждение очень простое.
Если бы это было не так… Если бы в А каждая вершина имела не более
2 соседей… Ну вот эта вершина имеет не более 2 соседей тут.
Вот эта вершина имеет не более 2 соседей тут.
Вот эта.
Каждая вершина имеет не более 2 соседей тут, но ведь вершин-то всего
не больше чем n и если каждая из не более чем n вершин имеет не более,
в свою очередь, 2 соседей, то всего этих соседей не больше чем 2 * n,
а мы то предположили, что их хотя бы 2n + 1.
Вот мы сделали такое предположение, что их хотя бы 2n + 1,
но значит не может такого быть,
чтобы каждая вершинка из множества А, всего таких вершинок ведь не больше чем n,
чтоб каждая вершинка из множества А имела здесь не более 2 соседей.
Если бы их было не более 2 для каждой, то их всего было бы не больше чем 2n,
но мы-то предположили, что их не меньше чем 2n + 1.
Никакого пока противоречия, просто следствие,
которое я вот только что доказал.
В А есть некая вершина y,
которая имеет не менее 3 соседей вот в этом нашем множестве вершин.
И я этих трех соседей даже нарисовал.
Если бы не более 2, то в сумме не получилось бы 2n + 1.
Всё. Значит, есть такая вершина.
Вот давайте ее обозначим y, а ее соседей x1, x2, x3.
И я повторяю, x1, x2, x3 — это такие вершины,
каждая из которых имеет только y соседом внутри A.
Только y, никого больше.
Это единственное ребро, которое x1 отправляет внутрь А,
просто по определению нашего множества.
В нашем множестве сейчас находятся вершины,
каждая из которых соединена ровно одним ребром с множеством А.
Вот это то самое ребро, которым x1 соединена с y,
а это то самое То самое ребро, которым x2 соединена с y.
И всё. Другого ребра, идущего внутрь A, ни из x1,
ни из x2, ни из x3 нету.
Вот.
Нашлась вершина y, и нашлись вершины x1, x2, x3 в нашем множестве.
Отлично.
Допустим на мгновение,
что нет, например, ребра (x1, x2).
Ну вот нет такого ребра в нашем графе.
Допустим.
Допустим, нет такого ребра.
Вот этого ребра нет.
Нету.
Не сложилось.
Смотрите, какая прелесть.
Если это допущение верно,
удалим из A вершину
y и добавим, наоборот,
вершины x1, x2.
Что получится?
А получится, товарищи, независимое множество.
Почему независимое?
Потому что мы предположили, что вот этого ребра нет, мы просто это допустили.
Ну нет этого ребра, не сложилось.
Дальше — y мы удалили.
Но, значит, пропали вот эти ребра.
А x1, x2 добавили.
Это ребро, повторяю, появиться не могло, потому что мы допустили, что его нет.
А ребер из x1 в A кроме x1,
y и ребер из x2 внутрь A кроме x2, y, как я несколько раз повторил, больше нету.
Это были единственные ребра, которые могли возникнуть между вершинами x1,
x2 и какими-либо вершинами из множества A.
Но, значит, если мы удалили y и добавили x1, x2,
возникло новое независимое множество.
В нем нету ребер.
Этих нету, никаких других из x1, x2 внутрь A тоже нету.
В самом A нету, потому что это независимое множество, и этого нету,
потому что мы допустили, что его нету.
Так, возвращаюсь сюда.
Значит, мы удалили из A вершину, добавили две вершины,
получилось в рамках нашего предположения,
получилось независимое множество.
Но, товарищи!
Мощность-то его больше, чем мощность A.
Мы одну вершину удалили, а две добавили.
A же — это максимальное по мощности независимое множество.
Так не бывает, так не может быть.
Что же не так?
Так не может быть.
A — максимальное, мы не можем увеличить его так,
чтобы снова получилось независимое множество.
Так не может быть.
Значит, что неверно?
Нет, пока не вот это неверно.
Пока неверно вот это допущение.
Мы зря допустили, что нет ребра (x1, x2).
Именно оно, вот это отсутствие ребра привело к тому,
что можно было добавить вот эти (x1, x2) без ущерба для независимости.
Значит, неверно вот это допущение.
Значит, есть ребро (x1, x2) в нашем графе.
Если его нет, получаем нонсенс.
Только что выяснили — увеличилось максимальное по мощности независимое
множество.
Значит, такое ребро есть.
Аналогично совершенно рассуждаем
и получаем, что есть (x1, x3) и (x2, x3).
Полная симметрия, никакой разницы.
Совершенно точно так же получаем, что не только (x1,
x2) должно присутствовать в нашем графе, но и (x1, x3), и (x2, x3).
Сейчас я вернусь к картинке.
Итак, мы выяснили, что обязательно должно присутствовать (x1, x2),
совершенно аналогично (x1, x3) и совершенно аналогично (x2, x3).
Э?
Чего получилось?
Получился...
Вот, это всё были шахи, да, как в шахматах, это всё были шахи.
А получился мат, потому что...
Смотрите, что возникло, просто глядите сюда.
Полный граф на четырех вершинах K4.
Ну мы начали с того, что дистанционный граф на плоскости не может
содержать полного графа на четырех вершинах.
Это тетраэдр.
Его не бывает на плоскости.
Тетраэдр с длинами сторон, равными единице, на плоскости реализовать нельзя,
мы с этого начали.
Всё.
Это мат.
И вот это уже мат по отношению к исходному предположению.
Мы сделали предположение, что вершин не меньше, чем 2 n + 1.
Из этого предположения нашли y,
исходя из этого предположения нашли y и его трех соседей.
Выяснили, что никак иначе быть не может, как если все эти
три соседа попарно перелинкованы, содержат вот такие вот ребра.
Ну и получили мат по отношению к нашему исходному предположению,
потому что тогда K4 реализуется на плоскости дистанционным графом.
Это, повторяю, чушь.
Ну и лемма доказана.
Предположение неверно, то есть вершин, каждая из которых отправляет
внутрь A ровно одно ребро, все-таки действительно не больше, чем 2 n.
Из этого предположения получилась чушь.
Всё. Задачка олимпиадная решена.
И дальше мы перейдем к изучению рамсеевских задач.
Вот это всё были турановские задачи, а сейчас будет еще один классический,
очень важный класс задач экстремальных, которые называются рамсеевскими.
Вот к этому мы сейчас перейдем.
