$n$-дольный граф, образованный $\{0,1,2, \dots, n-1\}^k$
Есть много вопросов о том, как график $Q_k$и он также известен как k-куб, и он двудольный. Где$Q_k$ чьи вершины помечены строками длины $k$ над $\{0, 1\}$. Между вершинами есть ребро, если маркирующие их строки отличаются ровно в одном месте.
Что бы изменилось, если бы этот график $Q_k$ и он был сформирован $n$-арочные струны длины $k$. И между вершинами есть ребро, если строки, обозначающие их, отличаются ровно в одном месте. Каким будет такой график$n$-частный?
Ответы
Думаю, следующая раскраска доказывает, что $3$ цвета достаточно (т.е. такой граф трехчастный): дана строка $s \in \{0, 1, 2 \}^k$ обозначим через $f(s)$ сумма цифр $s$. Мы определяем нашу раскраску как функцию$C$ который отображает $s$ к сумме цифр по модулю $3$, т.е. $C : s \rightarrow \mathcal{R}_3(f(s))$.
Рассмотрим любые две соседние строки $s$ и $s'$. Они отличаются ровно в одной позиции. Без ограничения общности имеем$f(s) < f(s') < f(s) + 3$. Следовательно$\mathcal{R}_3(f(s)) \neq \mathcal{R}_3(f(s'))$ и поэтому $s$ и $s'$должны быть окрашены по-другому. Это доказывает, что$C$ это правильная раскраска.
Обратите внимание, что есть общий основной аргумент: для $l$-арочные строки вы можете доказать, что их можно раскрасить, используя $l$ цвета точно так же.