Речь идет о правильной раскраске графа. Хроматическое число графа h - наименьшее число красок, которыми можно раскрасить граф правильно.

Есть ли теорема о нахождении такого пути, который будет содержать по одной вершине каждого цвета? Если нет, то как правильно доказать, что такой путь есть?

задан 4 Янв '17 17:40

10|600 символов нужно символов осталось
2

Это вроде бы чья-то "именная" теорема, и она верна в неком более сильном варианте.

Рассуждение такое. Введём ориентацию рёбер на раскрашенном графе, направляя их от цвета с меньшим номером к цвету с большим номером. Если найдётся путь по стрелкам, имеющий h вершин, то всё доказано (номера цветов при этом идут по порядку). Допустим, что такого пути не нашлось. Тогда для каждой вершины рассмотрим наибольшее число вершин пути по стрелкам с началом в данной вершине. Эта величина принимает значения от 1 до h-1 (если у всех соседей вершины номера цветов меньше данного, то она равна 1). Сопоставим каждой вершине это значение. Оно даёт новую раскраску не более чем в h-1 цвет. Проверим, что она является правильной. Допустим, что у двух соседних в исходном графе вершин v и w новые цвета совпали и оказались равны s. Старый цвет одной из вершин был меньше цвета другой вершины, и можно считать, что из v в w была поставлена стрелка. Тогда можно пойти по стрелке из v в w, а потом пройти из w каким-то путём с s вершинами, всё время увеличивая номера цветов. Это значит, что путь из v длиннее, и этой вершине не мог соответствовать тот же новый цвет, что и для w.

ссылка

отвечен 4 Янв '17 20:18

@falcao Извините, а что следует из этого: Это значит, что путь из v длиннее, и этой вершине не мог соответствовать тот же новый цвет, что и для w ?

(16 Ноя 8:50) gg_math15

@gg_math15: из этого следует противоречие с предположением о том, что новые цвета вершин v и w оказались равными. Тем самым, от противного доказана правильность новой раскраски.

(16 Ноя 14:43) falcao

@falcao извините, вы говорите: Тогда для каждой вершины рассмотрим наибольшее число вершин пути по стрелкам с началом в данной вершине. Эта величина принимает значения от 1 до h-1, а возможно ли, что эта величина принимает и значение 0 ?

(21 Ноя 15:28) gg_math15

@gg_math15: сама вершина тоже считается. Это путь может иметь длину 0, но тогда он состоит из одной вершины.

(2 дня назад) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×574
×305
×34

задан
4 Янв '17 17:40

показан
531 раз

обновлен
2 дня назад

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru