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

(8.99)

Рис. 8.15

Подставив формулу (8.99) в (8.96), получим результат (8.97).

Следует отметить, что, используя формулы перехода (8.98) и (8.99), можно уменьшить порядок производных в выражениях блочных групп модулей, входящих в выражения для блочных групп модуль-графов. Например, в формуле (8.97) блочную группу 1ab можно заменить выражением

а блочную группу 2ab — аналогичным выражением.

8.4. Деревья и деревья высших рангов модуль-графа

Как известно, дерево — это множество ребер связного под­графа, включающее все вершины графа и не содержащее ни одного контура. Блочной группой дерева будет один столбец блочной группы А. Таким образом, число Т деревьев графа равна количеству столбцов блочной группы А. Если вместо каждого эле­мента aіj блочной группы А подставить единицу и вычислить

(8.100)

то получим число деревьев

T =. (8.101)

Если aіj блочная группа А графа неизвестна, то число деревьев можно определить по формуле Трента (99) или (100) из раздела 7.8.3.

Нахождение определителей (99) или (100) из раздела 7.8.3 для графов с большим числом вершин или независимых контуров весьма трудоемко. Поэтому имеет смысл разделить граф на подграфы (модули), рассчитать число Tі этих подграфов и далее определить число Т деревьев всего графа, выразив его с помощью Ті.

Используя формулу (8.101), легко доказать, что для определе­ния числа Т деревьев модуль-графа, состоящего из подграфов, при­годна формула полной блочной группы модуль-графа, запи­санная с помощью блочных групп i отдельных подграфов. Тогда если известна полная блочная группа модуль-графа

=f(i), i = 1, 2, . . ., g, (8.102)

то количество деревьев Т выражается той же функцией

Т = f ( Тi), i = l,2,...,g, (8.103)

где Тi — число деревьев подграфа Гi.

Аналогичная зависимость справедлива для числа Тk k-деревьев (k-деревом называется множество ребер, образованное k раз­дельными связными подграфами, содержащими все вершины графа и не содержащими ни одного контура). k-деревья вводятся для данных k — 1 различных пар вершин графа и представляют собой геометрическое изображение столбцов блочной группы

(8.104)

где al, a2, . . ., аk-1 обозначают произвольные пути между дан­ными k — 1 различными парами вершин графа.

Заметим, что k-деревья состоят из тех же самых ребер, что и деревья графа с замкнутыми k — 1 путями, относительно которых рассматриваются k-деревья. Следовательно, число k-деревьев равно числу деревьев графа с замкнутыми k — 1 путями. Если

А,

i = 1, 2, ..., g, (8.105)

то число Tk k - деревьев блок-графа равно

Tk=f(Tі), i = 1, 2, ..., g. (8.106)

Аналогично определяется число Ts деревьев модуль-графа, содер­жащего s различных путей а1, а2, .... as, не имеющих общих ребер.

Эти деревья представляют собой геометрическое изображение

столбцов блочной группы

(8.107)

где

ai =— обозначения ребер, образующих путь аі.

А,

Способ расчета числа деревьев и k –деревьев графа проиллюстрируем следующими примерами.

Пример 8.12. Рассчитаем число Т деревьев графа (рис. 8.16, а).

Рис. 8.16.

Граф содержит 9 вершин, т. е. для отыскания числа Т следует

рассчитать определитель 8-го порядка

Раскрытие этого определителя достаточно трудоемко. С целью упрощения расчетов разделим исходный граф на три части (рис. 8.16, б), т. е. будем рассматривать граф Г как модуль-граф, состоящий из трех подграфов Г1, Г2, Г3. Согласно уравнению (8.97), полная блочная группа этого графа равна (рис. 8.16, в)

В соответствии с выражением (8.103) число деревьев Т этого графа равно

(а)

где Т1, Т2, Т3 — число деревьев отдельных подграфов Г1, Г2, Г3; T1a, Т1b, Т1с — число 2-деревьев подграфа Г1 относительно путей а1, b1, c1; Т2а, Т2b, Т2с —число 2-деревьев подграфа Г2 относи­тельно путей а2, b2, с2; Т1аb (Т2аb) — число 3-деревьев подграфа Г1 (Г2) относительно путей а1 и b1 (a2 и b2).

Обозначения путей подграфов указаны на рис. 8.16, в. Сле­дует отметить, что числа 2- и 3-деревьев равны числам деревьев подграфов с соответствующими замкнутыми путями.

Определим число деревьев отдельных подграфов.

Имеем

Т1 = 42=16 (полный граф),

Т2= = 27 — 3 — 3 = 21 (планарный граф),

Т3==9 — 1=8 (планарный граф),

Т1аb = 3 (граф с двумя вершинами),

Т2аb==11,

T1a= =8, Т1b = 8, Т3а= =8,

Т2а= =36-1-1-3-3-4 = 24,

Т2b = =24-1-1-3-2-4 = 13,

Т1с = 8, Т2с= =24-3-2=19.

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

Т = 8[3·21 + 16·11 + 8·13 + 8·24- (8 + 8-8) (24 + 13-19)] +

+ 8(8·21 + 16·24) = 8120.

Рассчитаем также число 2-деревьев графа Г (рис. 8.16, а) относительно пути а1 (рис. 8.16, в). Для этого нужно определить алгебраическую производную дА/да1. На основе скелета графа Г имеем

Ad0 = [aia2] [b1b2a3],

поэтому

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

P=

Так как в ней не содержится идентичных столбцов, то

и тогда число 2-деревьев равно

= Т3 (T1abT2a + T1aT2ab) + T1aT2aT3а =

= 8 (3·24 + 8·11) + 8·24·8 = 2816.

Пример 8.13. Рассчитаем число деревьев цепного графа (рис. 8.17, а) с п четырехполюсными модулями одинаковой струк­туры. Блочные группы модулей обозначим

А(1), А(2), . . ., А(п).

Рис. 8.17. Каскадный модуль-граф: а) общий вид; б) модули в раз­ных стадиях закорачивания.