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

Предыдущий
вопрос Следующий
вопрос

Для начала заметим, что так как из каждой вершины выходит только одно ребро, то весь граф можно представить как набор циклов. При этом наименьшее количество вершин в цикле равно 3.

Давайте посмотрим на случай, когда k=4. Рассмотрим ориентированный цикл из 4 вершин. Ясно, что минимальный путь между любыми двумя вершинами одного цвета будет содержать не менее 3 ребер (так как весь путь состоит из 4 вершин). Получается, что при k=4 нельзя добиться условия из задачи.

Теперь рассмотрим случай k=5. Возьмем ориентированный цикл из 5 вершин. Минимальный путь между любыми двумя вершинами одного цвета будет содержать не менее 5 ребер (так как весь путь состоит из 5 вершин). Таким образом, при k=5 условие из задачи выполняется.

Итак, наименьшее возможное k равно 5.