Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Артикул: 472559.02.99
Доступ онлайн
2 200 ₽
В корзину
Предложен единый подход к определению таких понятий, как ультраграф, гиперграф, ориентированный и неориентированный граф, и рассмотрено использование аппарата теории графов для разработки моделей структур сложных систем, а также постановка задач их синтеза и способы снижения вычислительной сложности алгоритмов на графах. Выполнен анализ ряда задач проектирования сложных систем, выявлены их общие признаки и характерные особенности. Для студентов, обучающихся по специальностям, связанным с информатикой. Может быть полезна преподавателям и аспирантам, а также специалистам, работающим в данной области.
Овчинников, В. А. Графы в задачах анализа и синтеза структур сложных систем : монография / В. А. Овчинников. - Москва : МГТУ им. Баумана, 2014. - 424 с. - ISBN 978-5-7038-3890-7. - Текст : электронный. - URL: https://znanium.com/catalog/product/2015357 (дата обращения: 29.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
В. А. ОВЧИННИКОВ

ГРАФЫ

 

В

 

ЗАДАЧАХ

АНАЛИЗА

 

И

 

СИНТЕЗА

СТРУКТУР

 

СЛОЖНЫХ

 

СИСТЕМ

Москва 

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. Изображение ребер ультраграфа в виде контуров (а) и линий (б)

Доступ онлайн
2 200 ₽
В корзину