Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Значения R(s,t) для малых s
Loading...
來自 Moscow Institute of Physics and Technology 的課程
Теория графов
268 個評分
從本節課中
Теория Рамсея
На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую совсем разные по сложности задачи.
與講師見面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Отлично.
Друзья, давайте продолжим рассуждать про числа Рамсея.
Мы разобрались-то, по сути, только с R(3, 3).
Априори ведь даже не понятно, а почему они всегда существуют?
Вот, между прочим, это же не очевидный вопрос: почему величина от R(s,
t) определена конечно?
Определена корректно.
Ведь мы говорим о минимальном n,
таком что вот нет полного хаоса для любого графа на n вершинах и так далее.
А почему это минимальное n существует?
Может, наоборот, для каждого n можно такой найти поганый граф, в котором нету
ни полного графа на s вершинах, ни независимого множества вершин мощности t.
Вот нет ни того, ни другого.
Ну может, для каждого n такой поганый граф существует.
Ну да, для s = 3 и t = 3 мы определились — такой ситуации быть не может.
Такое возможно только при n = 5, но уже начиная с n = 6 хаоса нет.
А может быть, если мы возьмем s = миллиону, а t = миллиарду,
то-таки при любом n найдется какая-нибудь бяка, которая портит все.
Но вот нет, это не самом деле не так.
И первым это заметил, собственно, Рамсей, как это ни удивительно,
который ввел свои числа в 1930 году и получил
для них конкретные эффективные оценки сверху, зависящие только от s и t.
Правда эти оценки получились не очень хорошими, они получились очень большими.
Но тем не менее Рамсей доказал, что R(s,
t) существует конечно при любом s и t,
при любых s и t.
Ну давайте мы с вами для начала обсудим какие-нибудь параметры,
отличные от двух троек.
Нет, не ждите, что я буду рассматривать сейчас 3 и 4, например.
Такое тоже можно, но это, скорей, в упражнениях.
В упражнениях мы этим, конечно, обязательно позанимаемся.
А сейчас я хочу рассмотреть какие-то более общие серии случаев, когда все понятно.
Вот, например, давайте рассмотрим такое число R(1, t).
s = 1, кажется, что совсем просто.
Вот когда задаешь этот вопрос сидящей перед тобою публике,
вопрос о том, а чему, как вы считаете, равняется вот эта величина R(1, t)?
Зачастую это тем не менее приводит слушателей в тупик,
ставит слушателей в тупик.
потому что не очень понятно, что значит полный граф на одной вершине.
Ну а что, собственно, полный граф на одной вершине — это и есть одна вершина.
В каком-то смысле все очень просто.
Единственное, что надо вот прочувствовать эту логику.
Ответ на поставленный вопрос тривиален — единица.
R(1, t) в точности равно 1.
Почему?
Ну если мыслить в терминах раскрасок, да, вот красные и синие ребра у полного графа,
то можно сформулировать это аллегорически: все крокодилы
в Москве-реке или там в канале имени Москвы все крокодилы красные.
Ну что я хочу сказать?
Вот у меня есть полный граф, полный граф на одной вершине.
Я пытаюсь раскрасить все ребра вот этого полного графа.
Какие-то в красный цвет, какие-то в синий цвет.
Ну так нет же ребер у этого полного графа!
И крокодилов, я надеюсь, в Москве-реке тоже нету.
И в канале имени Москвы тоже, наверное, нету.
Как вот у этого полного графа на одной вершине на самом деле нет ни одного ребра,
так что мы красим элементы пустого множества, которых нету.
Так же точно и с рекой происходит, и с крокодилами в ней.
Поэтому утверждение о том, что при любой раскраске ребер полного
графа на одной вершине в красный и синий цвета либо найдется
полный подграф на одной вершине, в котором все ребра красные.
Оно уже верное, потому что, да, найдется полный подграф на одной вершине,
в котором все ребра красные — это вот этот самый граф.
Сам граф является своим собственным полным подграфом, у которого все ребра красные.
Ну такая издевательская казуистика.
При любой раскраске ребер в красный и синий цвета.
При любой раскраске крокодилов в Москве-реке найдется крокодил,
найдется кусочек реки, в котором все крокодилы красные.
Вот так вот я бы сказал.
Не крокодил, конечно, найдется, а кусочек реки.
Вот, ну в общем, R(1, t) = 1.
Ну очевидно, что R(s, t) = R(t, s).
Определение, конечно, симметричное.
И вот в этом месте я жевать не стану, потому что, кажется,
что это правда очевидно.
Если кому-то не очень, то, пожалуйста, продумайте этот момент.
Должно быть очевидно по определению.
Ну и, соответственно, понятно, что R(t, 1) тем самым тоже найдено и тоже
равно единице, Хотя вот этот факт в общем уж совсем очевиден.
Если мы разобрались с этим, то с этим разберемся точно так же.
Вот.
И еще один простой случай есть.
R(2, t) — это величина равняется t, и это доказывается тоже совсем легко.
Доказывается примерно так же, как мы доказывали утверждение про R(3, 3).
А именно, мы сперва доказываем, что R(2, t) не превосходит t,
точно так же, как ранее мы доказывали, что R(3, 3) не превосходит 6.
Ну а затем доказываем, что R(2, t) больше либо равняется t.
Значит, как доказать, что R(2, t) не превосходит t?
Ну если мы доказали оба этих неравенства, то, естественно,
мы и равенство точное установили.
Давайте сначала поймем, как доказывается неравенство сверху оценка?
То есть R(2, t) не превосходит t?
Что это значит?
Что значит, что какое-то число Рамсея не превосходит данного конкретного числа t?
Это значит, что если мы возьмем любой граф на t вершинах...
Ну давайте я здесь это напишу: возьмем любой
граф на t вершинах,
[БЕЗ_ЗВУКА] то мы хотим доказать,
что, взяв вот тот произвольный граф, мы либо найдем в
нем полный подграф на двух вершинах,
либо независимое множество на t вершинах.
Ну так вот мы взяли любой граф на t вершинах.
Либо у него есть хотя бы одно ребро,
либо у него есть хотя бы одно ребро,
[БЕЗ_ЗВУКА] либо в нем ребер нет.
Это тривиальный факт, я даже не знаю, как это еще комментировать.
Либо в нем ребер нет.
Ну так, товарищи, ребро — это и есть полный подграф на двух вершинах.
Полный подграф на двух вершинах — это ребро.
То есть либо у него есть хотя бы одно ребро, ну, значит,
в этом случае у него есть полный подграф на двух вершинах — вот это самое ребро.
Либо в нем ни одного ребра нет, но тогда он целиком — вот этот граф на t вершинах
— свободен от ребер, то есть образует независимое множество мощности t.
То есть очевидная совершенно альтернатива: либо — либо.
То есть, конечно, R(2, t) не превосходит t.
Ну а что значит доказать, что R(2, t) не меньше, чем t?
Это значит доказать, что при t – 1 вершине вот то,
что я написал, вот такая вот альтернатива уже неверна.
Ну, действительно, возьмем
граф на t – 1 вершине,
в котором нету ребер.
Ну то есть такое вот независимое множество мощности t – 1.
В котором нет ребер, то есть независимое множество вершин мощности t – 1.
Это вполне себе пример графа на t – 1 вершине.
Ну так вот какая неприятность: в нем нет ребер,
ну значит в нем нет полных подграфов на двух вершинах,
то есть нет полных подграфов на двух вершинах.
[БЕЗ_ЗВУКА] Но в нем,
к сожалению, нет и независимого множества мощности t.
Потому что несмотря на то, что этот граф сам является независимым множеством,
сам образует независимое множество, но в нем вот вершинок не хватает.
В нем только t – 1 вершина.
В нем нет независимого множества мощности t.
Давайте: но в нем нет также и независимого
множества мощности t.
Мощности (t – 1) — пожалуйста, а вот t нету.
Ну, значит, как это было в случае с R(3,
3) с двумя вложенными друг в друга циклами на пяти вершинах,
которые не содержали треугольников, так и здесь вот есть пример графа,
который не обладает, к сожалению, ни одним из двух альтернативных свойств.
В нем нет ни полного подграфа на двух вершинах,
ни независимого множества вершин мощности t.
Это и означает, в свою очередь, что R(2, t) больше либо равняется t,
и равенство мы доказали.
Вот. Ну в каком-то смысле только что доказанные
простенькие утверждения сподвигают на мысль, что, наверное,
можно двигаться дальше.
Наверное, можно что-нибудь сказать про величину R(3, t).
Ну не могу же я только в рамках лекций разжевывать какие-то простые утверждения.
Нет, я не буду сейчас ничего сложного доказывать относительно этой величины,
но я порадую слушателей следующим утверждением.
До сих пор, до сих пор человечество не знает не только формулы общей для
числа Рамсея R(3, t), но даже не знает, чему эта величина равна асимптотически.
То есть не знает асимптотики этой величины — такой функции, что если мы R(3,
t) на нее поделим, то в пределе при t, стремящимся к бесконечности, получится 1.
Есть лишь пара оценок, тоже асимптотических,
каждая из которых — это сложнейшая теорема современного дискретного анализа.
Ну то есть вот люди, которые прослушивают наши лекции, по идее,
смогут уже немножко вникать в подобные результаты.
Это очень круто.
А именно известно следующее сейчас: R(3,
t) не превосходит некоторой функции
вида (1 + о(1)), ну то есть чего-то асимптотически равного 1,
помноженной на t квадрат и поделенной на натуральный логарифм t.
Вот откуда бы он только тут взялся, да?
Мы когда рассматриваем треугольник уже супротив независимого множества мощности
t, у нас возникают какие-то загадочные логарифмы.
И известно также, что R(3,
t) больше либо равняется (1/4 +
о(1)) умножить на ту же самую величину.
То есть счастье состоит в том, что мы по крайней
мере знаем асимптотический порядок роста величины R(3, t).
Мы знаем,
что зазор между верхней и нижней оценками в асимптотике всего лишь в 4 раза.
Это замечательно, 4 — это константа.
Могло бы быть и хуже.
Так бывает в дискретной математике, к сожалению,
когда зазор между известными оценками растет с бешеной скоростью,
и об этом мы сегодня тоже обязательно поговорим.
Такое у нас с числами Рамсея еще случится.
Но вот даже для случая R(3, t),
то есть чуть-чуть оторвались от тривиальности, от R(1, t) и R(2, t).
Даже для случая R(3, t) уже имеется асимптотический зазор в 4 раза
между известными верхними и нижними оценками.
Вот это специалист может доказать на пару страниц, а это — несколько десятков.
Причем до последнего времени самое лучшее, что было известно,
— не четверка в знаменателе, а 162.
И это был прорывной результат в 1995 году,
когда написали здесь 1/162-ю, потому что до того было все совсем плохо,
даже порядок роста величины числа Рамсея не был известен.
Ну я не думаю, что так необходимо здесь писать, кто когда это сделал.
Вот это результат 1980 года, вот это результат буквально 2014 года.
Такая вот удивительная наука про числа Рамсея, что она до сих пор
динамично развивается и вызывает большой интерес у специалистов.
