Дискретно-непрерывная математика (стр. 25 )

А + А' = А0 + А", (40а)

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

А + А'1 = А01 + А"1 α1,

А + А'2 = А02 + А"2 α2

………………………….

А + А'п = А0п + А"п αп

Отсюда левая часть равенства (40а) не содержит обозначений ребра графа Г и равна нулю. Тогда

А =А' =P1P2. . . Pп-1,

что и требовалось доказать.

Сформулируем утверждение об условиях, при которых блочная группа имеет связное изображение.

Утверждение 12. Необходимые и достаточные условия существования геометрического изображения блочной группы в виде связного графа состоят в том, чтобы блочная группа А имела разложение на простые однострочные сомножители

А = Р1Р2 ...Рт, (41)

причем произвольный элемент αik должен встречаться самое большее в двух простых блочных группах Pі, Pj.

Доказательство. Разложение (41) непосредственно следует из утверждения 11 и не требует специального обоснования. Условие того, что элемент αik встречается максимум в двух блочных группах Pі, Pj, тоже очевидно, так как в графе имеют место лишь ребра с двумя концами (одномерные симплексы).

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

1) в произведении А = Р1Р2 … Рт не может быть одинако­вых сомножителей, т. е.

Рі ≠ Pj, i, j = 1, 2, . . ., т (і ≠ j); (42)

2) любой сомножитель Pk произведения (41) не может быть равен сумме произвольного числа остальных сомножителей, т. е.

Рі≠, k = 1,2,...,т (k≠ і). (43)

Из утверждения 12 следует, что блочная группа, у которой число элементов в строках различно, не имеет связного геоме­трического изображения. Условие имеет не только теоретическое значение. Оно однозначно, например, условию физического соответствия матрицы полных проводимостей и пассивной электрической структурной цепи.

6.4. Дополнительная блочная группа и геометрическое обратное изображение

Определение 6. Дополнительной блочной группой для данной блочной группы А называется блочная группа Ad, столбцы которой представляют собой дополнения столбцов блочной группы А до множества элементов αik, из которых состоит блочная группа А.

Если обозначить множество элементов αik, из которых состоит блочная группа А, через L, то столбцы Cdi блочной группы Ad определим как разность (в смысле понятий алгебры множеств)

C1d = L-C2, C2d = L-C2, ..., Cпd = L-Cn, (44)

где С 1, С 2, . . ., Сп — столбцы блочной группы А.

Дополнительную блочную группу можно в таком случае записать в виде

A d ={bk | (bk=L- аk) ∆ (ak А)} (44а)

или иначе

Ad ={{αik} - apk | αik L, ak A). (44б)

Отметим справедливость такого свойства

(А + B)d = Ad+Bd, L = LA LB, (45)

которое означает, что дополнение — операция аддитивная. Допол­нительную блочную группу можно также определить по отноше­нию к другому множеству L*, такому, что L L*, и тогда

AdL* ={L* - ak | ak A}. (44в)

Способ получения дополнительной блочной группы проиллю­стрируем на следующем примере.

Пример 7. Определить блочную группу Ad по отношению к блочной группе

Множество элементов блочной группы L таково:

L ={2, 3, 5, 6, 8, 9}.

Дополнительная блочная группа равна

Оказывается, что для блочной группы удобно иметь дуальное геометрическое изображение, поэтому введем понятие обрат­ного изображения геометрической блочной группы.

Определение 7. Граф Г называется обратным изображением блочной группы А, если столбцы блочной группы А взаимно однозначно соответствуют дополнениям деревьев графа Г так, что столбец блочной группы А представляет собой множество значений описывающей функции соответствующего дополнения дерева. Тогда напишем

Г = cob (А). (46)

Нетрудно заметить, что обратное изображение дополнитель­ной блочной группы Ad одновременно служит изображением блочной группы А и наоборот.

Обратное изображение — это граф дуальной структуры по отношению к геометрическому изображению и иной блочной группы. Связное обратное изображение существует для любой блочной группы, имеющей связное изо­бражение.

Таким образом, блочной группе ставится в соответствие паpa графов дуальной структуры. Один из них служит геомерическим изображением, другой — обратным изображением.

Приведем примеры изображений простейших блочных групп.

Примеры геометрических изображений и обратных изображений блочных групп.

Для обратного изображения сформулируем следующее утверждение.

Утверждение 13. Блочная группа А с одинаковым числом эле­ментов в строках, геометрическое обратное изображение которой суть связный граф Г, характеризующийся цикломатическим числом т, равняется произведению т простых однострочных сомножителей

А = P1P2 ...Pm,

соответствующих линейно независимым контурам графа G. Доказательство. Докажем это утверждение методом индукции.

Утверждение верно для графа с одним и двумя контурами.

Такой граф всегда может быть упрощен и приведен к виду, показанному на рис.1, а или рис.1, б, где ребра 1, 2, 3 — суммы соответствующих ребер графа с двумя контурами.

Рис.1. Граф с двумя циклами.

Для графа (рис.1, а) имеем

,

т. е. действительно А = [1 2] [1 3].

Для случая, изображенного на рис.1, б, утверждение также справедливо, так как

= [1] [2] .

Можно доказать, что утверждение справедливо и тогда, когда ребра 1, 2, 3 заменены последовательным соединением произволь­ного числа ребер.

Положим, что утверждение справедливо для графа с цикломатиче­ским числом т — 1. Тогда можно доказать, что оно справедливо и для графа с числом контуров т.

Таким образом, утверждение справедливо для графов с произволь­ным числом независимых контуров и произвольной структурой.

Утверждения 11 и 13 будут особенно важны для применения метода блочных групп к анализу систем. Они будут служить основой анализа блочных групп, соответствующих заданным графам, представляющим структуру рассматриваемой блочной группы.

6.5. Алгебраическая производная и обратная производная блочной группы

На множестве блочных групп можно определить различ­ные операции; такой операцией является, например, — операция алгебраической произ­водной.

Определение 8. Алгебраической производной блочной группы называется блочная группа дА/дα, определенная как

(47)

( столбцы, содержащие элемент α, опущены.)

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

={bk|bk = ak — {α}, α ak, ak A}. (47а)

Ниже приведены зависимости, аналогич­ные «обычной» производной:

(48)

Алгебраическую производную обозначим как Аα, т. е.

= Аα. (49)

Заметим, что для одноэлементной блочной группы

[α] = 1. (50)

Пример 8. Найдем алгебраическую производную блочной группы:

По аналогии с математическим анализом нахождение произ­водной будем называть дифференцированием.

Дифференцирование блочной группы имеет про­стую геометрическую интерпретацию, сформулированную ниже.

Свойство 1. Геометрическое изображение блочной группы дА/дα представляет собой геометрическое изображение блочной группы А с замкнутым ребром α.

Свойство 1 обосновано утверждениями 11 и 13. Действительно, если положить, что опорным узлом служит любой узел цепи, неинцидентный с ребром α, то элемент α будет встречаться в двух простых сомножителях P1 и Р2, т. е.