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

Здесь Ad0 — дополнительная блочная группа скелета Г0 незамкнутого гра­фа Г; 2А (2Ad) — блочная (дополнительная) группа незамкну­того графа Г; A1, А2, . . ., Ag (Adg, Adg, . . ., Adg) — блочные (дополнительные) группы блоков незамкнутого графа Г; d1, d2, , . . . . ., dk-1 — пути скелета Г0 (незамкнутого), образующие произ­вольное дерево, касающееся вершин μ01, μ02, . . ., μ0k.

Заметим, что на основании правила формирования контурных графов в приведенных выше формулах d1, d2, , . . . . ., dk-1 также представляют собой пути модуль-графа Г, образующие дерево, касающееся вершин μ1, μ2, . . ., μk.

Пример 13. Найти блочную группу и дополни­тельную блочную группу графа образованного замыканием вершин μ1, μ2, μ3 в модуль-графе Г [рис. 25, а (пунктиром обо­значены пути замыкания вершин)].

Рис. 25.

Дополнительная блочная группа Ad0 скелета Г0 (рис. 25, б) незамкну­того графа Г равна

Ad0= [c1a2],

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

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

В скелете Г0 выберем пути между вершинами μ0й и μ03 - [b1] и вершинами μ03 и μ02 — [b2с2].

Тогда для замкнутого графа имеем

Если в графе Г выбрать пути b1 и d2 (рис. 25, а), то получим

Этот результат совпадает с предыдущим, так как

.

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

=[b1] [d2]( 2Ad)=

б. Деление вершин модуль-графа

Используя формулы (84), (85), (101) и (102) для блочной группы и дополнительной блочной группы графа , образованного делением вершины μ= [α1α2. . . αiαj. . . αp] гра­фа Г на две части μ1 = [α1α2. . . αi] и μ2 = [αj. . . αp], получим следующие выражения для блочной группы и дополнитель­ной блочной группы модуль-графа :

=(105)

= (106)

где [μ01] и [μ02] — однострочные блочные группы двух частей вершины μ0 скелета Г0, соответствующие частям μ1 и μ2 вершины μ в графе Г; [μ1] и [μ2] — однострочные блочные группы обеих частей вершины μ графа Г, рассматриваемого как линейный граф и состоящего из подграфов, представленных модулями (граф с известной структурой модулей).

Пример 14. Найти блочную группу графа , образованного делением вершины μ графа Г (рис. 26, а) на две части μ1 и μ2.

Рис. 26.

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

Ad0 = [а1а3] [b1b2] [а2b3], μ01 = [a3b3], μ02 = [а1 а2 b1b2],

Поэтому

=

Аналогичный результат получим, рассчитывая блочную группу графа на основании его скелета , изо­браженного на рис. 26, г.

7.8.6 Перемещение нижних индексов

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

Для упрощения записи введем условное обозначение алгебраи­ческой производной блочной группы А

(107)

а также дополнительной блочной группы Ad

[α] Ad = Ad α (108)

Кроме того, обозначим

(109)

[αk] Adk = Ad kα (110)

где индекс k в обозначении αk указывает, что ребро αk (или путь αk) принадлежит модулю Гk с блочной группой Ak и дополнитель­ной блочной группой Ad k.

Операцию, описываемую уравнениями (107) и (108) или (6.109) и (110), назовем перемещением нижних индексов и обо­значим стрелкой ↓; тогда

(111)

[α]Ad = [α]↓Ad = Ad α, (112)

=[αk]↓Ak = Akα, (113)

[αk] Adk = [αk]↓Ad k = Ad kα. (114)

Применяя операцию перемещения нижних индексов для блочной группы и дополнительной блочной группы модуль-графа, выражения

и

запишем в следующем виде:

(115)

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

[ak]↓Aka = Akaα = 0, (116)

[ak]↓Al = Al, k≠l, (117)

[ak]↓ (118)

где [ak]— произвольная блочная группа, связанная с графом Гk, а также

(119)

(120)

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

Пример 15.

Пример 16.

Пример 17.

Пример 18.

Рис. 27.

Пример 19. Найти блочную группу 2А модуль-графа Г (рис. 27, а), скелет которого Г0 изображен на рис. 27, б:

Ad0= [а1 а2] [b1 b 2 b 3] [с2 b3] = ,

Дополнительная блочная группа 2Ad находится аналогично, так как

Операция замыкания вершин графа при использовании пере­мещения нижних индексов выглядит следующим образом: замк­нуть граф Г (рис. 27, а) по пути а1. Тогда