Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Пути или звезды
Loading...
Do curso por Moscow Institute of Physics and Technology
Теория графов
268 ratings
Na lição
Теория Рамсея
На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую совсем разные по сложности задачи.
Conheça os instrutores
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Так, товарищи, ну давайте разберем последнюю задачу на графового Рамсея.
Давайте рассмотрим произвольные числа s и
t натуральные, но не думайте, что сейчас пойдет речь про R(st), конечно.
Про него-то ну что, про него все понятно.
Значит, рассмотрим произвольные натуральные числа s и t.
И давайте возьмем
произвольное дерево
на s в степени t вершинах, ну или больше.
Хватит на s в степени t.
Значит, рассмотрим произвольное дерево на s в степени t вершинах.
Утверждается, и мы сейчас это докажем, ну задача такая: докажите, конечно.
Вот сейчас: докажите, что либо в этом
дереве [БЕЗ_ЗВУКА]
есть (s + 1)-звезда,
как и в предыдущей задаче.
Ну давайте я обозначу это T(s + 1).
В предыдущей задаче было T5, то есть у нас была вершина и 5 ребер,
которые из нее выходят.
Ну здесь, соответственно, вершина и (s + 1) ребро, которое из нее выходит.
То есть можно сказать так,
что в этом графе возможно есть вершина степени (s + 1).
Либо, если такой вершины нет, либо есть цепь простая,
простая цепь P2t
с 2t – 1 ребрами,
ну или что тоже самое, с 2t вершинами.
Вот такая
вот еще замечательная альтернатива, которую удается явно просчитать.
Ну что значит явно?
Мы можем доказать,
что соответствующее число Рамсея точно не превосходит s в степени t.
Ну давайте, собственно, рассуждать так, как я уже как бы начал.
Давайте доказывать этот результат.
Смотрите, ну если в этом дереве есть (s + 1)-звезда, то мы в героях,
и можно больше ни о чем не думать.
Поэтому давайте предположим, что в этом дереве нету ни одной (s + 1)-звезды.
Ну если нету, тогда каждая вершина дерева,
каждая вершина имеет
степень не больше, чем s.
Ну раз нету звезды размера (s + 1),
значит степень каждой вершины не превосходит s.
Это совершенно понятно.
Давайте для того, чтобы изловить простую цепь с 2t вершинами,
действовать будем следующим образом.
Помните, у нас когда-то была задача про центр дерева.
Это было давно-давно.
На совершенно другом семинаре.
Мы доказывали, что центр дерева, ну в том случае, конечно, у нас было 10 вершин,
находится в средней точке самой длинной простой цепи нашего дерева.
Ну в том случае самая длинная простая цепь имела 10 ребер, соответственно, 11 вершин,
а в нашем случае мы пока что не знаем, какого размера самая длинная простая цепь.
Ну вот давайте рассмотрим, тем не менее,
рассмотрим самую длинную простую цепь в нашем дереве.
Простую цепь в нашем дереве.
Мы не знаем на сей раз четное в ней количество ребер или нечетное.
Вот этого мы пока сказать не можем.
Поэтому мы не можем строго сказать, что такое прям вот средняя точка этой цепи.
Ну понятно, если у цепи четное число ребер, тогда у нее есть серединка.
А если нечетное, ну тогда у нее есть серединное ребро.
Ну ладно, давайте назовем в кавычках «середина» этой цепи,
вообще говоря, не совсем середину,
а такую точку,
от которой расстояние до каждого из концов нашей цепи таково,
что вот разница этих расстояний не больше 1 по модулю.
Ну то есть расстояние до одного конца, до левого конца,
условно цепи и расстояние до правого конца этой цепи разнятся не больше, чем на 1.
Значит, назовем «серединой» этой цепи такую вершину,
расстояние от которой,
от которой до концов нашей цепи,
— ну то есть опять потенциальный центр дерева, понимаете?
— расстояния от которой до концов нашей цепи, расстояния отличаются
не больше чем на 1.
Не больше чем на 1.
В очередной и в очередной раз повторяю: вот это та самая вершина,
которую можно считать центром дерева.
То есть расстояние от нее до любой другой вершины, понятное дело, не должно,
опять же, превосходить какого-либо из расстояний до вот этих концов.
Это центральная вершина.
То есть рассуждать надо так же в этом месте, как в первом семинаре,
когда мы этим занимались, или так во втором, ну, в общем,
старом семинаре, который давно прошел.
Вот, ну хорошо, давайте обозначим ее v.
Обозначим ее v и посмотрим,
сколько вершин в нашем дереве находится от вот этой вершины на расстоянии ровно 1.
Ну понятно, мы ж предположили, что степень каждой вершины не превосходит s.
Разумеется, это означает,
что на расстоянии в точности 1 от этой вершины никак не больше чем s вершин.
Ну давайте так и напишем.
Значит, на расстоянии 1 от v не больше чем s вершин.
На расстоянии 2 от v, в точности 2,
на расстоянии 2 от v не больше чем сколько вершин?
Ну понятно, на расстоянии 1 не больше чем s, и от каждой из них,
опять же, в виду вот этого предположения,
на расстоянии 1 отстоит не больше чем (s – 1) вершина.
Почему (s – 1)?
Потом что v то уже учтено.
Ну давайте я нарисую картинку.
Вот v, вот из нее выходит какое-то количество ребер,
которое не превосходит s.
Теперь мы смотрим на каждый из вот этих концов,
чтобы понять, сколько вершин находится от v на расстоянии ровно 2.
И смотрим, сколько у них соседей.
Там они могут быть общими.
Нет, общими они не могут быть, потому что это дерево — это очень важно!
Значит, так, ну и тут сколько-то, опять не больше чем s.
Но смотрите: вот в эту степень входит и вот это ребро.
И в эту степень тоже входит вот это ребро.
Поэтому новых ребер, которые отличны от уже посчитанных, их не больше чем (s – 1).
Таким образом, вот эта величина не превосходит (s – 1) × s.
Ну или s × (s – 1), как угодно.
То есть для каждой из вот этих s соседок есть не больше чем (s – 1) новых соседок,
отстоящих от исходной вершины v на расстояние в точности равное 2.
Значит, аналогично на расстоянии 3,
на расстоянии 3 от
v не больше чем (s – 1) в квадрате × s, и так далее.
На расстоянии каком-то там (t – 1), не каком-то там, а (t – 1).
Вот то самое t, которое у нас в условии задачи.
На расстоянии (t – 1) не больше чем (s – 1) в
степени (t – 2), по-видимому, да?
Давайте посмотрим, значит, на расстоянии 2 (s – 1) × s,
на расстоянии 3 — (s – 1) в квадрате × s,
ну а на расстоянии (t – 1) — (s – 1) в степени (t – 2) × s.
Ну, вроде, понятно совершенно.
Да, (s – 1) в степени (t – 2) × s.
То есть
на расстоянии,
которое не превосходит (t –
1) не больше чем сумма полученных количеств вершин.
Ну то есть не больше,
чем s × (1 + (s – 1) + (s – 1) в квадрате +...
+ (s – 1) в (t – 2) степени).
Вот на таком расстоянии, которое не превосходит (t – 1),
не больше чем столько вершин нашего графа.
Это имеется в виду от центральной вершины v.
От середины самой длинной цепочки.
Ну тут у нас стоит сумма
геометрической прогрессии, сумма геометрической прогрессии,
которая ну, очевидно, там, меньше чем s в степени (t – 1),
то есть это меньше заведомо, чем s в степени t.
Это, вроде бы, совершенно понятно: меньше чем s в степени t, конечно.
Так, это, конечно,
меньше чем s в степени t, но у нас всего в нашем дереве s в степени t вершин,
а от вершины v на расстоянии меньше или равное (t – 1)
отстоит строго меньше чем s в степени t вершин.
Да, включая и саму вершину тоже, конечно, с запасом.
Вот. Поэтому получается,
что существуют вершины,
отстоящие от v
на расстояние
не меньшее чем t.
Получается, что существуют вершины в нашем дереве,
которые отстоят от данной вершины v на расстояние не меньше чем t ребер.
Вот давайте нарисуем картину, чтобы было просто понятнее, что происходит.
Еще раз, вот это наша самая длинная цепочка,
«серединой» условной в кавычках которой является вершина v.
Ну, пожалуйста, давайте я нарисую случай, в котором v действительно является
серединой, другой случай, если захотите, вы сами сможете вполне рассмотреть.
Вот. Это «серединка» v.
А, впрочем, это действительно неважно, где она расположена, главное,
что она в середине в кавычках, как мы это определили.
И вот от нее есть цепь условно на расстоянии t.
То есть в этой цепи всего t ребер.
Есть вершина, которая отстоит от вершины v на расстоянии t ребер.
Ну и понятно совершенно, что если бы с какой-то стороны у нас от вот
этой вершины v внутри этой цепи было бы ну,
скажем так: если бы с обеих сторон было меньше чем (t – 1) ребро, тогда у
нас бы получилось просто противоречие с самой длинной вот этой цепью.
В ней бы у нас получилось меньше чем (2t – 2) ребра, а вот в этой цепи плюс
один из вот этих кончиков получилось бы t + (t – 1) ребро,
то есть (2t – 1), и это бы уже противоречило тому,
что наша цепь вот эта вот самая длинная, самая длинная в дереве.
Ну значит, хотя бы с одной стороны не меньше чем t ребер и с
другой стороны не меньше чем (t – 1).
То есть получается, что вот в этой самой длинной цепи,
с которой мы стартовали все рассуждение, в самой длинной цепи,
из которой мы, собственно, выбрали вершину v, в самой длинной цепи не меньше
чем (2t – 1) ребер, а это ровно то, что мы хотели доказать.
Это и есть то, что мы обозначаем p с индексом 2t.
Задача решена.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
