ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 105069
Темы:    [ Обход графов ]
[ Раскраски ]
[ Процессы и операции ]
Сложность: 4+
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Раскраска вершин графа называется правильной, если вершины одного цвета не соединены ребром. Некоторый граф правильно раскрашен в k цветов, причём его нельзя правильно раскрасить в меньшее число цветов. Докажите, что в этом графе существует путь, вдоль которого встречаются вершины всех k цветов ровно по одному разу.


Решение

  Цвета, в которые покрашен граф, занумеруем от 1 до k. Те вершины цвета 2, которые не соседствуют ни с какими вершинами цвета 1, перекрасим в цвет 1. Новая раскраска будет правильной, поэтому в ней k цветов. Значит, какие-то вершины цвета 2 не перекрашены и потому соседствуют с вершинами цвета 1. Аналогично, вершины цвета 3, которые не соседствуют с вершинами цвета 2, перекрасим в цвет 2, и т. д. вплоть до последнего цвета.
  После этого рассмотрим какую-либо вершину цвета k. Она не перекрашена, и потому соседствует с вершиной цвета  k – 1.  Эта вершина тоже не перекрашена, так как иначе её первоначальный цвет был бы k, и она не могла бы соседствовать с вершиной того же цвета. Раз вершина не перекрашена, то она соседствует с вершиной цвета  k – 2,  и т. д. Продолжая этот процесс, построим путь из вершин k цветов, которые не были перекрашены.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 62
Год 1999
вариант
Класс 11
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .