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

Из приведенной таблицы также следует, что

(8.66)

или в явном виде

(8.67)

где — блочная группа произвольного дерева, касающегося всех вершин графа Гz, кроме вершины μ1, инцидентной ребру αk;

— блочная группа произвольного дерева, касающегося всех вершин графа Гz, кроме вершины μ2, инцидентной ребру αk.

Таким образом, дендритный вес ребра αk замещающего графа можно рассчитывать двумя способами: либо по формуле (8.64), либо по формуле (8.67).

Утверждение 8.3. Дендритные веса и двух произ­вольных ребер αk и αl замещающего графа не имеют оди­наковых столбцов, т. е.

k≠l, k,l=1,2,...,g. (8.68)

Доказательство. Ребра αk и αl могут быть расположены в гра­фе Гz двумя способами:

1) αk, αl μi, где μi — произвольная вершина графа Гz;

2) (αk μj) (μi≠ μj).

В первом случае используем формулу (8.59), которая при­менительно к произвольной вершине μi графа Гz запишется в виде

, (8.69)

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

касающегося всех вершин графа Гz, кроме вершины μi.

Это равенство означает, что сумма дендритных весов (как полных блочных групп) всех ребер, инцидентных верши­не μi, равна блочной группе закороченного графа .

Так как блочная группа не содержит идентичных столбцов (а согласно утверждению 8.2, все полные блочные группы положительны), то из формулы (8.69) для них можно написать равенство (8.68).

Для случая расположения ребер ak и аl в графе Гz по второму способу применим формулу (8.61), которую запишем в виде

(8.70)

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

касающегося всех вершин графа Гz, кроме вершин μk и μl, инци­дентных ребру αj; — сумма дендритных весов (как полных блочных групп ) всех ребер сечения графа Гz топо­логической сферой р, охватывающей только вершины μi и μj (рис. 8.3).

Рис. 8.3. Сечение замещающего графа топологической сферой р, охватывающей вершины μi и μj.

На основании равенства (8.70) по тем же соображениям, что и в первом случае, для всех можно написать равен­ство (8.68),

Так как в полном графе Гz для произвольных вершин μi и μj всегда существует ребро αj, соединяющее их, то среди ребер αр сечения р существуют ребра αk и αl, т. е. то, что и требовалось доказать.

Равенство (8.68) можно переписать следующим образом:

. (8.71)

Утверждения 8.2 и 8.3 справедливы также и для дендритных весов ak(p), рассчитанных по формуле (8.58).

Если обозначить через "z(p) полную блочную группу заме­щающего графа Г z(p), полученную путем замены ребер αі на дендритные веса , то на основании формулы (8.58) блочную группу А(р) графа Г(р) можно записать

А(р) (8.72)

Проиллюстрируем метод расчета дендритных весов ребер заме­щающего графа Гz.

Пример 8.3. Рассчитаем дендритные веса ребер замещающего графа с четырьмя вершинами Fz (рис. 8.4, б) для графа Г (рис. 8.4, а).

Рис. 8.4.

Запишем блочную группу А графа Г

.

Из формулы (8.67)

и, следовательно,

Аналогично рассчитаем дендритные веса остальных ребер гра­фа Гz(2); в результате получим

Отсюда следует, что

i≠j, i,j=1,2,...,6.

Теперь рассчитаем дендритные веса ребер замещающего графа Гz(p). Для этого вначале вычислим блочную группу . Выбираем дерево графа Гz, состоящее из путей α1, α2 и α3. Имеем

[α1] [α2] [α3] = [1 4] [1 2] [2 3] =

Поэтому

= А(3)= = [3 2 4 1].

В соответствии с формулой (8.58)

а k(p)=< а k(2)><1 2 3 4> (р-2)/(3-р)

Для р = 0 (незамкнутый граф) имеем

а k=< а k(2)><l 2 3 4>-2/3,

откуда, например, при k=1

а 1= <l 2 3 4>-2/3.

Для проверки полученных результатов рассчитаем блочную группу графа Г, используя дендритные веса аk графа Гz. C этой целью определим полную блочную группу графа Гz, выражен­ную через обозначения его ребер αi:

и далее заменим все элементы αi на дендритные веса аi . Получим

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

Пример 8.4. Рассчитаем дендритные веса а1(1), а2(1), а3(1) ребер αь α2, α3 замещающего графа Гz (рис. 8.5, б) для графа Г, изображенного на рис. 8.5, а.