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

Можно также обосновать свойство, согласно которому при исключении из обратного изображения блочной группы ребер, определенных столбцами дА/дα∩ дА/дβ, граф всегда сводится к такому графу, у которого цикломатическое число m=1. Опре­деление ориентации ребер α и β по отношению друг к другу не встречает трудностей.

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

Определение 12. Граф называется соответственным, если каждые две его вершины принадлежат хотя бы одному элемен­тарному контуру.

Для соответственного графа справедливо следующее свойство.

Свойство 3. Граф (мультиграф) будет соответственным тогда и только тогда, когда он служит обратным изображением блочной группы А, удовлетворяющего условию

(62)

Это свойство следует из определения функции совпадения, согласно которому столбцы

соответствуют ребрам, исключение которых приводит к упроще­нию графа обратного изображения к одному циклу с ребрами α и β.

На рис. 4 показано несколько графов, из которых только один граф соответственный.

Рис. 4. Примеры графов: а) соответственный; б, в, г) несоответственные.

Если применить условие (62), например к графу, показанному на рис. 4, б, получим

A=[1 2] [3 4]=

Тогда

=[3 4]≠0,

а также

==0.

т. е. условие (62) не выполняется для графа (рис. 4, б) и этот граф не соответственный. Применение условия (62) для определения характера графа излишне, если известна его структура. Из рассмотрения контуров графа можно непосред­ственно сделать вывод о том, выполняется ли условие (62). Это условие весьма ценно, если известно только блочная группа, не разложенная на первичные сомножители, а также для использования при синтезе систем с помощью блочных групп на ЭВМ.

6.8. Понятие ряда и последовательности блочных групп

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

<An>= А1, А2, А3, . . ., Ап, ....

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

A={ak | αij ak, i, j, k = 1, 2, 3, … .},

где мощность множеств а и А конечная, a αij — элементы норми­рованного пространства.

Введем сначала понятие нормы множества а, которую обозна­чим как || а ||. Введем определение

а={α1, α2, . . ., αv} || а || = ||Ø|=0,

где || αі || — норма элемента αі.

Норму блочной группы определим как

|| А || =

где λ проходит все столбцы, имеющиеся в блочной группе А. Метрику на множестве блочных групп определим как

ρ(А, В) = ||АВ||,

где — означает симметричную разность множеств. Из этого опре­деления следует, что метрика ρ(А, В) удовлетворяет следующим основным условиям:

ρ (А, В) = 0 А = В,

ρ (А, В) = ρ(В, А),

ρ (А, В) + ρ (В, С)≥ρ (А, С).

Для двух произвольных блочных групп справедливо неравенство

|| АВ ||≤|| A || || B ||,

которое следует из неравенства Буняковского — Шварца.

Если для последовательности блочных групп Ап суще­ствует блочная группа А, удовлетворяющее равенству

ρ (Ап, А) = 0,

то блочная группа А называется пределом последовательности блочных групп Ап и записывается в виде

А = An.

Последовательность Ап называется сходящейся, если существует предел, и, наоборот, расходящейся, если таковой отсутствует.

Кроме сходимости по отношению к метрике, введем и другие понятия сходимости последовательности блочных групп, кото­рые обозначаются

ob Ап и cob An

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

( ob Ап = А) [ ob (Ап) = σ] [σ = ob (А)],

( cob Ап = А) [ сob (Ап) = σ] [σ = сob (А)],

Примером сходимости последовательности Ап по отношению к обратному изображению может служить структура в виде цепи, метрический граф которой имеет ступенчатую структуру с равномерно распре­деленными на отрезке [0, 1] вершинами (рис. 5).

Рис. 5. Лестничный граф с равномерно распределенными вер­шинами.

Если увеличить число делений отрезка [0, 1], то при п→∞ граф преобразуется в структуру с густым (однако четным) множе­ством ребер. Нумеруя грани графа, например, как показано на рис. 5, можно определить следующую последовательность блочных групп:

А1=[1 2 3 4],

А2 = [1 2 3 4] [3 5 6 7],

А3 = [1 2 3 4] [3 5 6 7] [6 8 9 10],

…………………………………..

обратным изображением которой и служит граф.

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

А = cob-1 σ, σ = Sn,

где Sn — последовательность цепей (метрических графов) вида изображенных на рис. 5.

Рядом блочных групп будем называть выражение

A1+A2+A3 + ...+An=

Блочные группы А1, А2, А3, ... называются составляющими ряда, блочные группы же

S1 =A1,

S 2 =A1 + A2,

S 3 = A1 + A2 + А3,

………………………..

Sn=A1+A2+A3 + ...+An

есть частичные суммы ряда. Бесконечный ряд блочных групп называется сходящимся, если последовательность частичных сумм сходится. Предел последовательности частичных сумм называется суммой ряда блочных групп. Если

Sn = S,

то

S=

7. Блочные группы и графы высших рангов

Различного класса системы состоят из элементов, взаимодействую­щих друг с другом различным образом. Например, структуры физических систем могут состоять из многополюсных элементов (многополюс­ников); их также можно рассматривать как системы, состоящие из блоков или подблоков. Топологические модели таких систем представим в виде графов второго ранга, построенных из дву­мерных континуумов (блоков) с выделенными точками, называе­мыми полюсами. Блоки соответствуют ребрам линейных графов первого ранга. Блочные группы блок-графов назовем блочными группами высших рангов — второго, третьего и т. д. Эти блочные группы, подобно матрицам, состоящим из блочных матриц, представ­ляют собой семейства блочных групп низшего ранга. Основываясь на определении операций над блочными группами первого ранга, определим в соответствии с теорией множеств, теории графов и теорией математической логики операции над блочными группами высшего ранга и графами высшего ранга.

7.1. Определение блочной группы второго ранга

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

Определение 1. Блочная группа второго ранга 2А есть семейство множеств 2аj

2A={2аj}j=1, 2,..,n. (1)