В дереве 100 вершин. Сколькими способами можно раскрасить его вершины в а) 2 б) 3 цвета так, чтобы соседние вершины всегда были разного цвета?

задан 5 Фев '18 16:28

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

Пусть число вершин дерева равно n, а число цветов равно k. Зафиксируем одну из вершин дерева, нарисовав его как корневое, где рёбра от корня идут вниз. Корень дерева можно раскрасить в любой из k цветов. Соседние с ним вершины (на расстоянии 1 от корня) -- в k-1 цвет любую из них (кроме цвета корня). Вершины уровня 2 (на расстоянии 2 от корня) можно также раскрашивать в любой из k-1 цветов (кроме цвета той единственной вершины уровня 1, с которой соседствует данная). И так далее. В итоге получаем хроматический многочлен дерева, равный k(k-1)^{n-1}. Можно подставлять любые значения k. При k=2 будет два способа. При k=3 получится 3*2^{99}.

ссылка

отвечен 5 Фев '18 17:35

Спасибо! =)

(5 Фев '18 22:09) make78
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×548

задан
5 Фев '18 16:28

показан
284 раза

обновлен
5 Фев '18 22:09

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

по почте:

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

по RSS:

Ответы

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

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