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

μ21=[ α211α212 . . . α21m1]

μ22=[ α221α222 . . . α22m2]

то, согласно правилам разделения вершин графа, блочная группа графа, полученная разделением вершин μ1 и μ2 графа Г (рис. 8, б), равна

A[μ12] [μ22] (или A[μ11] [μ21]) (а)

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

(или ) (б)

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

Граф (рис. 8, б) имеет одну общую вершину, поэтому его блочную группу можно представить в виде произведения блочных групп А1 и А2, а его дополнительную блочную группу — в виде произведения дополнительных блочных групп Ad1 и Ad2. Так как оба подграфа Г1 и Г2 не имеют общих ребер, т. е.

а

где D 2 — блочная группа произвольного дерева подграфа Г2, a Dd2 — блочная группа произвольного дополнения дерева подграфа Г2, то

и

Заменив в этих равенствах произведения A1A2 и Ad1Ad2 выра­жениями (а) и (б), получим

(или ),

(или )

В общем случае, когда подграфы Г1 и Г2 соединены р вер­шинами, последние выражения принимают вид

(или ), (86)

(или ) (87)

Пример 9. Найдем блочную группу графа Г (рис. 9) при отключении узла μ с инцидентными ребрами 1, 2, 3.

Рис. 9. Граф с выде­ленной вершиной μ.

Согласно выражениям (86) и (87), имеем

(так как Dd2 = 1).

в) Перемещение части графа (подграфа)

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

Рис. 10. Перемещение подграфа Г1

Блочная группа графа, полученная в результате перемещения подгра­фа Г1, рассчитывается следующим образом: сначала определяется блочная группа графа Г2 после отключения подграфа Г1 от графа Г; затем присоединяется подграф Г1 к другим вершинам графа Г2 и находится блочная группа образованного таким образом графа, при этом используются формулы из приме­ров а) и б).

Для иллюстрации этого метода приведем пример пере­мещения ребра α графа Г (рис. 11).

Рис. 11. Перемещение ребра α.

Блочная группа графа Г с отключенным от вершин μ1 и μ2 ребром α, согласно соотношениям (86), равна

После присоединения конца отключенного ребра α к новой вер­шине μ'1 графа Г его блочная группа будет равна

Если присоединить другой конец ребра α к вершине μ'2, то

где — произвольный путь графа Г между вершинами μ'1 и μ'2, а А' — блочная группа графа Г с перемещенным ребром α.

7.8. Графы второй категории (модуль-графы)

7.8.1. Определение модуль-графа

Если определить связный граф Г как упорядоченную тройку

Г=<Р, U, ε> (88)

(где Р — множество вершин графа Г, U — множество ребер графа Г, ε — двухаргументное соотношение инциденции) и выде­лить в этом графе его связную часть

Г1 = <P1, U1, ε 1>,

а оставшуюся часть (необязательно связную) определить как

Г2 = <Р2, U2, ε2>,

то для подграфа Г1 графа Г можно записать следующее опре­деление.

Определение 7. Подграф Г1 = <P1, U1, ε 1> графа Г=<Р, U, ε> есть связная часть графа Г, удовлетворяющая вместе с остальной частью Г2 = <Р2, U2, ε2> этого графа следующим условиям:

(89)

где Pk P1; — множество концов (выделенных вер­шин) подграфа F1.

Граф может состоять из большого числа g подграфов, для которых выполняется соотношение

{i, j (Ui ∩ Uj =0)} (Ui = U) ( Pi =Р)

(εi = ε) {j i (Рi∩Рj≠0)}, i, j=l,2, ...,g. (89а)

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

Г=<P,Z,ε>, (90)

где Р — множество вершин графа, Z — множество модулей, ε — многоаргументное соотношение инциденции.

Рис. 12 иллюстрирует способ изображения модуль-графов.

Рис. 12. Примеры модyль-графов.

На рис. 12, а модуль Г1 четырехполюсный, а модули Г2 и Г3 трех-полюсные; на рис. 12, б модули Г1 и Г5 трехполюсные, модуль Г2 двухполюсный, а двухполюсные модули Г3 и Г4 образуют ребра (одномерные континуумы). Если все модули — одномерные кон­тинуумы и соотношение ε инциденции есть функция двух аргу­ментов, то получаем линейный граф (первого ранга); его модули представляют собой ребра. Следовательно, линейный граф — лишь частный случай модуль-графов. Любой линейный граф можно преобразовать в модуль-граф, заменив каждое его ребро двумерным, двухполюсным модулем. Можно поступить и наоборот, т. е. модуль-граф преобразовать в линейный граф, заменив каждый его модуль линейным графом (подграфом).

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

7.8.2. Блочная группа модуль-графа

Модули Г1, Г2, .... Гg модуль-графа представляют собой под­графы, блочные группы которых обозначим через А1,А2,…...,Ag, а дополнительные блочные группы — Ad1, Ad2, .... Adg. Найдем блочную группу А и дополнительную блочную группу Ad модуль-графа с помощью блочных групп его модулей А1, А2, ….. ., Ag или их дополнительных блочных групп Ad1, Ad2, .... Adg. С этой целью введем понятие скелета модуль-графа.

Определение8. Скелетом Г0 модуль-графа Г называется граф, полученный в результате замены каждого модуля Гk графа Г деревом Dk, составленным из отрезков, соединяющих полюсы и касаю­щихся всех полюсов модуля. Ребра дерева Dk соответствуют про­извольным путям между полюсами модуля Гk.