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

Теорема 1.8. Каждое сложное число имеет бесконечное множе­ство способов разложения на простые числа.

Доказательство. Положим, что А = Р1 Р2 . . . Рr. Легко заметить, что величина этого произведения не изменится, если любое из чисел Pі дополнить столбцами, содержащими некоторые элементы всех столбцов одного из оставшихся сомножителей.

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

Пример 1.6.

Рассмотрим свойства структурных чисел с одинаковым числом элементов в строках и одинаковым числом элементов в столбцах, которые представляют наибольший интерес для применения алгебры структурных чисел.

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

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

Теорема 1.9. Если структурное число с одинаковым числом элементов в строках А≠0 (с m строками) имеет каноническое разложение

(1.32)

то все остальные канонические разложения числа А на простые однострочные числа имеют вид

(1.33)

где числа εij принимают только значения 0 или 1.

Доказательство. Положим, существует разложение

отличное от (1.32). Тогда, перемножая А и любоеполучим

Далее,— сопряженный элемент по

отношению кОднако можно заметить, что в классе однострочных структурных чисел Pi справедливо соотношение

(1.34)

Тогда, действительно,

Непосредственно из теоремы 1.9 следует, что двустрочное сложное структурное число имеет лишь три возможных канони­ческих разложения на однострочные числа

(1.35)

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

Теорема 1.10. Число возможных канонических разложений отличного от нуля сложного структурного числа с т строками на однострочные сомножители удовлетворяет неравенству

(1.36)

где k = т (т —1).

Доказательство. Если структурное m-строчное число не имеет вовсе разложения на однострочные сомножители, неравенство (1.36) полностью удовлетворяется. В случае когда имеется воз­можное разложение, оно имеет вид (1.33).

На основе этого разложения можно выделить (т — 1)2 + 1 множеств разложений числа А, ставя в соответствие каждому отдельному множеству те разложения, которые имеют одинаковое число нулевых чисел εij. В общем в выражении (1.33) имеем т2 чисел εij, причем нулевое значение может одновременно при­нимать не более чем k = т2 — т = т (т — 1) чисел εij. С дру­гой стороны, нулевое значение должно иметь минимум т — 1 чисел εij, так как в противном случае в разложении (1.33) имелись бы идентичные сомножители и А = 0. Обозначая через е число нулевых значений εij, имеем неравенство

Таким образом, ∆е выделенных множеств разложений числа А равно

Если через Rem обозначить число разложений с е нулевыми числами εij, то с помощью простых комбинаций можно определить следующие зависимости:

а так как то неравенство (1.36)

действительно выполняется. Рассмотрев зависимость

(1.37)

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

(1.38)

Однако эта оценка дает худшие результаты по сравнению с неравенством (1.36).

6.3. Геометрическое изображение структурного числа

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

Геометризация структурного числа имеет значение прежде всего для его применения при анализе и синтезе электрических цепей.

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

Г = оb (А). (1.39)

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

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

Теорема 1.11. Структурное число А с одинаковым числом эле­ментов в строках, геометрическим изображением которого служит связный граф с вершинами p1, p2, . . ., рп, равно произведению п — 1 простых однострочных сомножителей

(1.40)

причем сомножители состоят из значений описывающей функции ребер, инцидентных произвольно выбранной вершине рi (pi ≠ pj, если i ≠ j) графа Г.

Доказательство. Равенство (1.40), очевидно, справедливо в слу­чае графов с одной и двумя вершинами. Рассмотрим произвольный связный граф с п вершинами. Соединим в нем две произвольные вершины ребром αk. Положим, что выражение (1.40) справедливо для образованного таким образом графа Г*, т. е. что структурное число равно

где

Найдем число

(1)

Структурное число А графа Г с несоединенными верши­нами и висячим ребром αk можно представить в виде

(2)

поскольку множество деревьев графа Г* (с замкнутым ребром αk), дополненное элементом αk, представляет собой множество всех деревьев графа Г с ребром αk. В выражении (2) символ А0 обозна­чает структурное число, составленное из всех столбцов числа А, не содержащих αk. Просуммировав равенства (1) и (2), получим

(3)

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

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

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

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