Решение задачи на Графы

Помогите пожалуйста с задачей на графы. Ответ на матоле не особо понятен мне. Могли бы вы дать ответ с пояснениями, и указать примерную тактику решения таких задач?

Видимо, объяснить последовательность мыслей не получится. Объясню подробнее решение на матоле. Основой идеей является использование другого графа для раскраски. Можно убрать степень двойки и немного упростить решение.

Утверждение 1. Ребра полного графа на 2019 вершинах можно раскрасить в 11 цветов так, чтобы граф с ребрами любого цвета были двудольным.

Доказательство. Разделим граф на две доли (1009 и 1010 вершин). Покрасим ребра между долями в первый цвет. Тогда надо доказать верность утверждения для 1010 вершин и 10 цветов. Проводя ту же операцию, уменьшаем задачу (505, 253, 127 вершин…), и в конце остаются 2 вершины, ребро между которыми можно покрасить в 11-ый цвет. Так как ребра разных долей не влияют друг на друга, мы можем раскрасить все ребра в 11 цветов.

Утверждение 2. Вершины нашего графа с 2018 ребрами можно раскрасить в 2019 цветов правильным образом (так, чтобы вершины одного цвета не были соединены ребром).

Докажем для n вершин и n+1 цветов по индукции. База легко проверяется.
Переход: Уберем любую вершину ненулевой степени (степень \le n) вместе со всеми ребрами, которые из нее исходят. Тогда оставшийся граф (максимум n-1 ребер) можно будет раскрасить в n цветов по предположению индукции. Добавляем удаленную вершину и красим в новый n+1-ый цвет.

Пронумеруем 2019 цветов вершин нашего графа числами от 1 до 2019. Так же пронумеруем 2019 вершин полного графа G из утверждения 1, ребра которого покрашены в 11 цветов.

То есть в нашем графе вершины 2019 цветов, а в графе G 2019 вершин. Здесь и соединение.

Покрасим ребра нашего графа, которые соединяют вершины, покрашенные цветом i и j, таким цветом, каким соединены вершины под номером i и j в графе G.

Утверждение 3. Такая раскраска удовлетворяет условию.

i \ne j, так как вершины нашего графа мы красили правильным образом.
Рассмотрим граф из ребер какого-то определенного цвета в нашем графе. Возьмем какой-то цикл A и поймем, почему он не может быть нечетным.

Нарисуем отдельно ребра того же цвета графа G. Тут есть две доли, и каждая вершина как-то пронумерована. Каждое ребро цикла A можно положить на место ребра между долями G.
То есть, цикл A можно сложить в цикл графа G на ребрах того же цвета (можно проходиться ребру несколько раз). Поэтому, утверждение выполняется.

7 симпатий

Спасибо вам Дильназ, вы мне очень помогли! Я ценю ваш труд, и благодарен за то время, что вы уделили мне!

1 симпатия

Интересная задача. Ответьте пожалуйста, почему изначально мы берём 2018/2 вершин, если в условие говорится про 2018 рёбер, как это может быть связано?
Почему мы сравниваем 2018 с 2^11? Откуда берётся 2^11 или как нужно додуматься до этого? Ответьте пожалуйста, если вас это не затруднит.

1 симпатия

Спасибо, сейчас исправлю
Предложение о 2018<2^{11} можно убрать на самом деле. Просто раз уж мы делим число 2018 на 2 несколько раз, можно и сравнить его с какой-нибудь степенью двойки

2 симпатии

А что насчёт моего первого вопроса?

Исправила, спасибо большое!
Показалось, что леммы, доказанной в решении на матоле, достаточно для доказательства

2 симпатии

Дильназ, большой рахмет! Видно что вы отдаете много сил и времени этому делу, за что я вам очень благодарен! Желаю вам всего самого хорошего!

3 симпатии