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

аіk(р)= (8.81)

или

аіk(р)= (8.82)

При этом

(8.83)

где — блочная группа произвольного дерева, касаю­щегося всех вершин замещающего графа Гiz, кроме вершин, инцидентных ребру aik;

(8.84)

(8.85)

где Di — блочная группа произвольного дерева замещающего графа Гiz (ребра этого графа одновременно представляют собой соответствующие пути модуля Гi).

Дополняя деревья отдельных модулей, содержащиеся в скелете модуль-графа, получаем их замещающие графы в виде полных графов (полных многоугольников). Пусть, например, блочная группа 2АІ выражения (8.77) равна

(a)

причем

(pij = pik = pi), i = l, 2, ..., g, j, k=l, 2,...,пІ.

Подставив вместо элементов , в выражении (а) блочные группы замещающих графов модулей, в соответ­ствии с канонической формой приведем полученную блочную группу второго ранга к замещающей блочной группе первого ранга АІ:

АІ = (б)

Далее по формулам (8.81) или (8.82) рассчитаем дендритные веса ребер замещающих графов и подставим их в выражение (б). Таким образом, получим полную блочную группу , выраженную с помощью полных блочных групп отдельных модулей.

Аналогично вычислим полные блочные группы и после суммирования с блочной группой найдем полную блочную группу модуль-графа Г.

Проиллюстрируем на примерах метод 1 определения полной блочной группы модуль-графа.

Пример 8.7. Определим полную блочную группу модуль-графа Г, изображенного на рис. 8.8, а.

Рис. 8.8.

Дополнительная блочная группа A0d скелета Г0 (рис. 8.8, б) равна

A0d = [a2 b1] [а3 b2]= .

Следовательно, блочная группа 2А графа Г имеет вид

(8.86)

Матрица порядков

P=

не содержит идентичных столбцов, следовательно, полная блочная группа графа Г, согласно выражению (8.79), имеет вид

(8.87)

где

Заметим, что для рассмотренного в этом примере типа графов в виде цепочки с произвольным количеством модулей матрица порядков никогда не содержит идентичных столбцов, поэтому полная блочная группа определяется по формуле (8.79) без применения замещающих графов.

Пример 8.8. Рассчитаем полную блочную группу модуль-графа Г, изображенного на рис. 8.9, а.

Рис. 8.9.

Дополнительная блочная группа A0d скелета Г0 (рис. 8.9, б) имеет вид

A0d = [a1 а2] [b1 b2]=

поэтому блочная группа 2А графа Г равна

а матрица порядков имеет вид

P= .

Х Х

В этой матрице содержатся два идентичных столбца (обозначен­ные снизу буквой X), поэтому, согласно уравнению (8.77), имеем

. (а)

Блочная группа равна

. (б)

Блочную группу

(в)

заменим полной блочной группой, используя замещающие графы Г1z и Г2z модуль-графа Г (фиг. 8.9, в). Для этих графов можно написать

A1a = [b 1(1) с1(1)],

А1 b = [а1(1) с1(1)],

А2а = [b 2(1) с2(1)],

А2 b =[ а 2(1) с2(1)].

Подставив эти выражения в формулу (в), получим

,

так как

а — дефект суммы столбцов блочной группы АІ (вычеркнуты два идентичных столбца). Дендритные веса с1(1) и c2(1) определяются из выражения (8.81)

так как

v1z=v2z=3, p1= p2, i(0)= I,

Полную блочную группу графа Г (рис. 8.9, а) подсчитаем по формуле

(8.88)

где

Пусть, например, граф Г имеет вид, представленный на рис. 8.10, а. Модули (подграфы) Г1 и Г2 изображены на рис. 8.10, б, a иx замедающие графы Г1z и Г2z — на рис. 8.10, в.

Рис. 8.10.

На основании формулы (8.88) полная блочная группа этого графа равна

Пример 8.9. Рассчитаем полную блочную группу модуль-гра­фа Г, изображенного на рис. 8.11, а.

Рис. 8.11.

Дополнительная блочная группа А0d скелета Г0 (рис. 8.11, б) равна

А0d = [а1а2] [b1b2] [с1 с2] =

Поэтому блочная группа 2А графа Г имеет вид

(8.89)

Матрица порядков имеет вид

P= ,

Х1 Х1 Х1 Х2 Х2 Х2

следовательно,

2А = 2АІ + 2АІІ + 2АМ, (а)

где

(б)

(в)

Для замены блочных групп 2АІ и 2АІІ полными блочными группами дополним деревья Г10 и Г20 до полных графов Г1z и Г2z, как показано на рис. 8.11, в, рассматривая эти графы как замещающие графы модулей Г1 и Г2. При этом будут справедливы следую­щие соотношения:

A1ac=[b1(2) d 1(2) f1(2) g 1(2)],

A1bc=[a1(2) d 1(2) f1(2)],

A1ab=[c1(2) d 1(2) g1(2)].

Подставив эти выражения в блочную группу 2АІ (б), получим

(г)