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

Акимов О.Е.

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

Группа цепей тетраэдра

На рис. 3.3 изображен граф Г₄, представляющий соответствующую группу цепей G₄, переводящую полные цепи тетраэдра друг в друга. Пусть для начала вершина a послужит нам привязкой. Тогда вершины и ребра тетраэдра разобьются на классы эквивалентности: вершины на {a} и {b, c, d}; ребра на {0, 1, 2} и {3, 4, 5}. Относительно привязки a существует шесть цепей:

A = abcd = 054,     D = acbd = 253,

B = abdc = 034,     E = adbc = 135,

C = acdb = 243,     F = adcb = 145.

Рис. 3.3

Преобразования цепей разбиваются на несколько классов. Прежде всего выделяются два класса, в первом из которых участвуют ребра из класса {0, 1, 2}, во втором — ребра из класса {3, 4, 5}:

C_a1: 

A – F = 01,     B – C = 02, 

F – A = 01,     C – B = 02, 

D – E = 21,     E – D = 21, 

C_a2:  

A – B = 35,     E – F = 34,

B – A = 35,     F – E = 34,

C – D = 45,     D – C = 45.

Третий класс C_a3  определяется последовательным преобразованием, взятым из класса C_a1 и C_a2 , или сначала из C_a2, потом из C_a1, т.е. по формуле:

C_a3 = {C_a1 – C_a2, C_a2 – C_a1}.

Конкретно — класс C_a3:

A – F – E = A – E = 10 34,     E – F – A = E – A = 10 34,

F – A – B = F – B = 10 53,     B – A – F = B – F = 10 53,

A – B – C = A – C = 20 35,     C – B – A = C – A = 20 35,

B – C – D = B – D = 20 54,     D – C – B = D – B = 20 54,

D – E – F = D – F = 21 34,     F – E – D = F – D = 21 34,

E – D – C = E – C = 21 45,     C – D – E = C – E = 21 45.

Четвертый класс C_a4 определяется формулой:

C_a4 = {C_a1 – C_a2 – C_a1, C_a2 – C_a1 – C_a2}.

C_a4: 

A – F – E – D = A – D = 20 34,     D – E – F – A = D – A = 20 34,

B – C – D – E = B – E = 10 54,     E – D – C – B = E – B = 10 54,

C – B – A – F = C – F = 12 53,     F – A – B – C = F – C = 12 53.

По рисунку графа Г₄ (рис. 3.3) можно установить, что в подстановках класса C_a3 ребра {0, 1, 2} расположены относительно ребер {3, 4, 5} несколько иначе, чем они расположены в классе C_a4. Полезно обратить внимание и на другое. В цепи A ребра чередуются как 0, 5, 4; в цепи C — как 2, 4, 3. При переходе от цепи A к цепи C происходит исчезновение ребер 0, 5 и появление ребер 1, 3. Вместе с тем ребро 4, расположенное в хвосте цепи A, оказывается в середине цепи C. При переходе от цепи A к цепи D сохраняющееся ребро 5 уже не меняет своего серединного положения. В индивидуальных реберных заменах A – C и A – D эти факты не получили никакого отражения; замены 20 35 и 20 34 ничем принципиальным не отличаются. Но они различимы коллективно при делении реберных подстановок на классы эквивалентности: A – C отнесена к классу C_a3, A – D — к классу C_a4.

Помимо упомянутых классов, имеется еще один нулевой класс C_a0 или класс тождественного элемента {e}, образованный всеми переходами

A – A = B – B = ... = F – F = e.

Таким образом, в группе G_4a имеется 31 элемент преобразования цепей, которые разнесены по пяти классам эквивалентных преобразований.

Обратимся к поиску подгрупп группы G_4a. С этой целью будем последовательно удалять ребра из графа Г₄ и смотреть, какие из цепей остались, а вместе с ними и цепные преобразования. Сначала удалим ребро 5. Получим неполный граф G₄₁, показанный на рис. 3.4а

Рис. 3.4

В графе Г₄₁ можно провести две цепи B = 034 и C = 243, в которых ребро 1 не участвует в образовании цепей, поэтому его также можно удалить вместе с ребром 5. Цепи B и C определяют минимальную группу {e, 02, 02}. К аналогичному результату приводит удаление по отдельности ребер 3 и 4: в первом случае от всей группы G_4a остается группа {e, 01, 01}, во втором — {e, 12, 12}. Это означает, что класс ребер {3, 4, 5} играет важную роль в формировании цепей. Меньшее влияние оказывают ребра из класса {0, 1, 2}. Удалим ребро 0, получим граф Г₄₂ (рис. 3.4б).