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

Поскольку путь a1 принадлежит только модулю Г1, то

и последнее выражение приводится к виду

На основании этого примера алгебраическую производную

можно определить, применяя следущие правила:

1) Если обозначить столбцы дополнительной блочной группы Аd0 ске­лета модуль-графа как Kd1, Kd2, ..., , тo

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

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

а11, а12, …, — из модуля Г1,

а21; а22, …, — из модуля Г2,

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

ag1, ag2 , …, — из модуля Гg,

причем число элементов некоторых модулей может быть равно нулю (kj =0), то

Для kj = 0 примем (д0Аj/д0) = Aj.

Из этого выражения вытекают следующие следствия.

Следствие 3. Число столбцов блочной группы второго ранга 2А модуль-графа Г равно числу столбцов дополнительной блочной группы Ad0 скелета графа Г.

Следствие 4. Сумма порядков производных блочных групп модуль-графа Г в каждом столбце блочной группы второго ранга 2А графа Г одинакова и равна числу строк дополни­тельной блочной группы Ad0 скелета графа Г (или цикломатическому числу этого скелета).

Вернемся к примеру 10. Найдем дополнительную блочную группу второго ранга 2Ad модуль-графа риc. 15, а. Согласно (98),

Заметим, что блочная группа второго ранга 2Ad имеет те же свойства, что и блочная группа 2А, с той лишь разницей, что вместо производных блочных групп модулей ее элементы есть произведения дополнительных блочных групп и путей отдельных модулей графа.

Как следует из (94), для модуль-графа можно составить один или несколько скелетов Г0, поэтому из утверждения 1 вытекает сле­дующее.

Следствие 5. Блочная группа А модуль-графа Г не зависит от выбора скелета Г0, т. е. она тождественно равна для всех Г0 скелетов данного графа Г.

Пример 11. Найти блочную группу А графа рис. 16, а по двум разным его скелетам Г0 и Г*0 (рис. 16, б и в).

Рис. 16.

Решение.

На основании правила построения конткных графов напишем

Подставив эти соотношения в выражения блочной группы 2А*, получим

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

2A = 2A*.

7.8.3. Дерево второго ранга

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

Столбец блочной группы второго ранга 2А модуль-графа Г можно рассматривать как блочную группу — столбец второго

ранга, геометрическое изображение которого будем называть деревом второго ранга. Скелет дерева второго ранга назо­вем обобщенным деревом скелета Г0. В качестве примера рассмо­трим модуль-граф рис. 17, а, скелет которого представлен на рис. 17, б.

Рис. 17.

Блочная группа второго ранга 2A этого графа равна

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

Рис. 18.

Учитывая, что модули графа Г не содержат общих ребер, опре­делим дерево второго ранга.

Определение 9. Деревом второго ранга графа Г или гео­метрическим изображением столбца блочной группы второго ранга 2А этого графа называется связный граф, имеющий g — 1 общих точек, соединяющих g модулей, которые служат геометрическими изо­бражениями (или обратными изображениями) блочных групп, составляющих столбцы блочной группы 2А. Блочные группы дерева второго ранга представляют собой модули графа Г, по-разному преобразованные путем замыкания их полюсов.

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

Очевидно, что при преобразовании графа в дерево второго ранга постоянны следующие величины: g — число модулей, v — число вершин и М — цикломатическое число графа, в то время как при преобразовании графа в дерево первого ранга постоянно лишь число вершин и.

Аналогично определим обобщенное дерево скелета графа Г.

Определение10. Обобщенное дерево скелета Г0 есть связный граф, имеющий g — 1 общих точек, соединяющих g графов, полученных путем соответствующего преобразования деревьев отдельных модулей, входящих в состав дерева второго ранга.

Подобно дереву второго ранга графа Г, под числом Т обобщенных деревьев скелета Г0 понимается число классов этих деревьев.

Как и ранее, при преобразовании скелета Г0 в обобщенное дерево постоянны: g — число ребер, v — число вершин, М — цикломатическое число скелета.

Число Т классов подобных деревьев второго ранга графа Г, равное числу классов подобных обобщенных деревьев скелета Г0 (а также числу деревьев скелета Г0), можно определить на осно­вании формулы Трента, применимой к скелету Г0

Т = Det|ε·εt| =Det(), (99)

где ε — матрица инциденций вершин (матрица соединений вер­шин) скелета Г0, εt — транспонированная матрица ε, — квадратная симметричная матрица порядка v—1, элементы кото­рой удовлетворяют равенству

где bij — символ Кронекера, — множество ребер, инци­дентных вершине μi (μj) скелета Г0, v — число вершин скелета.

Для планарных скелетов число Т можно определить по формуле

T=Det(UММ), (100)

где UММ — квадратная симметричная матрица порядка М, элементы которой

где {Сі} ({Cj}) — множество ребер, составляющих контур i (j) ске­лета Г0, М — цикломатическое число скелета.

Замечание. Вышеприведенные формулы справедливы для любых линейных графов.

Следует отметить, что для различных скелетов Г0 данного графа Г число Т может быть разным. Однако существует наи­меньшее число Тмин для графа Г, которое соответствует скелету Г0, дополнительная блочная группа которого Аd0 содержит наименьшее коли­чество столбцов.

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

Рис. 19. Граф, состоящий из двух­полюсных модулей: а) граф; б) скелет графа.

Пример 12. Найти для графа рис. 19, а блочную группу 2А.

Имеем