Тема Графы и турниры

Числа Рамсея

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела графы и турниры

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#81779

Докажите, что число Рамсея $r(m,n)≤ Cn−1 . n+m−2$

Показать доказательство

Докажем, что в графе, в котором нет полного подграфа первого цвета на $m$ вершинах и полного подграфа второго цвета на $n$ вершинах, не более $n−1 Cm+n−2− 1$ ребер. Будем вести индукцию по $m+ n.$ Базу проверим для $r(1,n)=r(m,1)= 1.$ Рассмотрим произвольную вершину $v.$ Заметим, что из нее выходит не более $r(m− 1,n)− 1$ ребер первого цвета, так как иначе среди таких вершин можно было бы выбрать либо $Kn$ второго цвета, либо $Km−1$ первого цвета, а затем, добавив к нему $v,$ получить $Km$ первого цвета. Аналогично из $v$ выходит не более $r(m,n− 1)− 1$ ребер второго цвета. Тогда всего вершин не больше, чем

r(m − 1,n)− 1+ r(m,n − 1)− 1+1 =Cnm−+1n−3+ Cnm−+2n−3− 1= Cnm−+1n−2− 1

Таким образом, переход доказан.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#81781

Докажите, что для любого натурального $n$ существует число $N$ такое, что в любом волейбольном однокруговом турнире на $N$ вершинах можно выделить $n$ человек так, чтобы первый обыграл всех остальных, второй — всех, кроме первого, и т. д., последний проиграл всем.

Показать доказательство

Возьмем число Рамсея $N =r(n,n)$ и сопоставим каждому круговому турниру на $N$ вершинах граф. Вершинами этого графа будут люди, пронумерованные числами от $1$ до $N,$ а ребрами — игры, причем ребро между $i$ и $j > i$ мы красим в первый цвет, если $j$ выиграл у $i,$ и во второй цвет в противном случае. Тогда найдется либо полный граф первого цвета, либо полный граф второго цвета. Предположим, что нашелся полный граф на $n$ вершинах первого цвета. Тогда человек с наибольшим номером выиграл у всех остальных, человек со вторым по величине номером выиграл у всех, кроме первого и так далее. То есть мы нашли требуемую конструкцию. Второй случай разбирается аналогично.

Ошибка.
Попробуйте повторить позже

Задача 3#81782

Пусть $T n$ — произвольное дерево на $n$ вершинах. Докажите, что тогда

r(Tn,Kk)≤ (n − 1)(k − 1)+ 1

где $r$ соответствующее число Рамсея.

Показать доказательство

Нам надо показать, что в любом графе на $(n− 1)(k− 1)+1$ вершине, ребра которого покрашены в два цвета можно найти либо $T n$ первого цвета, либо $Kk$ второго цвета. Предположим, что не найдется полного подграфа на $k$ вершинах второго цвета. Выделим максимальный полный подграф второго цвета. Присвоим ему номер $n.$ В ем не больше $k− 1$ вершины по нашему предположению. Заметим, что из каждой из оставшихся вершин в наш подграф ведет хотя бы одно ребро первого цвета (иначе мы бы выбрали не максимальный полный подграф). Далее среди оставшихся вершин снова выберем максимальный полный подграф второго цвета, присвоим ему номер $n − 1$ и так далее. На каждом шаге мы выкидываем не более $k− 1$ вершин, поэтому мы сможем выделить минимум $(n−1)(k−1)+1 k−1$ подграфов, то есть минимум $n$ полных подграфов. Нам буду нужны первые $n$ выбранных подграфов, которые мы занумеровали числами от $n$ до $1.$ Рассмотрим дерево $Tn.$ Подвесим его за вершину. Все вершины дерева разбились на уровни. Вершину, за которую подвесили пронумеруем 1. Далее нумеруем по возрастанию все вершины первого уровня, потом второго и так далее.

Теперь будем строить наше дерево, причем $i$ -ую вершину дерева будем искать в $i$ -ом полном подграфе. На $i$ -ом шаге мы будем добавлять к графу вершину с номером $i+1.$ Изначально выберем любую вершину из первого подграфа. Когда нам нужно добавить вершину с номером $j,$ мы смотрим на номер ее предка. Он имеет меньший номер $k,$ а значит, уже выбран в $k$ -ом подграфе. Но тогда из этой вершины должно вести ребро первого цвета в $j$ -ый подграф, конец этого ребра и будет нашей вершиной с номером $j,$ добавим его в дерево. Таким образом, мы смогли построить $Tn.$

Ошибка.
Попробуйте повторить позже

Задача 4#81783

Теорема Шура. Все натуральные числа покрашены в несколько цветов. Тогда можно выбрать три одноцветных числа $x,y,z,$ для которых $x+ y = z.$

Показать доказательство

Рассмотрим полный граф, вершинами которого являются натуральные числа. Ребро вершинами $a$ и $b$ будем красить в цвет числа $|a − b|.$ Пусть всего цветов $n.$ Рассмотрим первые $r(n,3,3,...,3)$ вершин графа, где $r$ соответствующее число Рамсея. Среди них гарантированно найдется одноцветный треугольник. Тогда числа, соответствующие его ребрам будут покрашены в один цвет в исходной конструкции, а также сумма двух из них будет равна третьему.

Курсы

Всё необходимое для достижения цели

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущий раздел

Следующий раздел