1. Общие свойства блок-схем

В этом параграфе мы рассмотрим общие свойства блок-схем, которые сформулированы в следующих теоремах:

Теорема 1. Пусть - некоторая блок-схема. Тогда справедливы следующие утверждения:

1) - нормальное подмножество в G.

2) Если то - нормальная подгруппа группы G, причем - смежные классы группы G по подгруппе и

3) Множества поточечных компонент блок-схем и совпадают.

4) Если в частности, если то и

Если то справедливы утверждения 5)-8):

5) Множества и лежат в одной компоненте связности блок-схемы

6) Для любого натурального s и всех из B имеют место включения: если s четно и если s нечетно,

7) Если в B существует элемент нечетного порядка, то в частности,

8) Если в частности, если то причем если то все элементы из имеют четные порядки.

Если то При этом, если m - наименьшее натуральное число, для которого существует b из B такое, что то верны утверждения 9)-12):

9) для любых

10) Для любой поточечной компоненты блок-схемы равенство имеет место тогда и только тогда, когда

11) Для любых и из B справедливо сравнение

12) Если и - такие поточечные компоненты блок-схем и что то для любого

13) Если в G существует собственная подгруппа, содержащая B, то несвязна.

Теорема 2. Пусть Тогда существуют отображения и такие, что они взаимно однозначно отображают соответственно на и на причем блок-схеме ставится в соответствие блок-схема изоморфная (и, таким образом, самодвойственна). Эти отображения можно определить следующим образом:

1) и При этом если то и а если то

2) Если и в существует инволюция g, то и можно определить как композиции соответственно и где соответствует инволюции g. При этом и

Если блок-схема симметрична, то эти отображения можно определить следующим образом:

3) и При этом если то и а если то

4) Если и в существует инволюция g, то и можно определить как композиции соответственно и где соответствует инволюции При этом и

Д о к а з а т е л ь с т в о теоремы 1. 1) Так как и для любого то Поэтому и - нормальное в G подмножество.

2) Пусть Тогда для любого имеем и т.е. - нормальное подмножество группы G. Далее, для любого имеем и, следовательно, Таким образом, - нормальная подгруппа группы G. Ясно, что В силу транзитивности группы на для любого - смежный класс группы G по подгруппе

Теперь покажем, что Заметим, что для любого Поэтому Ясно, что Пусть Так как в силу то Поэтому существуют элементы группы G такие, что Покажем, что Если то существует такой, что Отсюда Допустим, что для из следует, что Возьмем Тогда существуют такие, что Поэтому Теперь по индукции получаем, что для всех Пусть теперь Повторяя предыдущие рассуждения, получаем, что Таким образом, и свойство доказано.

3) Пусть - связные компоненты блок-схемы соответственно - поточечные компоненты блок-схемы Допустим, для некоторых k и n. Так как - нормальная подгруппа группы G, то вместе с Bg в ней лежит также и блок т.е. Очевидно, Теперь в силу утверждения 2 получаем, что множества поточечных компонент блок-схем и совпадают.

4) Если то равенство следует из утвердения 3), причем - нормальная подгруппа группы G. Поэтому элемент x, образованный всевозможными произведениями элементов из также принадлежит и, следовательно, То, что следует из утверждения 3), так как Следовательно,

Пусть Докажем справедливость утверждений 5)-8).

5) Пусть Достаточно показать, что Для любого в силу того, что и имеем Отсюда следует, что

6) Ясно, что и Допустим, что для произвольного i < s доказана справедливость утверждения. Тогда если i четно, т.е. если i+1 нечетно, и если i нечетно, т.е. если i+1 четно.

7) Из утверждения 6) следует, что для любого элемента нечетного порядка m имеет место включение Поэтому и, как следствие из 5), имеем и

8) Если то утверждение следует из утверждения 4). Пусть Из утверждения 6) следует, что Так как по утверждению 2) то достаточно показать, что Пусть Тогда из утверждения 2) следует, что Возьмем (для ). Тогда существуют элементы группы G такие, что и Покажем, что для всех Пусть Тогда существуют такие, что Отсюда Далее, как и при доказательстве утверждения 2), индукцией по i легко доказать, что для всех Наконец, аналогично получаем, что Таким образом,

Остается показать, что состоит из элементов четных порядков. Допустим, что Тогда и, так как то Поэтому, если s - четно, то а если s - нечетно, то Это значит, что если то |g| - четное число.

Пусть То, что следует из утверждения 2). Пусть m - наименьшее натуральное число, для которого существует такое, что

9) Покажем сначала, что для любых Для любых имеем Допустим, что для i < s доказана справедливость равенства Тогда для имеем что равносильно причем
так как Поэтому Отсюда имеем справедливость равенства Таким образом, для любых справедливо равенство И если s=m - наименьшее натуральное число, что для некоторого имеем то для любых имеем

10) Покажем справедливость для случая Заметим, что тогда и только тогда, когда Действительно, для некоторого в силу утверждения 8) имеем для некоторого Но тогда и тогда по выбору m имеем причем - остаток от деления числа s на m, что невозможно. То, что из следует равенство очевидно.

Так как для любых то равенство равносильно равенству где и Если то это равенство равносильно что возможно, как уже показано, тогда и только тогда, когда Так как то а это и означает, что равенство возможно тогда и только тогда, когда

Пусть теперь По утверждению 2) существует такой, что Поэтому равенство равносильно равенству что равносильно которое возможно, в силу уже доказанного, тогда и только тогда, когда

11) Утверждение является непосредственным следствием утверждения 10).

12) Рассмотрим - поточечную компоненту блок-схемы содержащую точку [e]. Так как - симметричная блок-схема, то по утверждению 8) имеем По утверждению 2) Поэтому и, следовательно, С другой стороны, заметим, что произвольный элемент лежит в для некоторого 0 < i < m. Действительно, если где то в силу 9) и 10) легко видеть, что в точности для Отсюда получаем, что

13) Допустим, - собственная подгруппа группы G, содержащая B. Тогда ясно, что и - собственная подгруппа группы G, т.е. - несвязная блок-схема.

Теорема доказана.

Следствие 1.1. Если G - простая неабелева группа, то связна.

Следствие 1.2. Пусть - симметричная блок-схема. Тогда справедливы утверждения:

1) Множества и лежат в одной компоненте связности блок-схемы

2) Для любых имеют место включения если s четно и если s нечетно, где

3) Если в B существует элемент нечетного порядка, то - нормальная в G подгруппа и связна тогда и только тогда, когда Если в B все элементы - четного порядка, то при либо связна, либо имеет только две компоненты связности и G содержит подгруппу индекса 2.

Следствие 1.3. Пусть - такая блок-схема, что и и - такие поточечные компоненты соответственно блок-схем и что Тогда:

1) и фактор-группа - циклическая порядка m или m/2, где m определено в теореме.

2) Если B состоит только из элементов нечетных порядков, то n=1 и

3) Порядок любого элемента делится на m.

Следствие 1.4. Если в B существуют элементы взаимно простых порядков, то

Доказательство следствий 1.1 и 1.2 достаточно очевидно. Аналогично и для первого пункта следствия 1.3. Пункт 2) следует из утверждения 12) теоремы и пункта 3) следствия 1.2. Пункт 3) следует из того, что по утверждению 10) теоремы для порядка q элемента равенство возможно тогда и только тогда, когда

Доказательство следствия 1.4 непосредственно вытекает из пункта 3) следствия 1.3.

Прежде, чем доказать теорему 2, докажем ряд вспомогательных результатов. Следующая лемма очевидна.

Лемма 1.

1) Равносильны включения и Если блок-схема симметричная, то равносильны включения:

а) и

б) и

2) Если где то для некоторого

Лемма 2. Справедливы следующие свойства

1) - нормальная в G подгруппа.

2) - подмножество множества причем для любых имеем

3) Равенство равносильно равенству

4) Если то для любых равенства и имеют место тогда и только тогда, когда а также для любого имеет место равенство

5) Имеет место включение

Д о к а з а т е л ь с т в о. Утверждение 1) очевидно.

2) То, что следует из определения O[e]. Допустим, что и Так как то

Таким образом, если то и O[g] = O[e], что и требовалось доказать.

Утверждение 3) очевидно.

4) То, что при для любых равенство возможно тогда и только тогда, когда очевидно. Пусть Можем считать, что O[e] = O[g] для некоторого Тогда

Поэтому для любого имеем где Таким образом, для произвольного имеем т.е. Отсюда т.е. g=e. Наконец, Поэтому для любого имеет место равенство

5) Очевидно, Bx = B равносильно и поэтому

Лемма доказана.

Следствие 2.1. Пусть Тогда если

то

при этом если - все такие блоки, что выполняется равенство (1.1), то выполняется и равенство

и наоборот, из равенства (1.3) следует равенство (1.1). Если блок-схема симметрична, то из равенства (1.1) следует включение

при этом, если - все такие блоки, что выполняется равенство (1.1), то выполняется и равенство

и, наоборот, из равенства (1.3') следует равенство (1.1).

Д о к а з а т е л ь с т в о. То, что из (1.1) следует (1.2), очевидно. Пусть - все такие блоки, что выполняется (1.1) и пусть Тогда существуют такие, что Это равносильно тому, что т.е. Следовательно, и в силу имеем Таким образом,

Докажем обратное. Очевидно, - максимальное множество, совпадающее с Поэтому - все блоки, содержащие По уже доказанному имеем, что из (1.3) следует (1.1).

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

Следствие доказано.

Лемма 3. Пусть - произвольная блок-схема. Тогда справедливы следующие утверждения:

1) где

2) тогда и только тогда, когда

Если - симметричная блок-схема, то кроме указанных утверждений справедливы следующие утверждения:

3) где

4) тогда и только тогда, когда

Д о к а з а т е л ь с т в о. 1) Имеем

2) равносильно тому, что (по лемме 1). Тогда, в силу и получаем требуемое утверждение.

Если - симметричная блок-схема, то Покажем справедливость утверждений 3) и 4).

3)

4) равносильно тому, что В силу и как и в 2), получаем требуемое утверждение.

Лемма доказана.

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

1) Если то по теореме I множество является подгруппой группы G и для любого имеем Поэтому То, что при этом сохраняется инцидентность блоков и точек, следует из леммы 3 (пункт 2). Пусть теперь Возьмем Из теоремы I следует, что Далее, все блоки из представимы в виде Bx, где Тогда Поэтому и Аналогично, по лемме 3 и сохраняют инцидентность. Далее, если то (так как причем каждый блок из представим в виде Bx для некоторого и Поэтому и Ясно, что инцидентность точек и блоков сохраняется.

2) Пусть и в существует инволюция. Тогда для и имеем и Если то и Поэтому отображает на Далее, все блоки из представимы в виде Bxg, где Тогда т.е. отображает на и сохраняют инцидентность точек и блоков подсхемы. Действительно, пусть для имеем Тогда, как показано, и Так как равносильно то оно равносильно т.е. равносильно и отображения сохраняют инцидентность точек и блоков. Если блок-схема симметрична, то имеем равносильность включений и (по лемме 1). Поэтому доказательство пунктов 3) и 4) проводится аналогично доказательству пунктов 1) и 2) с той лишь разницей, что везде отсутствуют степени -1.

Теорема доказана.

Следствие 2.2. Если то любая компонента блок-схемы самодвойственна.

Д о к а з а т е л ь с т в о. Это следует из утверждения 1) теоремы II, изоморфности всех связных компонент и из сохранения инцидентности при отображениях и