Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3.1. Группы цепей графа

Гиперкуб, образованный из 72-х цепей куба

Рис. 3.7

Большой 72-цикл симметрично укладывается на грани и ребра гиперкуба Г₇₂, развертка которого приведена на рис. 3.7, при этом каждая цепь связана с четырьмя другими отношением инверсии хвоста или головы. Два 9-цикла отвечают узлам, расположенным вблизи диаметрально противоположных вершин гиперкуба Г₇₂, обозначенными через a:

{1 – 2 – 3 – 52 – 53 – 54 – 55 – 62 – 72},

{47 – 16 – 15 – 20 – 19 – 33 – 32 – 37 – 42}.

Привязке h куба Г₈ соответствуют те же самые вершины Г₇₂, а узлы двух 9-циклов частично перекрываются с двумя предыдущими циклами:

{16 – 17 – 18 – 19 – 26 – 36 – 37 – 38 – 39},

{1 – 6 – 11 – 52 – 51 – 56 – 55 – 69 – 68}.

На рис. 3.7, помимо вершин a-h, помечены также вершины b-g, c-e и d-f, вблизи которых располагаются еще двенадцать 9-циклов, дважды покрывающие все узлы гиперкуба Г₇₂.

На гранях Г₇₂ можно выделить шесть 8-циклов:

{2 – 3 – 8 – 9 – 5 – 6 – 11 – 12},

{14 – 15 – 20 – 21 – 17 – 18 – 23 – 24},

{26 – 27 – 32 – 33 – 29 – 30 – 35 – 36},

{44 – 45 – 41 – 42 – 47 – 48 – 38 – 39},

{53 – 54 – 59 – 60 – 50 – 51 – 56 – 57},

{65 – 66 – 71 – 72 – 62 – 63 – 68 – 69}.

Распишем первый из них конкретно через цепи:

– 1698CB5 – 25BC896 – 98CB521 – 6125BC8 –

– CB52169 – 896125B – 521698C – BC89612 – .

Как видим, 8-цикл связан отношением инверсии только шести головных или хвостовых ребер. Переходы 2 – 5 = 82 и 8 – 11 = B6 сопровождаются заменой одного-единственного ребра. Однореберные замены характерны и для всех остальных переходов между узлами грани A гиперкуба Г₇₂:

3 – 5 = 81, 12 – 5 = 85, 3 – 11 = B1,

9 – 11 = B9, 9 – 2 = 29, 6 – 2 = 2C,

12 – 8 = 65, 6 – 8 = 6C, 3 – 6 = C1,

9 – 12 = 59, 3 – 9 = 91, 3 – 12 = 51,

6 – 9 = 9C, 6 – 12 = 5C, 2 – 8 = 62,

2 – 11 = B2, 5 – 8 = 68, 5 – 11 = B8.

С учетом этого связи грани A могли бы выглядеть иначе (рис. 3.8). Та же самая картина наблюдается на других гранях гиперкуба Г₇₂. Благодаря этому возможны пяти- и семизвенные циклы, например: {2 – 3 – 9 – 6 – 12} или {2 – 3 – 8 – 9 – 6 – 12}, что кажется странным, поскольку числа 5 и 7 не являются делителями числа 72. Однако последние выписанные нами переходы отходят от принципа инверсии двух, четырех и шести головных или хвостовых ребер.

Рис. 3.8

Если оставаться в рамках провозглашенного принципа перехода от одной цепи к другой, то связи на гранях Г₇₂ следует оставить такими, как они показаны на рис. 3.7. Впрочем, 4-, 6-, 8-, 9-, 12-, 18-, 24-, 36-циклы, которые можно выделить в Г₇₂, также не являются делителями 72-цикла, поскольку, например, 4-циклов всего 12 (вместо 18); они расположены на ребрах гиперкуба Г₇₂:

{1 – 2 – 67 – 68}, {4 – 5 – 34 – 35},

{7 – 8 – 13 – 14}, {10 – 11 – 52 – 53},

{16 – 17 – 46 – 47}, {19 – 20 – 25 – 26},

{22 – 23 – 64 – 65}, {28 – 29 – 58 – 59},

{31 – 32 – 37 – 38}, {40 – 41 – 70 – 71},

{43 – 44 – 49 – 50}, {55 – 56 – 61 – 62}.

В первом 4-цикле имеем следующие переходы:

– 169845B – 1698CB5 – 6138CB5 – 613845B –.

Аналогичные однореберные переходы характерны и для остальных 4-циклов.

Возьмем другой пример: 18-циклов можно провести только два (вместо 4), например:

{1 - 2 - 3 - 4 - 5 - 6 - 7 - 14 - 24 - 46 - 17 - 21 - 22 - 65 - 69 - 55 - 62 - 72}

{43 - 44 - 39 - 16 - 47 - 42 - 37 - 32 - 33 - 34 - 35 - 36 - 58 - 59 - 60 - 61 - 56 - 57}.

Всякий третий 18-цикл будет иметь пересечение с узлами уже выписанных циклов, в частности:

{8 - 9 - 10 - 11 - 12 - 34 - 35 - 36 - 37 - 32 - 33 - 19 - 20 - 15 - 64 - 23 - 18 - 13}.