Так, товарищи, ну давайте разберем последнюю задачу на графового Рамсея.
Давайте рассмотрим произвольные числа 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.
Задача решена.