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

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

Рис. 20. Деревья второго ранга модуль-графа: а) деревья гра­фа рис. 19, а; б) обобщенные деревья скелета графа рис. 9, б.

Если предположить, что двухполюсные модули графа Г (рис. 19, а) — ребра, то деревья второго ранга этого линей­ного графа будут изоморфны обобщенным деревьям скелета Го, два из которых приведены на рис. 20, б. Блочные группы А и Ad для линейного графа, изоморфного его скелету (рис. 19, б), соответственно равны

так как и т. д;

так как и т. д.

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

7.8.4. Модуль-граф с выделенными элементами

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

Рассмотрим несколько примеров.

а. Граф с выделенными ребрами (рис. 21)

На рис. 21 изображен граф Г с выделенными ребрами α, β и γ. Обозначим через А1 блочную группу этого графа без ребер α, β и γ, а через А блочную группу графа Г с этими ребрами.

Рис. 21. Модуль-граф с выделенными ребрами: а) граф;

б) скелет графа.

Представим граф Г в виде модуль-графа, состоящего из 4 модулей: шестиполюсного модуля Г1 (граф Г без ребер α, β и γ) и двух­полюсных модулей α, β и γ. Скелет Г0 этого графа приведен на рис. 21, б. В скелете Г0 дерево модуля Г1 состоит из путей а, b, с, d и е. Дополнительная блочная группа Ad0 скелета Г0 равна

Блочная группа второго ранга 2А графа Г имеет вид

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

Если ребра α, β и γ образуют контур (треугольник), то

В этом случае блочная группа графа Г

где — блочная группа графа, представляющая

собой контур (треугольник), состоящий из ребер α, β и γ. Дополнительная блочная группа этого графа равна

где

Тот же результат получим, непосредственно рассчитав блочную группу и дополнительную блочную группу графа Г (рис. 22, а). Скелет этого графа показан на рис. 22, б.

Рис. 22. Модуль-граф с вы­деленными ребрами, обра­зующими цикл: а) граф; б) скелет графа.

Граф, состоящий из ребер α, β и γ, обозначим через Г∆, где блочная группа А∆ равна

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

Аd∆=[αβγ].

Для графа Г, состоящего из двух модулей, имеем

Так как этот результат совпадает с полу­ченным ранее. Дополнительная блочная группа графа Г имеет вид

На основании правила формирования контурного графа имеем

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

Рис. 23. Модуль-граф с выделенными двумя ребра­ми: а) граф; б) скелет графа.

Для графа Г с двумя выделенными ребрами α и β (рис. 23, а) блочную группу А и дополнительную блочную группу Ad найдем следующим образом:

(согласно скелету Г0, изображенному на рис. 23, б),

б. Граф с выделенной вершиной (рис. 24, а)

Граф Г (рис. 24, а) представим в виде графа, состоящего из двух модулей Г1 и графа Г w, блочная группа которого равна

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

A dw=[Ø]=1.

Рис. 24. Модуль-граф с выделенной верши­ной: а) граф, б) скелет графа.

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

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

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

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

7.8.5. Преобразования модуль-графов

Каждому преобразованию модуль-графа Г, состоящему из замы­кания или деления его вершин, можно поставить в соответствие определенное преобразование его скелета Г0; например, замыка­нию вершин модуль-графа Г соответствует замыкание вершин его скелета Г0. Если обозначить через Ар блочную группу преобра­зованного графа Гр, а — дополнительную блочную группу соответствен­но преобразованного скелета графа ГСр, то можно написать

(101)

и аналогично

(102)

где А1, А2, ..., Ag (Ad1, Ad2, ..., Adg) — блочные (дополнитель­ные) группы модулей непреобразованного графа Г.

Заметим, что в преобразованном скелете Г0р преобразованные модули в общем случае не соответствуют их деревьям.

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

Для иллюстрации этого метода рассмотрим два вида преобра­зований модуль-графа: а) замыкание вершин графа, б) деление вершин графа.

а. Замыкание вершин модуль-графа

Используя формулу (77) для дополнительной блочной группы графа , образованного замыканием вершин μ1, μ2, . . ., μk в графе Г, для блочной группы и дополнительной блочной группы модуль-графа с замкнутыми вершинами μ1, μ2, . . ., μk можно написать

= (103)

= (104)