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

= (73)

где А — блочная группа незамкнутого графа,

В выражении (73) образуют путь, проходящий через промежуточные вершины μ2, μ3, …, μk-1 и соединяющий вершины μ1 и μk незамкнутого графа Г. Так как каждый из участков пути при замыка­нии вершин μ1, μ2, …, μk образует в графе Г контур, допол­нительная блочная группа замкнутого графа равна

= Аd (74)

Согласно правилу организации контурных графов, для произвольного участка пути имеем

(75)

Используя выражение (75), обобщим соотношения (73) и (74):

= (76)

= Аd (77)

где d1, d2,…, dk-1 — участки пути, образующие произвольное дерево, касающееся вершин μ1, μ2, …, μk. Произведение

Dk= (78)

представляет собой замещающую блочную группу для блочной группы второго ранга, описывающего дерево, касаю­щееся вершин μ1, μ2, …, μk.

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

Пример 7. Найдем блочную группу графа , обра­зованную замыканием вершин μ1, μ2, μ3, μ4 графа Г (рис. 5).

Рис. 5. Граф с выделенными ребрами.

Имеем

= и т. д.

и т. д.

Из соотношений (76) и (77) сформулируем следующие следствия.

Следствие 1. Производные блочной группы графа по блочным группам деревьев ее подграфа равны.

Следствие 2. Произведения дополнительной блочной группы графа на блочные группы ее подграфов равны.

П р и м е ч а н и е. Здесь подграф — связная часть графа, не имеющая общих ребер с его остальной частью.

В случае замыкания всех v вершин графа Г блочная группа A(v-1) равна

(79)

где Ki — произвольный столбец блочной группы А, а дополнительная блочная группа равна

где α1, α2, . . ., α g — обозначения всех ребер графа Г.

7.6. Блочная группа разомкнутого графа

Из формулы для блочной группы А графа Г

A =P1P2 . . . Pv-1,

где Рi — однострочная блочная группа, состоящая из обо­значений всех ветвей, инцидентных вершине μі, непосредственно следует, что блочная группа разомкнутого графа, полученная из графа Г отсоединением от произвольной вершины μі одного конца ребра α, равна

А = А [α] = (80)

где А — блочная группа неразомкнутого графа Г; дополни­тельная же блочная группа равна

Adα =, (81)

где Ad — дополнительная блочная группа Г.

Таким образом, при отсоединении от вершин графа Г по одному концу ребер α1, α2, . . ., αr блочная группа полученного разомкнутого графа имеет вид

(82)

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

(83)

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

Рассмотрим деление вершины графа.

Пример деления вершины μ графа Г приведен на рис. 6.

Рис. 6. Деление вершины графа: а) исходный граф; б) граф с разделенной вершиной.

Пусть ребра α1, α2, . . ., αi, αj, . . ., αр инцидентны верши­не μ. Осуществим деление вершины на две вершины μ1 и μ2 так, что вершине μ1 остаются инцидентны ребра α1, α2, . . ., αi, а вершине μ2 — αj, . . ., αр. Согласно правилу сечения графа,

А [α1, α2, . . ., αi, αj, . . ., αр] = 0,

т. е.

A [α1, α2, . . ., αi] = A [αj, . . ., αр].

Следовательно, подобно случаю отсоединения одного конца ребра, для блочной группы графа с разделенной вершиной μ = μ1+μ2 имеем

= A [α1, α2, . . ., αi] = A [αj, . . ., αр], (84)

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

= (85)

Пример 8. Для графа, изображенного на рис. 6, б, имеем

= A [α1α2α3]= A [α4α5], =

где A (Ad) — блочная (дополнительная) группа графа, представ­ленного на рис. 6, а.

7.7. Преобразование графа

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

а) соединение двух графов; .

б) отделение части графа;

в) перемещение части графа.

а) Соединение двух графов

Пусть даны два графа Г1 и Г2 (рис. 7, а), для которых известны блочные группы A1 и А2.

Рис. 7. Поочередное соединение вершин двух графов.

Соединим эти два графа, объединяя пары вершин: μ11 с μ21, μ12 с μ21, μ13 с μ23 и μ14 с μ24.

Соединив вершины μ11 и μ21, получим связный граф с одной общей точкой μ11 + μ21 (рис. 7, б), блочные группы которой равны

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

.

Соединив вершины μ12 и μ22 (рис. 7, в), получим граф, блочная группа которого

где — произвольный путь графа Г1 между вершинами μ11 и μ12, а — произвольный путь графа Г2 между верши­нами μ21 и μ22.

Соединяя пары вершин μ13 с μ23 и μ14 с μ24, окончательно получим граф Г, состоящий из двух подграфов Г1 и Г2 (рис. 7, г), блочная группа которого имеет вид

Аналогично можно поступить и при большем числе объединяе­мых вершин нескольких графов.

б) Отделение части графа (подграфа)

Рассмотрим отделение от графа Г его части (подграфа) Г2 (рис. 8, а). В результате получим граф Г1 (рис. 8, в).

Рис. 8. Поочередное отделение части графа.

Если вершине μ21 подграфа Г2 инцидентны ребра этого под­графа α211, α212, . . ., α21m1, а вершине μ22— ребра α221, α222, . . ., α22m2 , причем