Графы в задачах анализа и синтеза структур сложных систем

В. А. ОВЧИННИКОВ

ГРАФЫ

 

В

 

ЗАДАЧАХ

АНАЛИЗА

 

И

 

СИНТЕЗА

СТРУКТУР

 

СЛОЖНЫХ

 

СИСТЕМ

Москва 

2014

УДК 004+519.1
ББК 22.176
 
О-35

Рецензенты:

декан факультета информационных технологий МГТУ МИРЭА,

доктор технических наук, профессор А.Б. Петров;

генеральный директор ЗАО «РТСофт», 
доктор технических наук О.В. Синенко

Овчинников В.А.

О-35  
Графы в задачах анализа и синтеза структур сложных систем / 

В. А. Овчинников. ― М. : Изд-во МГТУ им. Н. Э. Баумана, 2014. ― 
423, [1] с. : ил.

ISBN 978-5-7038-3890-7

Предложен единый подход к определению таких понятий, как ультраграф, 

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

Выполнен анализ ряда задач проектирования сложных систем, выявлены их 

общие признаки и характерные особенности.

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

УДК 004+519.1
ББК 22.176

© Овчинников В.А., 2014
© Оформление. Издательство 

ISBN 978-5-7038-3890-7 
МГТУ им. Н.Э. Баумана, 2014

ВВЕДЕНИЕ

Задачи структурного синтеза возникают при разработке практически 

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

Успешное решение задач синтеза и анализа структур сложных систем не
возможно без их формализации. При решении таких задач в качестве аппарата 
формализации объектов проектирования широко применяется теория графов. 
Использование для формального описания объекта проектирования графа 
определенного вида – обыкновенных неориентированного и ориентированного, гипер- и ультраграфа должно обеспечивать:

• получение моделей, адекватных объекту в смысле полноты и правильности 

отображения информации, которая требуется для решения проектной задачи;

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

Аппарат теории графов хорошо развит, определены операции на графах, 

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

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

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

Недостаточно проработаны вопросы получения моделей алгоритмов и их 

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

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

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

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

Устранению указанных пробелов и посвящена предлагаемая книга.
В первой главе автор предлагает единый подход к определению понятия 

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

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

Введение

В третьей главе сформулированы требования к математическим моделям 

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

Четвертая глава посвящена операциям над ультра- и гиперграфами. 

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

В пятой главе обоснована необходимость разработки информационно-ло
гической модели алгоритма. Такая модель должна обеспечивать возможность 
автоматизации оценки вычислительной и емкостной сложности, выполнения 
оптимизирующих преобразований и проверки правильности его трансляции. 
Определен элементарный базис структуры алгоритма, а также другие его компоненты, связи между ними, характеристики компонентов и свойства связей, 
которые должны быть отражены в модели. Сформулированы правила перехода от алгоритма к его моделям в виде управляющего графа и графа «операторы – данные». Показаны уграф класса алгоритмов, граф «операторы – данные» 
и интегральная – информационно-логическая модель.

С использованием принятого элементарного базиса получены формальное 

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

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

Определены отношения на записях множеств, которые необходимы для 

получения моделей структур данных и их формального синтеза. Рассмотрены 

Введение

модели этих отношений. Сформулированы требования к моделям структур 
данных, приведены правила перехода от различных, в том числе двухуровневых и комбинированных, структур данных к их моделям в виде ориентированных графов. Даны оценки емкостной сложности реализации ряда структур и вычислительной сложности выполнения основных операций над ними. 
Рассмотрен пример синтеза комбинированной структуры данных для алгоритма разрезания гиперграфа. Изложена методика формального синтеза многоуровневых комбинированных структур данных.

В седьмой главе рассмотрены проектные операции и процедуры решения 

задач структурного синтеза и их реализация при аналитическом представлении графов. Приведены алгоритмы выполнения операций теории множеств 
структурными конструкциями в элементарном базисе алгоритмов. Указаны 
оценки их временной сложности «в лучшем», «в среднем» и «в худшем». Этот 
материал создает предпосылки для автоматизированной оценки функциональной вычислительной сложности алгоритмов.

Рассмотрены особенности реализации операций над упорядоченными 

множествами. Разработаны алгоритмы их выполнения. Даны оценки суммарного количества сравнений, требуемых для предварительного упорядочивания 
множеств и выполнения операций. Приведены формулы для определения степени сокращения вычислительной сложности операций над множествами за 
счет их упорядочивания. На примере последовательного алгоритма разрезания гиперграфа показана высокая эффективность использования операций над 
упорядоченными множествами в алгоритмах структурного синтеза.

Описан язык записи алгоритмов операциями теории множеств и матема
тической логики. Рассмотрены примеры применения операций над графами 
в алгоритмах схемно-топологического проектирования. Выполнено расширение указанного языка за счет включения операций над графами. Приведены 
примеры записи алгоритма Краскала в обеих версиях языка. Их сравнение 
показывает, что программа на языке уровня графов позволяет разработчику 
оперировать непосредственно математическими моделями объектов и результатов, однозначно интерпретируя проектные операции над объектами операциями над математическими моделями.

В восьмой главе определено понятие «оптимизирующие преобразования 

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

Книга в значительной степени базируется на оригинальных результатах 

работ по созданию компонент САПР и на курсе лекций, прочитанных автором 
в МГТУ им. Н.Э. Баумана. Автор надеется, что книга будет полезной студентам, обучающимся по специальностям, связанным с проектированием сложных систем, а также научным сотрудникам и аспирантам.

Введение

1. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

«В виде графов можно представлять блок-схемы программ (вершины – 

блоки, а дуги – разрешенные переходы от одного блока к другому), электрические цепи, географические карты и молекулы химических соединений, связи 
между людьми и группам людей» [31].

«Занимаясь статистической механикой, Уленбек обозначал точками (вер
шинами) молекулы, а смежность вершин толковал как взаимодействие наибольшей близости (соседства) некоторого физического типа, например магнитное притяжение или отталкивание» [32].

«Учение о цепях Маркова… связано с ориентированными графами в том 

смысле, что события представляются вершинами, а ориентированное ребро 
(дуга), идущее из одной вершины в другую, указывает на то, что вероятность 
прямого перехода от одного события к другому положительна» [32].

1.1. Общее определение графа

При решении задач структурного синтеза в качестве аппарата форма
лизации объектов проектирования широко применяется теория графов. 
Использование для формализации описания объекта проектирования графа 
определенного вида – неориентированного и ориентированного, гипер- и ультраграфа позволяет:

• разрабатывать модели, адекватные в смысле полноты и правильности 

отображения информации, которая требуется для решения задачи;

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

Аппарат теории обыкновенных графов достаточно развит: определены 

операции на графах, сформулированы теоремы, леммы и т. д., разработано много алгоритмов решения различных задач структурного синтеза. Гиперграфы исследованы мало [14, 15] и еще в меньшей степени исследованы  ультраграфы. 
Автору не известен единый подход к определению понятий обыкновенных, гипер- и ультра-графов, что не позволяет использовать значительные результаты, 
полученные в теории обыкновенных графов, для решения тех задач структур

1. Элементы теории графов

ного синтеза, в которых моделями объектов являются гипер- и ультраграфы. 
В [21] предложен подход, показавший связь между обыкновенными, гипер-, 
ультраграфами, а также приведены формальные правила, связывающие матричное и аналитическое представления для каждого вида графов, и выражения для оценки характеристик компонент графа.

В соответствии с предлагаемым подходом граф – это два непересека
ющихся множества X – вершин и U – ребер, на элементах которых определен трехместный предикат-инцидентор Р(X, U, X ). В такой трактовке граф 
обозначают G = (X, U, Р). Символ «=» в дальнейшем будем для краткости 
 опускать.

Предикат-инцидентор Р является конъюнкцией двуместных предикатов 

инцидентности Г1(X, U) и Г2(U, X ):

Р(X, U, X ) = Г1(X, U) & Г2(U, X ),

Р(xi, uj, xk) = «и» : (Г1(xi, uj) = «и» & Г2(uj, xk) = «и») / xi, xk ∈ X, uj ∈ U.

Предикат Г1(X,U) соответствует такой связи между элементами множеств 

X и U, которая содержательно определяется выражением «вершинам множества X инцидентны ребра множества U», а предикат Г2(U, X ) – «ребрам множества U инцидентны вершины множества X».

Пусть X = {x1, x2, x3}, U = {u1, u2, u3, u4} и предикаты принимают значение 

«истина» на парах

Г1(X, U): (x1, u1), (x1, u2), (x2, u3), (x3, u4);

Г2(U, X ): (u1, x2), (u1, x3), (u2, x2), (u2, x3), (u3, x3), (u4, x1), (u4, x2).

Геометрическое представление предикатов Г1(X, U), Г2(U, X ) и их конъ
юнкции показано на рис. 1.1, а и б. Здесь вершины и ребра изображены кружками, истинность предиката Г1(xi, uj) – стрелкой, идущей от xi к uj, а истинность 
предиката Г2(uj, xi) – стрелкой от uj к xi.

Рис. 1.1. Геометрическая интерпретация предикатов Г1 и Г2 (а), их конъюнкции (б), 
композиции (г) и выражения (1.1) (в)

В соответствии с операцией конъюнкция для всех графов при X ≠ ∅ и 

U ≠  ∅ справедливо следующее:

Г1(xi, uj) = «и» & Г2(uj, xk) = «и» ∨ Г1(xi, uj) & Г2(uj, xi) = «и». 
(1.1)

Положим X = {x1, x2}, U = {u1}, тогда, изображая вершины кружками, а ре
бра – отрезками дуги, при Г1(x1, u1) = «и», Г2(u1, x2) = «и» и Г1(x1, u1) = «и», 
Г2(u1, x1) = «и» получим геометрическую интерпретацию выражения (1.1), 
представленную на рис. 1.1, в.

На элементах множеств X и U определены также двуместные предикаты 

смежности F1(X, X ) и F2(U, U). Вершине xi смежна вершина xt в том случае, если существует ребро uj, инцидентное вершине xi, такое, что вершина 
xt инцидентна этому же ребру. Ребру uj смежно ребро uk, если существует 
вершина xi, инцидентная ребру uj, такая, что ребро uk инцидентно этой же вершине. Таким образом, понятие смежности вторично по отношению к понятию 
инцидентности.

В соответствии с определением понятия смежности предикат смежности 

вершин графа является композицией предикатов Г1(X, U) и Г2(U, X ):

F1(X, X ) = Г1(X, U) • Г2(U, X ),

где F1(X, X ) = {F1(xi, xt) = «и»: ∃ uj (Г1(xi, uj) = «и» & Г2(uj, xt) = «и») / xi, xt ∈ X, 
uj ∈ U}; • – символ операции композиции (см. рис. 1.1, г).

Аналогично предикат смежности ребер графа является композицией пре
дикатов Г2(U, X ) и Г1(X, U):

F2(U, U) = Г2(U, X ) • Г1(X, U),

где F2(U, U) = {F2(uj, uk) = «и» : ∃ xi(Г2(uj, xi) = «и» & Г1(xi, uk) = «и») / uj, uk ∈ U, 
xi ∈ X }.

Предлагаемая трактовка графов допускает существование в них петель и 

кратных ребер. Вид графа – обыкновенный неориентированный или ориентированный, гипер- и ультраграф – определяется свойствами предикатов инцидентности Г1 и Г2.

Задание графа трехместным предикатом-инцидентором Р(X, U, X ) затруд
няет его анализ и преобразование. В дальнейшем граф будет задаваться через 
предикаты инцидентности Г1, Г2, и смежности F1, F2.

Рассмотрим одноместные предикаты-свойства, производные от преди
катов Г1 и Г2, полученные подстановкой в двуместный предикат некоторого 
определенного элемента того или иного множества.

Зафиксировав в Г1(X, U) некоторую вершину xi ∈ X, получим предикат
свойство Г1xi(U) «вершине xi инцидентны ребра множества U», истинность которого задается i-й строкой матрицы предиката Г1(X, U), а подставив некоторое ребро uj ∈ U, – предикат-свойство Г1uj(X ) «ребро uj инцидентно вершинам 
множества X». Истинность этого предиката определяет j-й столбец матрицы 
предиката Г1(X, U).

1.1. Общее определение графа

1. Элементы теории графов

Зафиксировав в предикате Г2(U, X ) ребро uj, придем к предикату-свойству 

Г2uj(X ) «ребру uj инцидентны вершины множества X», истинность которого задает j-я строка матрицы предиката Г2(U, X ), а подставив вершину xi, предикатсвойство Г2xi(U) «вершина xi инцидентна ребрам множества U». Истинность 
данного предиката задает i-й столбец матрицы предиката Г2(U, X ).

Характеристические множества рассмотренных предикатов-свойств обо
значим через Г1xi, Г1uj, Г2uj, Г2xi, где

Г1xi = Ui

+ = {uj ∈ U : Г1xi(uj) = «и»}, Ui

+ ⊆ U – ребра, инцидентные вершине 

xi ∈ X;

Г1uj = Xj

– = {xi ∈ X : Г1uj(xi) = «и»}, Xj

– ⊆ X – вершины, которым инцидентно 

ребро uj ∈ U;

Г2uj = Xj

+ = {xi ∈ X : Г2uj(xi) = «и»}, Xj

+ ⊆ X – вершины, инцидентные ребру 

uj ∈ U;

Г2xi = Ui

– = {uj ∈ U : Г2xi(uj) = «и»}, Ui

– ⊆ U – ребра, которым инцидентна 

вершина xi ∈ X.

1.2. Ультраграф

Определенный выше граф называется ультраграфом HU(X, U, Г1, Г2), если 

кроме выполнения для всех ребер условия (1) существует хотя бы одно ребро, 
суммарное количество вершин, которым оно инцидентно и которые инцидентны ему, больше двух, т. е.

∃ uj ∈ U (|Г1uj| + |Г2uj|) > 2. 
(1.2)

На рис. 1.2, а показан ультраграф, у которого X = {x1, x2, x3, x4, x5}, U = 

={u1, u2, u3}, причем u3 – петля при вершине x5. При большом количестве ребер 
ультраграфа представление их в виде контуров делает рисунок плохо обозримым. В этом случае ребра целесообразно изображать линиями, как показано 
на рис. 1.2, б.

Для визуального анализа ультраграфа иногда более наглядно его изобра
жение выглядит в виде двудольного графа (графа Кенига). В этом случае ребра, как и вершины, представлены кружками, а истинность предикатов Г1 и Г2 

Рис. 1.2. Изображение ребер ультраграфа в виде контуров (а) и линий (б)