Орграфы Кэли групп

Найдите гамильтонов цикл в ориентированном графе из примера 7, отличный от цикла на рисунке 28.3.

Найдите гамильтонов цикл в

Найдите гамильтонов цикл в

где $m$ чётно.

Запишите последовательность образующих для каждого из циклов, найденных в упражнениях 1, 2 и 3.

Используйте ориентированный граф Кэли из примера 7, чтобы вычислить произведение $a^3ba^{-1}ba^3b^{-1}$.

Пусть $x$ и $y$ --- две вершины ориентированного графа Кэли. Объясните, почему два пути из $x$ в $y$ в этом графе дают групповое соотношение, то есть равенство вида $a_1a_2 \cdots a_m = b_1b_2 \cdots b_n$, где $a_i$ и $b_j$ --- образующие ориентированного графа Кэли.

Используйте ориентированный граф Кэли из примера 7, чтобы проверить соотношение $aba^{-1}b^{-1}a^{-1}b^{-1} = a^2ba^3$.

Определите, какой известной группе соответствует следующий ориентированный граф Кэли.

Пусть $D_4 = \left\langle r, f \mid r^4 = e = f^2, rf = fr^{-1}\right\rangle$. Проверьте, что

является гамильтоновым циклом в

Нарисуйте $\operatorname {Cay}(\left\{ 2, 5\right\} : \mathbb {Z}_8)$.

Если $s_1, s_2, \ldots , s_n$ --- последовательность образующих, задающая гамильтонов цикл, начинающийся в некоторой вершине, объясните, почему та же последовательность задаёт гамильтонов цикл, начинающийся в любой вершине. (На это упражнение ссылаются в данной главе.)

Покажите, что ориентированный граф Кэли из примера 7 имеет гамильтонов путь из $e$ в $a$.

Покажите, что в

нет гамильтонова пути из $(0, 0)$ в $(2, 0)$.

Нарисуйте $\operatorname {Cay}(\left\{ 2, 3\right\} : \mathbb {Z}_6)$. Есть ли в этом ориентированном графе гамильтонов цикл?

Пусть $D_4 = \left\langle a, b \mid a^2 = b^2 = (ab)^4 = e\right\rangle$. Нарисуйте $\operatorname {Cay}(\left\{ a, b\right\} : D_4)$. Почему разумно сказать, что этот ориентированный граф неориентированный?

Пусть $D_n$ определена как в примере 10. Покажите, что $2 * [(n - 1) * r, f]$ является гамильтоновым циклом в $\operatorname {Cay}(\left\{ r, f\right\} : D_n)$.

Пусть $Q_8 = \left\langle a, b \mid a^8 = e, a^4 = b^2, b^{-1}ab = a^{-1}\right\rangle$. Найдите гамильтонов цикл в $\operatorname {Cay}(\left\{ a, b\right\} : Q_8)$.

Пусть $Q_8$ определена как в упражнении 18. Найдите гамильтонов цикл в

Докажите, что ориентированный граф Кэли из примера 6 не имеет гамильтонова цикла. Имеет ли он гамильтонов путь?

Найдите гамильтонов цикл в

Обобщается ли этот цикл на случай $D_{n+1} \oplus \mathbb {Z}_n$ для всех $n \ge 3$?

Пусть $Q_8$ определена как в упражнении 18. Найдите гамильтонов цикл в

Пусть $Q_4$ определена как в примере 7. Найдите гамильтонов цикл в

Пусть $Q_4$ определена как в примере 7. Найдите гамильтонов цикл в

Запишите последовательность образующих, которая описывает гамильтонов цикл из примера 9.

Пусть $D_n$ определена как в примере 10. Найдите гамильтонов цикл в

Обобщается ли ваш цикл на случай $D_n \oplus \mathbb {Z}_{n+1}$ для всех $n \ge 4$?

Докажите, что $\operatorname {Cay}(\left\{ (0, 1), (1, 1)\right\} : \mathbb {Z}_m \oplus \mathbb {Z}_n)$ имеет гамильтонов цикл для всех $m$ и $n$, больших 1.

Предположим, что существует гамильтонов цикл для $\operatorname {Cay}(\left\{ (1, 0), (0, 1)\right\} : \mathbb {Z}_m \oplus \mathbb {Z}_n)$ и что этот цикл выходит из вершины $(a, b)$ по вертикали. Покажите, что цикл выходит по вертикали из каждого элемента смежного класса $(a, b) + \left\langle (1, -1)\right\rangle$.

Пусть $D_2 = \left\langle r, f \mid r^2 = f^2 = e, rf = fr^{-1}\right\rangle$. Найдите гамильтонов цикл в $\operatorname {Cay}(\left\{ (r, 0), (f, 0), (e, 1)\right\} : D_2 \oplus \mathbb {Z}_3)$.

Пусть $Q_8$ определена как в упражнении 18. Найдите гамильтонов цикл в $\operatorname {Cay}(\left\{ (a, 0), (b, 0), (e, 1)\right\} : Q_8 \oplus \mathbb {Z}_3)$.

В $\operatorname {Cay}(\left\{ (1, 0), (0, 1)\right\} : \mathbb {Z}_4 \oplus \mathbb {Z}_5)$ найдите последовательность образующих, которая посещает ровно одну вершину дважды, а все остальные ровно один раз и возвращается в начальную вершину.

В $\operatorname {Cay}(\left\{ (1, 0), (0, 1)\right\} : \mathbb {Z}_4 \oplus \mathbb {Z}_5)$ найдите последовательность образующих, которая посещает ровно две вершины дважды, а все остальные ровно один раз и возвращается в начальную вершину.

Найдите гамильтонов цикл в $\operatorname {Cay}(\left\{ (1, 0), (0, 1)\right\} : \mathbb {Z}_4 \oplus \mathbb {Z}_6)$.

Пусть $G$ --- ориентированный граф, полученный из $\operatorname {Cay}(\left\{ (1, 0), (0, 1)\right\} : \mathbb {Z}_3 \oplus \mathbb {Z}_5)$ удалением вершины $(0, 0)$. Докажите, что $G$ имеет гамильтонов цикл.

Докажите, что ориентированный граф, полученный из $\operatorname {Cay}(\left\{ (1, 0), (0, 1)\right\} : \mathbb {Z}_4 \oplus \mathbb {Z}_7)$ удалением вершины $(0, 0)$, имеет гамильтонов цикл.

Пусть $G$ --- конечная группа, порождённая $a$ и $b$. Пусть $s_1, s_2, \ldots , s_n$ --- дуги гамильтонова цикла в ориентированном графе $\operatorname {Cay}(\left\{ a, b\right\} : G)$. Говорят, что вершина $s_1s_2 \cdots s_i$ проходит по $a$, если $s_{i+1} = a$. Покажите, что если вершина $x$ проходит по $a$, то каждая вершина смежного класса $x \left\langle ab^{-1}\right\rangle$ проходит по $a$.

Конечная группа называется гамильтоновой, если все её подгруппы нормальны. (Одним из неабелевых примеров является $Q_4$.) Покажите, что теорему 28.3 можно обобщить на все гамильтоновы группы.