В этой части работы выявлены некоторые свойства групп автоморфизмов блок-схем; они сформулированы в следующей теореме.
Теорема 3. Справедливы следующие свойства группы
автоморфизмов 
блок-схемы 
.
1) транзитивна на множестве точек и блоков блок-схемы.
2) Для любого 
имеет место равенство
3) Для произвольных и 
имеют место
равенства 
Если 
то справедливы свойства 4) - 6).
4) Для любого имеет место равенство 
и изоморфизм 
5) Если - такая блок-схема, что 
для некоторых 
то 
6) Если - такая блок-схема, что для некоторых g и 
из G и 
то
и для 
равенство 
возможно тогда и только тогда, когда 
т.е. когда
для имеет место равенство
Если - симметричная блок-схема, то выполняются следующие
свойства:
7) 
8) 
для любого 
9) 
в частности, если
то 
10) 
если 
Д о к а з а т е л ь с т в о. Справедливость
свойства 1) нами уже замечена выше. Свойство 2) непосредственно
следует из известного факта о порядке транзитивной группы,
действующей на конечном множестве 
мощности |G|.
Докажем справедливость свойства 3). Пусть 
Тогда для произвольного имеем
Отсюда и следует, что 
Если 
то 
и, следовательно, 
и свойство 3) доказано.
Пусть 
4) Так как 
то первая часть утверждения
очевидна. Вторая часть утверждения следует из свойства
самодвойственности блок-схемы.
5) Если для некоторых 
из G имеет место равенство
то в силу свойства 3) можно
считать 
для некоторого 
Так как 
то
для любого 
справедливо
т.е. для любого 
имеет место 
(по лемме 1.2 в силу 
Тогда 
и свойство доказано.
6) Пусть Тогда из свойства 5) следует, что для
некоторых g и 
при выполнении условия выполняется условие 
Пусть 
Тогда для некоторого имеем
что равносильно тому, что
Последнее
равносильно 
или 
Таким образом, 
Свойство 6) доказано.
Пусть теперь блок-схема симметрична. Тогда, как замечено
выше, отображение 
определенное по правилу 
является автоморфизмом блок-схемы. При этом
справедливость свойства 7) очевидна. Докажем справедливость
свойств 8)-10).
8) Для любого 
имеем 
и свойство доказано.
9) Допустим, что 
и 
Тогда 
и для
произвольного выполнено равенство 
С одной стороны, 
С другой стороны, 
Таким образом, если z зафиксирован, а g -
произволен, то 
; в частности, при g=e имеем
т.е. 
Следовательно, 
и 
Обратно, пусть Тогда
для любого имеем zg=gz и 
и 
Таким образом, 
что и требовалось доказать.
10) Ясно, что 
Поэтому в силу пункта 9) достаточно показать
перестановочность элементов из 
и 
Для
произвольных 
и 
имеем, с одной стороны, 
а с другой стороны, 
т.е. 
Теорема доказана.
Следующая лемма дает еще одно свойство для блок-схем с некоторыми жесткими ограничениями на строение.
Лемма 4. Пусть - симметричная блок-схема
такая, что |O[e]| > 1, в ней нет k-веников для 
для некоторых g и из G имеем место равенство и пусть Тогда из
следует 
Д о к а з а т е л ь с т в о. Заметим, что по
пункту 6 теоремы 3 
и 
лежат в одной
компоненте связности и по пункту 4 теоремы I имеем 
Так как - симметричная блок-схема, то любой
элемент 
имеет вид 
где 
для любого 
Таким образом, достаточно
показать, что если 
то 
централизует любой элемент вида 
где 
Пусть 
Заметим, что 
(поэтому 
) и для всех 
имеем 
так как 
(см. пункт 6 теоремы III). Покажем сначала, что
для для всех 
имеем 
Допустим, что для некоторого справедливо
Тогда 
Возьмем 
содержащие [x]. Тогда 
и поэтому 
- k-веник с
k>2, что невозможно в силу условия. Таким образом, для любого
имеем 
в частности,
показано, что для любых 
справедливо равенство
Допустим, что для произвольного
натурального i показано, что 
где 
Для того,
чтобы показать, что и для 
из B имеет место равенство
достаточно
показать, что все точки блока 
централизуются
автоморфизмом (см. пункт 6 теоремы
III). Имеем 
причем все блоки 
множества 
в силу пункта 6
теоремы III нормализуются автоморфизмом 
так как по
индукции 
Возьмем все блоки,
содержащие 
и 
Аналогично тому, как доказывается, что 
показывается, что 
Следовательно, централизует 
и по индукции получаем, что
централизует любой элемент вида где 
Лемма доказана.
В заключение автор выражает искреннюю признательность А.Н.Фомину за постановку задачи и постоянное внимание к работе.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант 96-01-00488).
Поступила 16.03.95
СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ