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

Это определение можно записать следующим образом:

Г0 =<Р, Z0, ε>. (91)

где Р — множество вершин модуль-графа Г, Z0 — множество деревь­ев Dk модулей графа Г, ε — многоаргументное соотношение инци­денции графа Г.

В качестве примера (рис. 13) изображены скелеты: модуль-графов, показанных на рис. 12.

Рис. 13. Скелеты модуль-графов, изоб­раженных на рис. 12.

Ребра а1, b1, с1 (рис. 13. а) образуют дерево D1 модуля Г1, ребра а2, b2 — дерево D2 модуля Г2, а ребра а3, b3 — дерево D3 модуля Г3 графа (рис. 12, а).

Число ребер, образующих дерево Dk модуля Гk, равно vk — 1, где vk — число полюсов этого модуля.

Скелет графа Г имеет р ребер, причем

р= (vk-1), (92)

где g — число модулей графа Г.

Цикломатическое число М скелета графа Г равно

М= (vk-1) - (v -1) = vk -v-g+1, (93)

где v — число вершин графа Г. Например, для графа, изображен­ного на рис. 12, а, цикломатическое число скелета Г0

М = (4 + 3+3) — 5 — 3 + 1= 3.

Заметим, что для всех скелетов модуль-графа Г число ребер р, число вершин v и цикломатическое число М постоянны.

Как следует из формулы (94), для линейного (состоящего из ребер) графа можно построить лишь один скелет (Г0 = 1), который изоморфен рассматриваемому графу. Лишь один скелет также соответствует графу, состоящему из двухполюсных модулей.

Представление пути d ребром а скелета Г0 выражается в виде

[а] = [d].

Например, для ребра дерева Dk (рис. 14, пунктирная линия)

напишем

[ak] = [1 2 3 4],

[bk] = [4 6 7] (рис. 14, а) или [bk] =[4 3 5 7] (рис. 14, б),

[ck] = [8 9] (рис. 14, а) при [ck] = [8 10 11 12] (рис. 14, б).

Рис. 14. Представление ребра подграфа Гk реб­рами дерева Dk (пунктир), концы подграфа выделены.

Приведем утверждение для модуль-графов.

Утверждение 1. Блочную группу А модуль-графа Г всегда можно записать в виде

(95)

а дополнительная блочная группа Ad этого графа в виде

(96)

где А1, A2, . . ., Ag — блочные группы модулей Г1, Г2, . . ., Гg графа Г; Ad1, Ad2, . . ., Adg — дополнительные блочные группы модулей Г1, Г2, . . ., Fg графа Г; Аd0 — дополнительная блочная группа скелета графа Г; g — число модулей графа Г.

Докажем утверждение методом полной математической индукции.

Скелет Г0 графа Г преобразуем в граф , не содержащий контуров. Для этого выполним однополюсное отключение М ребер l1, l2, . . ., lМ произвольного дополнения графа . Блочная группа графа , полученная путем преобразования модуль-графа Г (подобно преобразованию графа Г0 в граф ), равна

(а)

так как граф имеет общие точки, соединяющие отдельные модули.

В этом выражении А1, A2, . . ., Ag — блочные группы модулей Г1, Г2, . . ., Fg рассматриваемого графа Г. Заметим, что произведение не имеет так называемого дефекта произведения, так как блочные группы А1, A2, . . ., Ag не содержат общих элементов.

В графе будем поочередно присоединять отключенные ранее концы ребер дополнения. Присоединив концы ребра l1, получим первый контур, состоящий из последующих ребер гра­фа :

l1, l11, l12, . . ., l1α.

Блочная группа соответственно преобразованного графа [согласно выражению (70), при замыкании вершин графа] равно

(б)

а дополнительная блочная группа графа равна

=[ l1l11l12 . . . l1α]. (в)

Учитывая в равенстве (б) соотношения (а) и (в), получим

Граф , образованный путем присоединения М — 1 ребер допол­нения l1, l2, . . ., lm-1, имеет М — 1 независимых контуров.

Пусть для преобразованного таким образом графа блочная группа равна

где = С1С2 . . . CМ-1; С1, С2, …, CМ-1— блочные группы независимых контуров графа .

Замечание. Блочная группа контура графа — одно­строчная блочная группа, элементы которой представляют собой обозначе­ния всех ребер этого контура.

Присоединив последнее ребро lМ, получим скелет Г0 графа Г. Ребро lМ замыкает М-ый независимый контур, состоящий из ребер

lM,

На основании формулы замыкания вершин графа блочная группа А графа Г равнa

а дополнительная блочная группа скелета Г0 равна

= [ lМlM1lM2 . . . lMζ]. (е)

Учитывая равенство (г) и (е), из выражения (д) получим

что и требовалось доказать.

Аналогично можно доказать формулу (96) для дополни­тельной блочной группы Аd модуль-графа Г.

Выражения (95) и (96) можно записать в виде блочных групп второго ранга

(97)

(98)

Этот способ записи более нагляден и удобен на практике.

Сравнивая блочные группы 2А и 2Аd произвольного модуль-графа, заметим, что их элементы связаны соотношением

(Aij)d=Adij.

Тогда

(2A)d* = 2Ad,

т. е.

Ad* = Ad, A = 2A, Ad 2Ad, (A)d (2A)d*.

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

Пример 10. Найдем блочную группу модуль-графа рис. 15, а, скелет Го которого приведен на рис. 15, б.

Рис. 15.

Дополнительная блочная группа модуль-графа скелета Г0 равна

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

А

Для первого столбца этой блочной группы второго ранга найдем алгебраическую производную

Так как путь с2 принадлежит только модулю Г2, то

и