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

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

(1.41)

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

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

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

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

(1.42)

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

(1.43)

Из теоремы 1.12 следует, что структурное число, у которого

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

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

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

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

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

(1.44)

где — столбцы числа А.

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

(1.44а)

или иначе

(1.44б)

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

(1.45)

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

(1.44в)

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

Пример 1.7. Определить структурное число Ad по отношению к структурному числу

Множество элементов числа L таково:

Дополнительное структурное число равно

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

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

Г = cob (A). (1.46)

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

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

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

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

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

соответствующих линейно независимым контурам графа G.

Доказательство. Докажем эту теорему методом индукции.

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

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

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

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

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

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

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

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

Теоремы 1.11 и 1.13 особенно важны для применения метода структурных чисел к анализу электрических цепей. Они служат основой расчета структурных чисел, соответствующих заданным графам, представляющим структуру рассматриваемой цепи.

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

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

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

(1.47)

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

(1.47а)

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

(1.48)

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

(1.49)

Следует заметить, что для одноэлементного структурного числа

(1.50)

Пример 1.8. Нахождение алгебраической производной струк­турного числа:

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

Дифференцирование структурного числа имеет весьма про-. стую геометрическую интерпретацию, сформулированную ниже. Свойство 1. Геометрическое изображение структурного числа дА/дα представляет собой геометрическое изображение струк­турного числа А с замкнутым ребром α.

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

где п — число вершин графа. Отсюда

Так как для однострочных простых чисел Р1 и Р2 справедливо, что то

(1.51)

Это означает замыкание ребра α в геометрическом изображении или отключение (или однополюсное отключение) ребра α в обрат­ном геометрическом изображении (тогда п — 1 = т — цикло-матическое число графа). Поскольку величина структурного числа не зависит от выбора опорного узла, полученный результат носит общий характер.