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

Рис. 8.5.

По формуле (8.67) напишем

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

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

Подставив выражение блочной группы А графа Г в выраже­ние для а1(1), получим

([2 5 6] [3 6 7] [7]) ∩ ([5] [2 5 6] [3 6 7]) +

+ [1 5] [2 5 6] [3 6 7] =

Аналогично рассчитаем а2(1) и а3(1):

Очевидно, что

Пример 8.5. Используя замещающий граф Гz с четырьмя вершинами (рис. 8.6, б), рассчитаем полную блочную группу графа , полученного в результате замыкания вершин μ1 и μ3 в графе Г (рис. 8.6, а).

Рис. 8.6.

Дендритные веса ребер графа Гz(2) определяются из уравнений (8.64) и (8.65):

(а)

Заметим, что

Блочная группа Аz графа Гz равна

Аz= [α1 α2 α5] [α2 α3 α6] [α3 α4 α5],

поэтому блочная группа замкнутого графа равна

== [α2 α3 α6] [α3 α4 α5]=

Согласно уравнению (8.72), для блочной группы графа

получим

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

где

Пример 8.6. Рассчитаем полную блочную группу графа Г с тремя выделенными вершинами μ1, μ2, μ3 (рис. 8.7, а) с помощью замещающего графа Гz, имеющего три вершины (рис. 8.7, б).

Рис. 8.7.

Дендритные веса графа Гz(1), согласно уравнениям (8.64) и (8.65), равны

так как

Применив формулу (8.72), находим

Блочную группу получим, подставив в блочную группу графа Гz

вместо ребер α1, α2 и α3 их дендритные веса а1(1), а2(1) и а3(1). В ре­зультате получаем

и окончательно

где

8.3. Полная блочная группа модуль-графа

Рассмотрим два метода расчета полной блочной группы модуль-графа.

Метод 1. Блочная группа второго ранга 2А модуль-графа, определенное двумя тождественными формулами:

.

может быть преобразовано в замещающую блочную группу А (первого ранга)

А 2А,

если применить операции алгебры блочных групп над ее элементами Aіj в соответствии с выражением

А=

(здесь п= Т — количество столбцов блочной группы 2А, равное числу деревьев скелета Г0 модуль-графа, а g - количество строк блочной группы 2А, равное числу модулей модуль-графа).

На практике при расчете блочных групп модуль-гра­фов часто вместо операций алгебры блочных групп применяют операции алгебры полных блочных групп.

Чтобы преобразовать блочную группу 2А модуль-графа в пол­ную блочную группу , следует заменить все элементы Aіj блочной группы 2А, представляющие собой блочные группы модулей графа Г, полными блочными группами

Aіj

с учетом дефекта суммы столбцов блочной группы 2А

Произведения элементов столбцов

не обладают дефектом произведения, поскольку модули графа Г не содержат общих ребер.

Как известно, элементы блочной группы 2А модуль-графа Г представляют собой алгебраические производные блочных групп отдельных модулей Гі графа Г

Aіj=

где pij - порядок производной блочной группы Aіj, Aі - блочная группа модуля Гі.

Заметим, что все столбцы блочной группы упорядочены в соответствии с номерами модулей

(8.73)

Составим из элементов pіj матрицу, построенную аналогично блочной группы 2А:

P= . (8.74)

Эту матрицу назовем матрицей порядков блочной группы 2А модуль-графа. Порядок элементов pіj в ней аналогичен порядку элементов в блочной группе 2А. Тогда отношение R преобра­зования блочной группы 2А в матрицу порядков Р определим следующим образом:

(2АRР) i=1,2,...,g, j=1,2, ...,n. (8.75)

Заметим, что суммы элементов в отдельных столбцах тматрицы Р равны между собой и равны цикломатическому числу скелета модуль-графа.

Определим понятие идентичности двух столбцов матрицы порядков Р.

Определение 8.5. Два столбца К j1 и Kj2 матрицы порядков Р идентичны тогда и только тогда, когда выполняется условие

(К j1 = К j2) i = l,2,...,g. (8.76)

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

2A = 2AІ+ 2AІІ+ ...+2AN + 2AM, (8.77)

где 2AІ,2AІІ, ..., 2AN — блочные группы второго ранга, содержащие по крайней мере два столбца и имеющие матрицу порядков, построенную из идентичных столбцов; 2АМ— блочная группа, матрица порядков которой не имеет идентичных столбцов.

Отметим, что сумма, представленная выражением (8.77), не обладает дефектом и ее можно записать в виде

(8.78)

причем

а также

, (8.79)

где п'— количество столбцов блочной группы 2АМ и

Из равенств (8.78) и (8.79) следует, что для определения пол­ной блочной группы модуль-графа Г необходимо рассчитать полные блочные группы

Замену блочных групп 2AІ,2AІІ, ..., 2AN на полные блочные группы можно произвести, используя замещающие графы отдельных модулей графа Г и следующие формулы (см. предыду­щий раздел):

(8.80)

где Аі(р) — блочная группа модуля Гі при замыкании его р путей; — полная блочная группа замещающего графа с замкнутыми р путями, элементы которого — дендритные веса аіk(р) ребер этого графа (обозначим эти ребра символами дендрит­ных весов aik при р = 0);