162
правки
Изменения
м
Нет описания правки
для <tex>0 \leqslant i \leqslant n</tex>. Для всех уровней выполняется соотношение <tex>|V_n(i)| = C_n^i</tex>.
Пусть <tex>Q_n(i)</tex> подграф <tex>Q_n</tex>, который является обединением объединением двух смежных уровней, т. е. <tex>V_n(i) \cup V_n(i+1)</tex>, и пусть <tex>E_n(i)</tex> множество граней <tex>Q_n(i)</tex>.
Тогда монотонным кодом Грея будет являтся [[:Гамильтоновы_графы|Гамильтонов путь]] в <tex>Q_n</tex>, при котором любое множество вершин <tex>\delta_1 , \delta_2</tex> такие, что <tex>\forall i, j : i \leqslant j</tex>, то <tex>\delta_1 \in E_n(i)</tex> идет перед <tex>\delta_2 \in E_n(j)</tex>.
Ниже на катринке Гамильтонов путь в гиперкубе <tex>Q_4</tex> для <tex>n = 4</tex>, построенный по алгоритму Саважа-Винклера (англ. ''Savage-Winkler'').<ref>[http://www.sciencedirect.com/science/article/pii/0097316595900918 C. D Savage and P. Winkler (1995). "Monotone Gray codes and the middle levels problem"page 14]</ref>
[[Файл:Monotonic_Gray_Code_Graph.png|center|4-ичный монотооный монотонный код Грея]]
Элегантная идея построения <tex>n</tex>-ичного монотонного кода Грея состоит в том, чтобы рекурсивно строить подпути <tex>P_{n,j}</tex> длинны <tex>2 \binom{n}{2C_n^j}</tex> включающих вершины <tex>E_n(j)</tex>.
Определим <tex>P_{1,0} = (0, 1)</tex> и <tex>P_{n,j} = \emptyset</tex>, когда <tex>j < 0</tex> или <tex>j \geq geqslant n</tex> и
<tex>
P_{n+1,j} = 1P^{\pi_n}_{n,j-1}, 0P_{n,j}
</tex>. То есть P_{n+1, j} это объединение множеств P^{\pi_n}_{n,j-1} с приписанной в начале 1 и P_{n,j} с приписанными в начале нулем.
Здесь <tex>\pi_n</tex> это определенная перестановка элементов множества к которому она применена, а <tex>P^{\pi}</tex> это путь <tex>P</tex> к котрому была применена пересатновка <tex>\pi</tex>.
Существует два варианта построить моготонный монотонный код грея по путям <tex>P_{n, j}</tex>.
Назовем их <tex>G_n^{(1)}</tex> и <tex>G_n^{(2)}</tex>. Будем строить их таким образом:
