Так, друзья, давайте позанимаемся теорией Рамсея.
На лекциях у нас уже было достаточно много весьма нетривиальных и забавных
утверждений.
Сейчас мы попробуем на примерах различных задач понять,
как еще могут быть устроены рамсеевские результаты, рамсеевские соображения.
Давайте обозначим буквой T произвольное конкретное дерево на 5 вершинах.
Произвольное дерево на 5 вершинах.
И введем по аналогии с обычным числом Рамсея
такую вот величину, обозначим ее R (T, K4).
Ну вот, что такое обычное число Рамсея?
Все помнят, конечно, определение.
Какое-нибудь там R (S, T), да?
Это минимальное количество вершин, такое, что для любого
графа с таким количеством вершин либо в нем есть копия полного графа KS,
либо в его дополнении, то есть мы все его ребра стерли,
а все, которых не было, провели, вот в его дополнении есть копия графа KT.
Ну вот здесь вместо KS мы рассматриваем дерево T.
А вместо KT рассматриваем K4.
Давайте так и напишем.
Это есть по определению минимальное натуральное число N,
такое, что для любого G = (V,
E), у которого мощность V = n,
то есть для любого графа на n вершинах.
Либо в G есть дерево
T, либо в G с чертой есть полный граф на 4 вершинах.
Ну, это то же самое, конечно, либо в G в самом
есть независимое множество,
независимое множество на 4-х вершинах.
Давайте еще раз.
Либо в самом графе есть копия дерева T,
либо в его дополнении есть копия полного графа K4.
Но в его дополнении есть копия полного графа K4, это то же самое,
что в нем самом есть независимое множество на 4-х вершинах.
Я думаю, что это понятно.
Вот минимальное количество вершин, которые гарантируют, что какой бы граф мы не
взяли, в нем есть либо это дерево, либо четырехвершинное независимое множество,
минимальное такое n и обозначает наше нынешнее R (T, K4).
Вот интересно, чему это равняется.
Значит задача состоит в том, чтобы доказать, что R (T,
K4) = 13.
Ну, действительно, давайте, во-первых, докажем, что R (T,
K4) больше, либо равняется 13.
Для того чтобы это обосновать, нужно просто привести
пример такого графа на 12 вершинах, в котором нету ни дерева T,
ни независимого множества на 4-х вершинах.
Если мы такой пример приведем,
тогда минимальное n с вот этой альтернативой уж точно не меньше, чем 13,
раз на 12 вершинах бывает гнусный граф, который ни того,
ни другого не содержит, ни T, ни независимого множества на 4-х вершинах.
Ну пример очень простой.
Давайте рассмотрим три копии графа K4,
три копии графа K4, между которыми никаких ребер нету.
То есть вот здесь вот полный граф на 4-х вершинах,
здесь полный граф на 4 вершинах, и здесь полный граф на 4 вершинах,
и вот это все вместе — некоторый граф с 3 компонентами связности,
каждый из которых является полным графом на 4-х вершинах.
У него, естественно, 12 вершин и у него число
независимости, конечно, не превосходит 3.
Ну это как турановский результат.
Помните?
Ну, это в общем совершенно понятно.
Из каждого полного графа на 4-х вершинах мы больше одной вершинки-то в независимое
множество все равно взять не сможем.
Как только мы берем 2, там сразу возникает ребро,
поэтому число независимости этого графа заведомо не превосходит 3.
Ну и стало быть, смотрите, может в нем возникнуть дерево на 5 вершинах?
Нет, конечно.
Потому что это граф на 4 вершинах, это граф на 4 вершинах,
и это граф на 4 вершинах.
Дерево на 5 вершинах никак не возникнет.
Дерево на 5 вершинах — это связный граф.
Ему взяться неоткуда.
Значит дерева на 5 вершинах там нет, а α (G) не превосходит 3, это значит,
что независимого множества на 4 вершинах в этом замечательном примере тоже нет.
То есть пример очень простой, очень простой.
Но вот теперь нам предстоит доказать,
что R (T, K4) точно не превосходит 13,
то есть теперь мы берем произвольный граф на 13 вершинах,
произвольный абсолютно, и пытаемся доказать, что либо в нем найдется копия
нашего конкретного дерева, либо уж если этого не случится,
то точно найдется независимое множество на 4-х вершинах.
Ну, давайте рассуждать более или менее в стандартном духе.
Вот у нас G.
Вот у него 13 вершин.
Давайте предположим для начала,
предположим, что
для любой вершины нашего графа,
который мы зафиксировали, для любой его вершины степень
больше либо равняется 4.
Помните, как мы с вами когда-то очень давно, еще там в первом семинаре,
наверное, разбирали такую задачку.
Если степень каждой вершины графа, ну или там минимальная степень
вершины графа не меньше n или равняется n, где n больше,
либо равно 1, тогда этот граф точно содержит цепь с не менее,
чем n ребрами, ну и, соответственно, с менее чем n + 1 вершиной.
Смотрите, здесь мы знаем, что минимальная степень не меньше 4.
Но, значит, мы можем гарантировать,
что в таком графе поймается цепь, содержащая, как минимум 5 вершин.
Но если вы вспомните то рассуждение, с помощью которого мы доказали,
что поймается цепь, содержащая не менее 5 вершин,
а оно было совершенно элементарным, мы просто брали произвольную вершину,
выводили из нее какое-то ребро, удаляли эту вершину вместе со всеми смежными
ребрами, смотрели на оставшиеся вершины, замечали, что у них там степень уже,
соответственно, не меньше, чем n − 1 и дальше продолжали эту процедуру.
Так вот, если вы посмотрите на это рассуждение, то вы поймете,
что не только цепь на 5 вершинах, но и любое дерево на 5 вершинах эта процедура
нам обеспечивает, любое дерево на 5 вершинах.
То есть, если мы предполагаем,
что у каждой вершины нашего графа степень не меньше 4-х, то не только дерево,
представляющее собою цепь на 5 вершинах, но и наше конкретное дерево T,
которое сейчас у нас зафиксировано, мы тоже можем гарантировать в нашем графе.
То есть в этом случае за счет идей очень простых,
которые я сейчас произнес заново, изложенных еще в первом семинаре,
в этом случае мы гарантируем наличие T,
дерева T в нашем графе.
И все замечательно.
Наличие дерева T в нашем графе.
И все, конечно, совершенно замечательно, вы в героях.
Ну ладно, давайте предположим, что нам не повезло.
Пусть наоборот.
Пусть, наоборот,
существует такая вершина из множества вершин нашего графа, которая,
к несчастью, имеет маленькую степень, то есть степень, не превосходящую 3.
Тогда у нас нет ресурса для того,
чтобы гарантировать наличие дерева T в нашем графе.
Но у нас же есть альтернатива.
Мы можем попытаться в этом случае попробовать поискать независимое
множество на 4-х вершинах.
Ну, сразу-то мы его не найдем.
Вот давайте предположим, что есть вершина степени не больше, чем 3.
Вот какая-то эта вершина, V.
У нее степень не больше 3.
Но я нарисую, как будто бы она равняется 3, а так это в общем не очень важно.
Давайте удалим эту вершину из нашего графа вместе со всеми ребрами,
которые из нее выходят.
Сколько вершин таким образом удалится?
Давайте напишем.
Удалим V вместе со всеми смежными ребрами из исходного графа G.
Удалится, понятное дело, не больше 4-х вершин.
То есть останется граф с не менее чем 9 вершинами.
Не забывайте, что исходный граф по условию имеет 13 вершин.
Значит, вот если мы удаляем вершину с вот такой маленькой степенью и все выходящие
из нее ребра, тогда мы получаем на выходе граф, у которого не менее 9 вершин.
Дальше мы можем снова рассмотреть такую же точно альтернативу.
Давайте граф обозначим как-нибудь, G'.
И я еще раз для него произведу эту альтернативу,
чтобы было совершенно понятно.
Значит альтернатива такая.
Предположим, существует какая-то W из V (G') Ой, почему же существует.
Предположим, для любой W (извините, конечно, так же точно,
как было до сих пор).
Так вот, предположим, для любой W из V (G') deg W ≥ 4.
Ну, в этом случае, я вот так вот напишу, в этом случае (только
здесь G' надо писать) мы гарантируем наличие дерева T, но уже в графе G'.
Поэтому, если мы все время пытаемся избежать наличия T,
как-то вот привести к противоречию то, что у нас должно было получиться,
обмануть самих себя, то мы, конечно,
должны опять предполагать, что существует W из V (G'),
у которой снова степень не превосходит 3.
Ну и проделаем с ней ту же самую процедуру, которая вот здесь.
То есть вот она — W, из нее выходят 3 ребра или там меньше,
удалим W из G', удалим W из G'.
Останется какой-то там граф G'', если хотите,
G'' с не менее чем 5 вершинами.
Понятно, да?
То есть мы уже удалили,
то есть либо мы нашли дерево T в нашем графе, либо мы удалили вершину.
Либо снова нашли дерево T, и тогда мы в героях,
либо опять удалили вершину, но даже после того, как мы удалили 2 вершины,
у нас остался граф, который имеет не менее 5 вершин.
И следующая альтернатива точно такая же.
Ну, либо мы заловим дерево, либо мы еще раз покоцаем граф,
останется 1 вершина как минимум.
И вот смотрите, мы удаляем еще какую-то X.
То есть V, W, X.
После удаления X остается хотя бы 1 вершина.
Берем вот эту вершину, называем ее Y,
и либо на каком-то из шагов до удаления у нас образовалось дерево T и тогда все
замечательно, либо в конце концов мы набрали 4 вершины, V, W, X и Y.
И они по построению ребрами в исходном графе не соединены.
Потому что когда мы брали V, мы ведь удаляли всю ее окрестность.
W не могла в ней находиться.
W — это вершина несмежная с вершиной V.
И точно так же X заведомо несмежна ни с V, ни с W.
И, наконец, Y несмежна ни с X, ни с W, ни с V.
То есть если на каком-то этапе мы не изловили дерево,
то в конце концов мы заловим 4 вершины, которые попарно несмежны,
то есть, товарищи, образуют независимое множество на 4-х вершинах.
И задача полностью решена.