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

Для обратной производной суммы, произведения и частного полных блочных групп справедливы следующие соотношения:

(8.40)

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

1. А + B + - 2(∩r), А , B . (8.41)

Выражение 2(∩r) будем называть дефектом суммы блочных групп А и В. Если

∩r=0,

(если А и В , то пересечение ∩r запишем в виде∩)

т. е.

А ∩ В = 0,

то будем говорить, что сумма блочных групп А и В не обладает дефектом суммы, т. е. А + B + .

2. АB - , (8.42)

где

аі ≠ а0 — столбцы произведения , имеющие по крайней мере два идентичных элемента r(α) ≥ 2;

ki — число идентичных столбцов aі в произведении .

Полную блочную группу в выражении (8.42) будем называть дефектом произведения блочных групп А и В. Заметим, что

[ ] = 0 (8.44)

при условии

= <a|( ra(α)>l) (а) = 2 k)>, (8.45)

где k — натуральное число.

Если = 0, то произведение блочных групп А и В не обладает дефектом, т. е. АB .

Произведение блочных групп А1, А 2, . . ., Ag модулей модуль-графа не имеет дефекта, т. е.

(8.46)

так как эти блочные группы не имеют общих элементов.

8.2. Замещающие графы

В заданном графе Г с v вершинами выделим vz вершин, причем

2 ≤vz ≤ v.

Определение 8.4. Замещающим графом графа Г называется полный граф Гz (полный многогранник), построенный на vz вер­шинах, соответствующих vz выделенным вершинам графа Г в пред­положении, что полная блочная группа z графа Гz равна блочной группе А графа Г:

z А. (8.47)

Граф Гz имеет g = vz (vz — 1)/2 граней. Замещающий граф можно рассматривать как скелет модуль-графа Г*z, построенного из двухполюсных модулей. На рис. 8.1 изображен граф Г с vz = 4 выделенными вершинами, его замещающий граф Гz, а также модуль-граф Г*z. А1, А2, . . ., A6 — блочные группы отдельных модулей графа Г*z.

Рис. 8.1. Замещающий граф с выделенными вершинами: а) граф с выде­ленными четырьмя вершинами; б) замещающий граф; в) эквивалентный граф.

Модуль-граф Г*z эквивалентен графу Г при выполнении равенства

*z А, (8.48)

где *z означает полную блочную группу графа Г*z. Из ра­венств (8.47) и (8.48) следует, что

z = *z . (8.49)

Это равенство справедливо, если в полную блочную группу вместо элементов α1, α2, . . ., αg, обозначающих ребра замещающего графа Гz, подставить соответствующие выражения, которые называются дендритными весами ребер замещающего графа.

Обозначим: Adz — дополнительную блочную группу графа Гz, состоящую из элементов α1, α2, . . ., αg, обозначающих его ребра; *z — полную блочную группу графа Г*z, полученную в резуль­тате замыкания всех вершин эквивалентного графа Г*z; 'z — полную блочную группу графа Гz, в котором вместо обозначений ребер α1, α2, . . ., αg графа Fz используются следующие выражения

(8.50)

где g A1, g A2, ..., g Ag — блочные группы модулей графа Г*z, а

Используя эти обозначения, можно написать следующее выражение для блочной группы графа Г*z:

(8.51)

причем

(8.52)

так как модуль-граф Г*z— слабо связный граф, в котором все закороченные модули присоединены к одной вершине (точке сочленения).

Формула (8.51) следует из сравнения блочных групп 2A*z и 2A'z, имеющих одинаковое число столбцов. В каждом столбце блочной группы 2А*z содержится п элементов типа Aiα и g — п элементов типа Aj, в то время как в каждом столбце блочной группы 2А'z содержится g — п элементов типа а′j.

Формула (8.51) справедлива также для всех закороченных графов Г*z(р) порядка р (порядок замыкания — это порядок про­изводной блочной группы закороченного графа):

*z(р) 'z(р) * z (8.53)