BC/NW 2009; №2 (15):4.2

МНОЖЕСТВО ОПЕРАЦИЙ ПРЕОБРАЗОВАНИЯ СТРУКТУР

Акчурин Р.М., Старичкова Ю.В., Шаграев А. Г.

(ГОУВПО «Московский энергетический институт (технический университет)», Россия)

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

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

В данной работе проводится доказательство полноты набора операций по преобразованию структур, предложенных в работе [1].

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

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

Самое простое определение, которое может быть вложено в понятие преобразования структуры, такое: операция – это некоторая всюду определенная функция . Определенную так операцию будем называть операцией типа 1.

Безусловно, операции мыслимы и над несколькими графами, поэтому для большей общности нужно считать операцией по преобразованию структур (графов) любую функцию . Например, операция объединения структур – функция, определенная на декартовом квадрате Г. Так определенную операцию будем называть операцией типа 2.

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

Полнота набора функций в классе операций типа 1.

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

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

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

Утверждение 1. Оператор корректно определен.

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

База индукции. Докажем, что оператор определен корректно. Это проверяется непосредственно: .

Предположение индукции. Предположим, что оператор определен корректно.

Шаг индукции. Пусть дан произвольный граф . Выберем любые вершины . Рассмотрим следующие индуцированные подграфы G:

Тогда

Если , то H = G. Тогда

Если же , то . Тогда

.

Утверждение 1 доказано.

Утверждение 2. Оператор корректно определен.

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

Утверждение 3. Оператор корректно определен.

В самом деле, например, .

Пусть теперь дана некоторая операция типа 1, то есть функция . Рассмотрим функцию , такую, что , коль скоро . В таком случае, очевидно, имеем . Но функция g’ представляется по своему определению суперпозицией операций. Значит, функция g может быть представлена суперпозицией операций.

Утверждение 4. Набор операций является полным в классе операций типа 1.

Достаточность операций по преобразованию структур.

Всюду далее полагаем, что граф , граф .

Достаточно просто понять, что операции могут быть описаны через следующие операции:

Добавление вершины к графу

, где , .

Добавление ребра к графу

, где , .

Удаление вершины из графа

, где , .

Удаление ребра из графа

, где , .

Для простоты введем следующие инфиксные записи этих операций:

,

,

,

.

При этом естественно определяются операции добавления или удаления множеств вершин или ребер.

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

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

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

Добавление вершины: .

Присоединение ребра: .

Удаление ребра: .

Удаление вершины: ,

где .

Доказана полнота набора операций по преобразованию структур.

Выделен базис операций 1, 4, 5, 11 из набора операции операций по преобразованию структур, достаточный для того, чтобы построить весь набор. Независимость набора операций 1, 4, 5, 11 очевидна. В то же время, вопрос о минимальности этого базиса остается открытым. Эти четыре введенные операции являются с теоретико-графовой точки зрения более естественными, тогда как использование операций оправдано с точки зрения прикладной области. Поэтому естественно в теоретических исследованиях пользоваться набором операций, а в прикладных задачах – набором 1, 4, 5, 11.

Разработан программный продукт «Structure editor», позволяющий проводить операции по изменению структур.

Литература

1. Акчурин Р.М. Разработка метода совершенствования сложных информационных систем на основе многоуровневого структурного анализа (автореферат диссертации). М., МЭИ, 1984. 24 стр.