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

где *z(р) — блочная группа закороченного графа Г*z(р), 'z(р) — полная блочная группа графа Г2(р).

Число элементов а′і в отдельных столбцах блочной группы 'z(р) равно

vz — р — 1.

Если предположить, что

*z(р) z(р) ,

то элементы блочной группы z(р) можно записать в виде

(8.54)

Для p = vz — 2 имеем

(8.55)

Выразив аk(р) с помощью , получим

(8.56)

Полагая

*z(р) = z(р) А(р) (8.57)

(где А(р)) — блочная группа графа Г(р), полученная в результате замыкания выделенных вершин графа Г таким образом, что их блочная группа уменьшилась на р), выражение (8.56) можно записать в виде

(8.58)

где

Аvz-1.

Величина аk(р) — дендритный вес ребра αk замещающего гра­фа Гz(р). Из выражения (8.58) следует, что дендритные веса ребер замещающего графа зависят от порядка р замыкания графа Г.

Определим далее дендритный вес с помощью блочной группы графа Г.

Пусть ребра α1, α2, . . ., αg графа Гz одновременно обозна­чают произвольные пути в графе Г, соединяющие его соответствующие выделенные вершины. Выберем в графе Гz произволь­ный элементарный цикл, включающий все vz вершин этого графа (так называемый гамильтоновский цикл) и состоящий из ребер

α1, α2, . . ., αk, . . .,

Этот цикл изображен на рис. 8.2.

Рис. 8.2. Цикл Гамильтона.

Рассматривая графы и , на основании формул (8.51) и (8.55) можно написать сле­дующие соотношения:

(8.59)

где αk-1, αk, — обозначения всех ребер графа Гz, инцидентных вершине μ1 (рис. 8.2).

Аналогично можно написать

(8.60)

где αk, αk+1,— обозначения всех ребер графа Гz, инцидентных вершине μ2 (рис. 8.2). Кроме того,

(8.61)

Решив систему уравнений (8.59) — (8.61), получим выражение для дендритного веса ребра αk замещающего графа

(8.62)

где А— блочная группа графа Г:

Чтобы упростить запись, примем обозначение

(8.63)

Тогда формула (8.62) для дендритного веса ребра αk примет вид

(8.64)

Причем

,

На основе правила для циклов

(8.65)

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

касающегося всех вершин графа Гz, кроме вершин μ1 и μ2 ребра αk (рис. 8.2).

Рассмотрим два утверждения, относящиеся к дендритному весу ребра αk графа .

Утверждение 8.2. Дендритный вес ребра αk замещающего графа для произвольного графа Г представляет собой полную топологическую блочную группу

Доказательство. Замещающий граф с замкнутыми ребрами

α1, α2, . . ., αk, . . .,

гамильтоновского цикла (рис. 8.2) имеет в своем составе цикл, состоящий из ребер αk—1, αk+1, для которого правило циклов принимает вид

, (а)

где А — блочная группа графа Г, а рассчитывается по формуле (8.65). Разделим блочную группу из выражения (а) на 23 — 1=7 частей X1,X2, . . ., Х7, не содержащих идентич­ных столбцов:

(Xi∩Xj = 0), i≠j, М = (1, 2, ..., 7), (б)

и составим из них следующую таблицу:

На основании этой таблицы выражение (а) можно записать

[X1X2X3X5]+[X1X2X4X5]+[X1X3X4X7]= =[X1X5X6X7]=0.

Из условия (б) следует

X1 =X5=X6=X7=0.

В результате получим следующую систему уравнений:

где

Решив эту систему уравнений с тремя неизвестными, получим

(в)

и аналогичные выражения для

Поскольку Х2, Х3 и X4 — части блочных групп они представляют собой поло­жительные блочные группы, и выражение (в), идентичное выражению (8.64) для дендритного веса , также является положительной полной блочной группой, что и требовалось доказать.