Задача про графы: вершины покрашены в k цветов, сущ. ли путь

[Snef]

Помогите, пожалуйста, ответить на вопрос.

Дано дерево из $n$ вершин, которые покрашены в $k$ цветов.
Никакие две смежные вершины не покрашены в один цвет.

Существует ли путь длины $k$ из корня дерева,
с вершинами покрашенными в разные цвета?

Можно ли свести эту задачу к задаче поиска гамильтонова пути
в графе с $k$ вершинами ?

[cyb12]

Рассмотрите граф, множество вершин которого есть множество всех цветов графа, а ребро проводится между двумя цветами тогда и только тогда, когда в дереве есть ребро между некоторыми вершинами, окрашенными в эти цвета. В графе есть гамильтонов путь (из вершины-цвета, в который окрашен корень дерева) $\Leftrightarrow$ в дереве есть путь с указанным свойством.

Для получения самого пути нужно рассматривать граф с кратными рёбрами, соответствующими рёбрам исходного дерева.

А почему бы не решать эту задачу каким-нибудь обходом?

[Snef]

Огромное спасибо!
Как я понял, такое дерево можно быстро преобразовать в граф для поиска гамильтонова пути.
А можно ли быстро сделать обратную операцию ?

Обход это полный перебор всех возможных путей в дереве ?

[cyb12]

Под обходом я имел в виду поиск в глубину например.

Что вы имеете в виду под обратной операцией?

[Snef]

Извините за мою безграмотность если что.

Под обратной задачей я понимал превращение графа с $k$ вершинами в дерево с $n$ вершинами, такое, что если к этому дереву применить преобразования как Вы написали выше, получится исходный граф.

Для решения задачи нахождения пути в дереве с заданным условием (длина $k$ и все вершины разного цвета) поиск в глубину будет экспоненциальным или полиномиальным ?

[cyb12]

Ну конечно полиномиальным.

Обратная операция невозможна. Так как одному графу может соответствовать несколько деревьев

[Snef]

Т. е. можно написать обычный поиск в глубину и при каждом заходе в непокрашенную вершину в массиве предков проверять цвета у предыдущих вершин в пути ?
Таким образом путь найдется в худшем за $ (n+n^2) \cdot n$ операций, где $n$ число вершин в дереве ?

Мне кажется что это неверный алгоритм... может надо как то по-другому ?

[cyb12]

Не надо проверять у всех предыдущих. Можно, например, завести стек, в котором хранить цвета вершин в текущем пути.

[Snef]

А, точно, сразу до меня не дошло, что можно все цвета не проверять. Спасибо!
Наверно можно вместо стека завести массив размером в количество цветов, в который на $i$-ое место ставим $1$ если идем через вершину с цветом $ i$ и ставим $0$ если рекурсия возвращается назад ?

Если можно еще вопрос по этой задаче (думаю над ней весь день уже)

1) Если каждая $i $-ая вершина покрашена не в $1$ цвет, а в $a_i$ цветов (всего цветов $k$), и необходимо найти путь в дереве длиной $d$, такой, что все цвета из вершин этого пути разные. Можно ли это сделать аналогично предыдущей задаче, так же поиском в глубину например ?