2 Транспозиционный граф кэли

В [4] были показаны следующие свойства транспозиционного графа Кэли

S_n (T ).

n

Утверждение 1. Транспозиционный граф Кэли S_n (T ), n ≥ 3, является связным двудольным, C ² -регулярным, порядка n!, диаметра (n − 1).

Действительно, порядок графа совпадает с мощностью симметрической группы, равной n!. Расстояние в этом графе определяется как наименьшее число транспозиций, переводящих одну перестановку в другую. Диаметр графа равен (n − 1), так как любой цикл длины k может быть разложен в

^{произведение не менее (k − 1) транспозиции. Граф является двудольным,}

^{поскольку любое его ребро соединяет четную и нечетную перестановки.}

Отсюда следует следующая теорема.

Теорема 1. χ(S_n (T )) = 2, n ≥ 3.

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

Теорема 2. Хроматическое число χ(S_n (T^˜)) = 2, где T^˜ произвольное по- рождающее множество симметрической группы, состоящие из транс- позиций.

Примерами таких графов могут служить широко используемые в ино- странной литературе [4] bubble-sort graph S_n (T_b ), где T_b = {t_ii+1 ∈ S_n , 1 ≤ i < n}, а также star graph S_n (T_s ), где T_s = {t_1i ∈ S_n , 1 < i ≤ n}. Данные графы используются для представления компьютерных сетей.

3 ПРЕФИКС-РЕВЕРСАЛЬНЫЙ ГРАФ И ЕГО СВОЙСТВА

Рассмотрим общие свойства префикс-реверсального графа Кэли S_n (P R).

Обхватом называется наименьшая длина цикла в графе.

Утверждение 2. Граф Кэли S_n (P R), n ≥ 3 является связным, (n − 1)- регулярным графом порядка n!, с обхватом g(S_n (P R)) = 6.

Хроматическое число данного графа неизвестно. Из теоремы Брукса сле- дует тривиальная верхняя оценка:

χ(S_n (P R)) ≤ (n − 1) (3.1)

3.1 Иерархическая структура Sn (p r)

Известно, что S_n (P R) имеет иерархическую структуру, которая может быть представлена следующим образом. Для любого n ≥ 3 граф S_n (P R),

2

содержащий n! вершин и ^(n−1)n!

ребер, может быть получен на основе n

^{копий графа S}_n−1^{(P R). Между любыми двумя копиями S}_n−1^{(P R) имеется}

_n!

^{(n−2)! ребер, а между всеми копиями Sn−1(P R) имеем ровно}

₂ ^{ребер. Воз-}

^{можность иерархического построения данных графов следует из свойств}

порождающего множества.

2

Рассмотрим простейший случай S₂ (P R). Граф имеет две вершины, од- но ребро. Совпадает с K₂. При n = 3 имеем S₃(P R) = C₆, где C₆ представ- лен последовательностью реверсалов r₁ и r₂. |V | = 3! = 6, |E| = ^{2· 3!} = 6. Для построения графа S₄(P R) нужно три префикс-реверсала r₁, r₂ и r₃. Два первых префикс-реверсала r₁ и r₂ определяют на множестве всех 4! перестановок четыре непересекающихся по вершинам и ребрам цикла дли-

ны шесть C₆, а префикс-реверсал r₃ определяет связи между ними. Между любыми двумя копиями C₆ в S₄(P R) имеется ровно 2 ребра, а между все- ми копиями C₆ ровно 12 ребер как показано на рис. 3.1.

^{В общем случае, для любого n ≥ 3 в графе S}n ^{(P R) префикс-реверсал r}n−1

^{определяет связи между n копиями графов S}_n−1^{(P R), каждая из которых}

^{порождается (n − 2) префикс-реверсалами.}

₃₂₁₄

1234

_{✟ ✟❍ ❍}

r₃

₂₁₃₄

₃₄₂₁

4321

_{✟ ✟❍ ❍}

₂₃₄₁

₁₂₃

^r₂ ^r₁

r₁ r₂

_{r2 r1}

^r₁ ^r₂

r₂ r₁

_{r1 r2}

_✟❍

321 ^{✟ ❍} 213

₂₃₁₄

_{❍ ❍✟ ✟}

_{3124 r3}

_{2431 ❍}

_{✟✟ 3241}

^{r2 r1}

r₁ r₂

_{r2 r1}

1324

^r₃ ^r₃

❍✟

4231

^{231 ❍} _❍✟ ^{✟ 312}

132

r₃ r₃ r₃ r₃

_{S3(P R) = C6}

3142

^r₃ ^r₃

2413

₄₁₃₂

_{✟ ✟❍ ❍}

_{1342 r3}

₄₂₁₃

_{✟ ✟❍ ❍}

₁₄₂₃

^r₂ ^r₁

r₁ r₂

_{r2 r1}

^r₁ ^r₂

r₂ r₁

_{r1 r2}

1432

^❍ _❍✟ ^✟

₃₄₁₂

4312

r₃

1243

^❍ _❍✟ ^✟

₂₁₄₃

4123

Рис. 3.1. Иерархическое строение S₄(P R)