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

задан 20 Янв '16 21:19

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

Здесь не сказано, что $%n$% -- это число вершин, но я так понимаю, что это подразумевалось.

В такой формулировке раскраска не всегда возможна: легко привести контрпример. А именно, рассмотрим полный граф на 4 вершинах, и ещё одну дополнительную вершину, которая ни с чем не соединена. При этом $%n=5$%, $%k=3$% нечётны, но раскраска в три цвета невозможна. Чтобы рассуждение проходило, граф надо считать связным.

При этом дополнительном предположении мы сначала заключаем, что граф не является регулярным степени $%k$%. Если бы имела место эта ситуация, то число рёбер было бы равно $%nk/2$%, но есть оно не целое (лемма о рукопожатиях). Далее индукцией по числу вершин, без предположений о нечётности, доказываем, что если граф связен, и степени всех его вершин не больше $%k$%, и при этом имеется вершина степени $%< k$%, то граф $%k$%-раскрашиваем.

База индукции очевидна. Шаг: берём вершину $%v$% степени $%< k$% и временно удаляем её вместе со всеми исходящими рёбрами. При этом может возникнуть не связный граф. Однако в каждой связной компоненте имеется вершина, которая в предыдущем графе была соединена с $%v$%. Поэтому её степень в подграфе будет строго меньше $%k$%. Тогда все связные компоненты по предположению индукции будут $%k$%-раскрашиваемы. После этого добавляем $%v$%, и подбираем для неё цвет. Она соединена менее чем с $%k$% уже раскрашенными вершинами, и тогда какой-то из $%k$% цветов не задействован. В него и раскрасим $%v$%.

ссылка

отвечен 20 Янв '16 21:53

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×151
×81

задан
20 Янв '16 21:19

показан
437 раз

обновлен
20 Янв '16 22:11

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

по почте:

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

по RSS:

Ответы

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

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