Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Операции над ультра- и гиперграфами для реализации процедур анализа и синтеза структур сложных систем

# 10, октябрь 2009
Файл статьи: Овчинник...ть 1.pdf (308.00Кб)
автор: профессор Овчинников В. А.

1

УДК 004.3 +519.6

МГТУ им. Н.Э. Баумана

gsivanova@gmail.com

 

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

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

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

Для всех операций приведена асимптотическая оценка вычислительной сложности. В результате анализа формального описания результата операции и процесса ее выполнения определялось количество операций сравнения и копирования, необходимых для получения всех множеств аналитического представления ультра/гиперграфа. Использовались известные соотношения O(n) + O(n) = O(n), O(n) × O(n) = O(n2), O(n) + O(n2) = O(n2), O(n) × n = O(n2) и предполагалось, что вычислительная сложность операций сравнения и копирования одинаковы.

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

Для схем ЭВМ, которые являются основными объектами формализации, эти предположения справедливы. Действительно, для ребра ультраграфа uj количество инцидентных ему вершин r+(uj) = |Г2 uj | – это нагрузочная способность элемента, который является источником сигнала для цепи сj « uj. Для подавляющего большинства элементов схем ЭВМ эта величина редко превышает 10…20 и во всяком случае не зависит от количества элементов схемы n.

Сумма числа ребер, инцидентных вершине xi, и ребер, которым инцидентна эта вершина, r+(xi) + r-(xi) = |Г1xi | + |Г2xi | – это количество выходных и входных контактов элемента эi « xi. Этот параметр меняется в зависимости от степени интеграции элементов, используемых для представления схемы на данном этапе проектирования. Его значение не зависит от числа элементов и/или цепей схемы и ограничено константой. Таким образом при разработке алгоритмов решения задач схемно-топологического проектирования средств ЭВТ следует ориентироваться на оценку «в лучшем» вычислительной сложности операций над графами.

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

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

HU (X, U, Г1X, Г2X, Г2U, Г1U, F1X, F1-1X, F2U, F2-1U) – ультраграф и

H (X, U, Г1X, Г2U, F1X, F2U) – гиперграф.

В том случае, когда результат операции должен быть получен в виде неполного представления, в обозначениях преобразуемого графа (преобразуемых графов) и графа результата следует указать те множества, которые должны быть заданы и получены. Например, обозначение результата операции добавления вершины xk в ультраграф, если последний надо получить в форме HU1 (X1, U1, Г1X1, Г2U1), должно иметь вид

HU1 (X1, U1, Г1X1, Г2U1) = HU (X, U, Г1X, Г2U) + xk (Uk+, Uk).

Если указаны только множества вершин и ребер

HU1 (X1, U1) = HU (X, U) + xk (Uk+, Uk),

то в результате операции будет получено полное аналитическое представление HU1 (X1, U1, Г1X1, Г2X1, Г2U1, Г1U1, F1X1, F1-1X1, F2U1, F2-1U1).

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

Таблица 1.

Операция

Соответствующая проектная процедура

Пример

1

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

Добавление в структуру объекта нового компонента

Включение в схему элемента и подключение его к существующим цепям

2

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

Подсоединение фрагмента структуры объекта в процессе его последовательного формирования

Введение в схему новой цепи и подключение ее к заданным элементам

3

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

Удаление из структуры объекта существующего компонента

Удаление из схемы элемента с сохранением в ней цепей, подключенных к нему

4

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

Отключение соединения от компонент объекта

Удаление из схемы существующей цепи

5

Стягивание ребер uf и uk графа

 

Замена выбранных соединений одним

Замена двух цепей одной

6

Подразбиение ребра uk графа

Замена выбранного соединения структуры объекта двумя

Разрыв цепи и подключение двух новых к вводимому элементу.

7

Удаление вершины xk из образов и прообразов нцидентных ей ребер

Отключение компонента от заданных соединений

Отсоединение элемента от определённых цепей

8

Удаление ребра uk из образов и прообразов инцидентных ему вершин

Отключение соединения от заданных компонентов

Отсоединение цепи от определённых элементов

9

Формирование части графа

Выделение фрагмента структуры объекта

Локализация части схемы по заданному множеству элементов

10

Свертка (факторизация) множества Xсв вершин графа

Представление фрагмента структуры объекта одним компонентом

Замена части схемы макроэлементом

 

11

Декомпозиция вершины xсв графа

Замена выбранного элемента структуры объекта фрагментом

Декомпозиция элемента более высокого уровня на множество элементов более низкого уровня

12

Дополнение части до графа или его куска

Удаление из структуры объекта заданного фрагмента

Удаление части схемы

13

Объединение частей графа

Создание одной структуры их двух

Объединение двух схем, имеющих общие элементы и/или цепи.

14

Пересечение графов

Определение общих фрагментов структур объектов при совпадающих индексах их компонент и связей

Выделение в схемах одинаковых частей

 

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

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

Рис. 1. Фрагмент схемы (а), его модель в виде ультраграфа HU и результат выполнения операции HU1 (б), модель в виде гиперграфа H и результат H1 (в)

Задается имя добавляемой вершины xk и множества инцидентных ей ребер Uk+ = Г1xk и ребер, которым она инцидентна Uk = Г2xk, – для ультраграфа или множество инцидентных вершине ребер Uk = Г1xk – для гиперграфа.

Обозначение операции: HU (X, U) + xk (Uk+, Uk) и H (X, U) + xk (Uk) для ультра- и гиперграфа соответственно.

Условия корректности операции: xk Ï X, Uk+, Uk (Uk) Í U.

Результатом выполнения операции является:

ультраграф HU1 (X1, U1) = HU (X, U) + xk (Uk+, Uk) или гиперграф H1 (X1, U1) = H (X, U) + xk (Uk).

Содержательно-формальное описание выполнения операции

над ультраграфом HU (X, U).

Формируем множества вершин, ребер, их образов и прообразов относительно предикатов инцидентности и смежности ультраграфа HU1 (X1, U1). Для чего:

1. Создаем множества X1, Г1X1, и Г2X1, добавляя в X вершину xk, а в Г1X и Г2X подмножества Г1xk и Г2xk соответственно:

X1 = X · xk; Г1X1 = Г1X · Г1xk; Г2X1 = Г2X · Г2xk, где «·» – символ операции конкатенации.

2. Копируем множество U под именем U1: U1 = U.

3. Определяем множество образов ребер Г2U1, занося в него Г2uj из множества Г2U, если ребро uj не принадлежит множеству ребер, которым инцидентна вершина xk, и добавляя вершину xk в образы тех ребер, которым она инцидентна:

Г2U1 = {Г2uj : uj Ï Г2xk Ú 2uj · xk} : uj Î Г2xk uj Î U1, Г2uj Î Г2U}.

4. Формируем множество прообразов ребер Г1U1, занося в него Г1uj из множества Г1U, если ребро uj не инцидентно вершине xk, и добавляя вершину xk в прообразы тех ребер, которые ей инцидентны:

Г1U1 = {Г1uj : uj Ï Г1xk Ú 1uj · xk} : uj Î Г1xk uj Î U1, Г1uj Î Г1U}.

5. Создаем множество образов F1X1 вершин относительно предиката смежности F1(X1, X1), занося F1xi из F1X, если вершина xk не инцидентна ребрам, которые принадлежат образу Г1xi вершины xi, и добавляя в F1xi вершину xk в противном случае. Определяем по выражению (16) из работы [1] вершины, смежные добавляемой, и заносим их в множество F1X1:

F1X1 = {{F1xi Î F1X : Г1xi Ç Г2xk = Æ Ú F1xi · xk : Г1xi Ç Г2xk ¹ Æ xi Î X,

Г1xi Î Г1X} · F1xk},

где F1xk = È Г2uj, Г2uj Î Г2U.

uj Î Г1xk

6. Формируем множество прообразов F1-1X1, занося в него F1-1xi из F1-1X, если вершине xk не инцидентны ребра прообраза Г2xi, и добавляя в F1-1xi вершину xk в противном случае. Определяем по выражению (17) из работы [1] вершины прообраза F1-1xk и заносим его в множество F1-1X1:

F1-1X1 = {{F1-1xi Î F1-1X : Г2xi Ç Г1xk = Æ Ú F1-1xi · xk : Г2xi Ç Г1xk ¹ Æ xi Î X, Г1xi Î Г1X} · F1-1xk},

где F1-1xk = È Г1uj, Г1uj Î Г1U.

uj Î Г2xk

7. Определяем множество образов ребер F2U1, копируя в него F2uj из F2U, если ребро uj не принадлежит множеству ребер, которым инцидентна вершина xk. В противном случае добавляем в F2uj не принадлежащие ему ребра множества Uk+, инцидентные вершине xk:

F2U1 = {F2uj : uj Ï Г2xk Ú F2uj È Uk+ : uj Î Г2xk uj Î U1, F2uj Î F2U}.

8. Создаем множество прообразов ребер F2-1U1, занося в него F2-1uj из F2‑1U, если ребро uj не инцидентно вершине xk. В противном случае добавляем в F2-1uj не принадлежащие ему ребра множества Uk, которым инцидентна вершина xk:

F2-1U1 = {F2-1uj : uj Ï Г1xk Ú F2-1uj È Uk : uj Î Г1xk uj Î U1, F2-1uj Î F2-1U}.

Если не заданы образы и прообразы вершин и ребер ультраграфа относительно предикатов F1(X, X) и F2(U, U), то на основании (16), (17), (18) и (19) из работы [1], они определяются по следующим выражениям:

F1X1 = {F1xi / xi Î X1},

где F1xi = È Г2uj, Г1xi Î Г1X1, Г2uj Î Г2U1;

uj Î Г1xi

F1-1X1 = {F1-1xi \ xi Î X1},

где F1-1xi = È Г1uj, Г2xi Î Г2X1, Г1uj Î Г1U1;

uj Î Г2xi

F2U1 = {F2uj / uj Î U1},

где F2uj = È Г1xi, Г2uj Î Г2U1, Г1xi Î Г1X1;

xi Î Г2uj

F2-1U1 = {F2-1uj / uj Î U1},

где F2-1uj = È Г2xi, Г1uj Î Г1U1, Г2xi Î Г2X1.

xi Î Г1uj

Формальное описание операции над гиперграфом H (X, U).

Выполнение операции над гиперграфом аналогично операции над ультраграфом с учетом свойств задающих гиперграф предикатов инцидентности и смежности (смотри [1]). Множества аналитического представления гиперграфа H1 (X1, U1) будут:

X1 = X · xk; Г1X1 = Г1X · Г1xk;

U1 = U;

Г2U1 = {Г2uj : uj Ï Г1xk Ú 2uj · xk} : uj Î Г1xk uj Î U1, Г2uj Î Г2U},

F1X1 = {{F1xi Î F1X : Г1xi Ç Г1xk = Æ Ú F1xi · xk : Г1xi Ç Г1xk ¹ Æ xi Î X,

Г1xi Î Г1X} · F1xk},

где F1xk = È Г2uj, Г2uj Î Г2U.

uj Î Г1xk

F2U1 = {F2uj : uj Ï Г1xk Ú F2uj È {Uk \ uj} : uj Î Г1xk uj Î U1, F2uj Î F2U}.

Если не заданы образы вершин и ребер гиперграфа H относительно предикатов F1(X, X) и F2(U, U) , то на основании (31) и (32) из работы [1] они определяются по следующим выражениям:

F1X1 = {F1xi / xi Î X1},

где F1xi = È Xj', Xj' = Г2uj \ xi, если |Г2uj | > 1,

uj Î Г1xi

Г1xi Î Г1X1, Г2uj Î Г2U1;

F2U1 = {F2uj / uj Î U1},

где F2uj = È Ui', Ui' = Г1xi \ uj, если |Г2uj| > 1,

xi Î Г2uj

Г2uj Î Г2U1, Г1xi Î Г1X1.

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

Г2U1 = {Г2uj : uj Ï Г2xk Ú 2uj · xk} : uj Î Г2xk uj Î U1, Г2uj Î Г2U}:

– проверка условия uj Ï Г2xk требует максимум |Г2xk| сравнений,

– при благоприятном исходе выполняется копирование |Г2uj| элементов,

– количество благоприятных исходов равно |U1| – |Г2xk|,

– количество противоположных исходов |Г2xk| и при каждом таком исходе происходит копирование |Г2uj| элементов.

Отсюда суммарное количество операций будет

(|Г2xk| + |Г2uj|) ´ (|U1| – |Г2xk|) + |Г2xk| ´ 2uj|.

Оценки сложности формирования множеств аналитического представления ультраграфа приведены в таблице 2. В ней использованы обозначения n = |X| и m = |U|.

Таблица 2.

N п/п

Формируемые

множества

Количество операций сравнения и копирования в функции от мощности обрабатываемых множеств

Мера сложности

формирования множества

1.1.

X1

|X| = n

О(n)

1.2.

Г1X1

|Г1X| ´ |Г1xi|

О(n × m), если |Г1xi| £ m,

О(n), если |Г1xi| £ const*

1.3.

Г2X1

|Г2X| ´ |Г2xi|

О(n × m), если |Г2xi| £ m,

О(n), если |Г2xi| £ const

2.

U1

|U| = m

О(m)

3.

Г2U1

(|Uk| + |Г2uj|) ´ (|U1| -

|Uk) + |Uk| ´ 2uj|

О(m × n), если |Uk| £ m и |Г2u | £ n,

О(m), если |Uk| и |Г2uj| £ const

4.

Г1U1

(|Uk+| + |Г1uj|) ´ (|U1| -

|Uk+|) + |Uk+| ´ 1uj|

О(m × n), если |Uk+| £ m и |Г1uj| £ n,

О(m), если |Uk+| и |Г1uj| £ const

5.

F1X1

(|Г1xi| ´ | Uk| +

|F1xi|) ´ |X|

О(m2 × n), если |Г1xi| и |Uk| £ m,

О(n), если |Г1xi|, |Uk| и |F1xi| £ const

6.

F1-1X1

(|Г2xi| ´ |Uk+| +

|F1-1xi|) ´ |X|

О(m2 × n), если |Г2xi | и |Uk+| £ m,

О(n), если |Г2xi|, |Uk+| и |F1-1xi| £ const

7.

F2U1

(|Uk| + |F2uj|) ´ (|U1| - |Uk|) + (|Uk| + |F2uj| ´ |Uk+|) ´ |Uk|

О(m3), если |Uk|, |Uk+|и |F2uj| £ m,

О(m), если |Uk|,|Uk+| и |F2uj| £ const

8.

F2-1U1

(|Uk+| + |F2-1uj|) ´ (|U1| - |Uk+|) + (|Uk+| + |F2-1uj| ´ |Uk|) ´ |Uk+|

О(m3), если |Uk+|, |Uk| и |F2-1uj| £ m,

О(m), если |Uk+|,|Uk| и |F2-1uj| £ const

* – т. е. не зависит от размера входа операции n и/или m.

Асимптотическая оценка вычислительной сложности данной операции над ультраграфом равна:

·        в худшем О(m3) при m > n, если |Uk|, |Uk+|и |F2uj| или |Uk+|,|Uk| и |F2-1uj| ограничены m, и О(m2 × n) при n > m, если |Г1xi| и |Uk| или |Г2xi| и |Uk+| ограничены величиной m;

·        в лучшем О(m) при m > n или О(n) при n > m, если мощности образов и прообразов вершин и ребер ограничены константой.

Без учета операций формирования образов и прообразов вершин и ребер относительно предикатов смежности асимптотическая оценка вычислительной сложности операции будет равна:

·        в худшем О(m × n), если |Г1xi| или |Г2xi| ограничены величиной m либо 2uj| или1uj| величиной n;

·        в лучшем О(n) при n > m или О(m) при m > n, если |Г1xi|, |Г2xi|, |Г2uj| и1uj| ограничены константой.

Асимптотическая оценка вычислительной сложности этой операции над гиперграфом имеет тот же порядок.

Операция применима к куску ультра- или гиперграфа.

Особенности выполнения операции.

При добавлении вершины xk к куску HUк (Xк, Uк) ультраграфа HU (X, U) ребро ut Î Uкext становится внутренним, если выполняется одно из следующих условий:

ut Î Uk+ & ut Ï Uk & Xt+к · xk = Xt+ & Xtк = Xt,

ut Ï Uk+ & ut Î Uk & Xt+к = Xt+ & Xtк · xk = Xt,

ut Î Uk+ & ut Î Uk & Xt+к · xk = Xt+ & Xtк · xk = Xt,

где Xt+к = Г2ut Î Г2Uк, Xt+ = Г2ut Î Г2U,

Xt–к = Г1ut Î Г1Uк, Xt = Г1ut Î Г1U.

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

Для куска Hк (Xк, Uк) гиперграфа H (X, U) ребро ut Î Uкext становится внутренним, если

ut Î Uk & Xtк · xk = Xt, где Xtк = Г2ut Î Г2Uк, Xt = Г2ut Î Г2U.

При выполнении этого условия для всех ut Î Uкext результатом операции будет гиперграф.

Вырожденный случай операции: при Uk+ = Uk = Æ для ультраграфа и

Uk = Æ для гиперграфа операция приводит к увеличению количества компо-нент связности за счет тривиального HU (xk, Æ) ультра- или H (xk, Æ) гиперграфа.

Пример. Добавим в схему, показанную на рис. 1, а, элемент э5 и подключим его к цепям с1 и с2. При представлении схемы ультраграфом это соответствует добавлению в ультраграф, изображенный на рис. 1, б, вершины x5, такой, что Г1x5 = Æ, Г2x5 = {u1, u2}.

Результатом выполнения операции HU1 (X1, U1) = HU (X, U) + xk (Uk+, Uk) будет ультраграф, заданный множествами:

X1 = {x1, x2, x3, x4} · x5 = {x1, x2, x3, x4, x5}; U1 = {u1, u2};

Г1X1 = Г1X · Г1x5, где Г1x5 = Æ; Г2X1 = Г2X · Г2x5, где Г2x5 = {u1, u2};

Г2U1: Г2u1 = {x2, x3} · x5 = { x2, x3, x5}, Г2u2 = {x3, x4} · x5 = {x3, x4, x5};

Г1U1: Г1u1 = {x1}, Г1u2 = {x2}.

F1X1: F1x1 = {x2, x3} · x5 = {x2, x3, x5}, F1x2 = {x3, x4} · x5 = {x3, x4, x5},

F1x3 = F1x4 = F1x5 = Æ;

F1-1X1: F1-1x1 = Æ, F1-1x2 = {x1}, F1-1x3 = F1-1x5 = {x1, x2}, F1-1x4 = {x2};

F2U1: F2u1 = {u2}, F2u2 = Æ;

F2-1U1: F2-1u1 = Æ, F2-1u2 = {u1}.

При представлении схемы гиперграфом (смотри рис. 1, в) множество ребер, находящихся в отношении инцидентности с вершиной x5, Г1x5 = {u1, u2}, тогда множества вершин, ребер и их образы относительно предикатов инцидентности результата операции H1 (X1, U1, Г1X1, Г2U1) = H (X, U, Г1X, Г2U) + xk (Uk) будут:

X1 = {x1, x2, x3, x4, x5}; U1 = {u1, u2};

Г1X1 = Г1X · Г1x5, где Г1x5 = {u1, u2};

Г2U1: Г2u1 = {x1, x2, x3} · x5 = {x1, x2, x3, x5}, Г2u2 = {x2, x3, x4} · x5 = {x2, x3, x4, x5}.

Добавление ребра uk в ультраграф HU и гиперграф H рис. 2. Реализует проектную операцию подсоединения фрагмента структуры объекта (некоторая связь и один или более компонентов) в процессе его последовательного формирования, например, введение в схему новой цепи и подключения ее к заданным элементам.

Рис. 2. Исходная схема и варианты добавления цепи с3 (а), модель схемы в виде ультраграфа HU и соответствующие результаты операции: ультраграф HU1 и кусок ультраграфа HU1К (б); модель в виде гиперграфа H и результаты операции: гиперграф H1 и кусок H1к (в)

Задается имя добавляемого ребра uk и множества инцидентных ему вершин Xk+ = Г2uk и вершин, которым оно инцидентно Xk = Г1uk, – для ультраграфа или множество инцидентных ребру вершин Xk = Г2uk – для гиперграфа, т. е. Xk+ È Xk « Эk – множество элементов, к которым подключается цепь ck.

Обозначение операции: HU (X, U) + uk (Xk+, Xk) и H (X, U) + uk (Xk) для ультра- и гиперграфа соответственно.

Условия корректности операции: Xk Ç X ¹ Æ, где Xk = Г2uk È Г1uk – для ультраграфа и Xk = Г2uk – для гиперграфа, т. е. в общем случае при добавлении цепи в схему могут быть включены новые элементы (на рис. 2 рассмотрен вариант, для которого Xk Í X). Так как Xk Ç X ¹ Æ, в результате выполнения операции количество компонент связности не изменяется. Если uk Î U и Xk Í X, операция реализует проектную процедуру подключения уже существующей цепи к элементам схемы.

Результатом выполнения операции является:

ультраграф HU1 (X1, U1) = HU (X, U) + uk (Xk+, Xk), если |Xk+| + |Xk| ³ 2, или кусок ультраграфа HU1к (X1к, U1к) = HU (X, U) + uk (Xk+, Xk), если |Xk+| + |Xk| = 1;

– гиперграф H1 (X1, U1) = H (X, U) + uk (Xk), если |Xk| > 1, или кусок гиперграфа H1к (X1к, U1к) = H (X, U) + uk (Xk), если |Xk| = 1.

Содержательно-формальное описание выполнения операции над ультраграфом HU (X, U) при |Xk+|+|Xk| ³ 2.

Для получения ультраграфа HU1 (X1, U1):

1. Создаем множество вершин X1, объединяя множества X и Xk:

X1 = X È Xk, где Xk – то же, что и выше.

2. Определяем множество ребер U1: U1 = U · uk.

3. Формируем множество образов вершин Г1X1:

– записывая в него Г1xi из множества Г1X, если ребро uk не инцидентно вершине xi,

– включая ребро uk в образы вершин, которым оно инцидентно, если эти вершины принадлежат множеству X,

– занося ребро uk в образы тех вершин, не принадлежащих множеству X, которым оно инцидентно,

– записывая в образ вершины значение Æ, если она не принадлежит ни множеству X, ни подмножеству Xk = Г1uk.

Г1X1 = {Г1xi : xi Ï Г1uk & xi Î X Ú 1xi · uk} : xi Î Г1uk & xi Î X Ú uk : xi Î Г1uk & xi Ï X Ú Æ : xi Ï Г1uk & xi Ï Xxi Î X1, Г1xi Î Г1X}.

4. Создаем множество прообразов вершин Г2X1:

– записывая в него Г2xi Î Г2X, если вершина xi не инцидентна ребру uk,

– включая ребро uk в прообразы инцидентных ему вершин, если эти вершины принадлежат множеству X,

– занося ребро uk в прообразы тех вершин, не принадлежащих множеству X, которые ему инцидентны,

– записывая в прообраз вершины значение Æ, если она не принадлежит ни множеству X, ни подмножеству Xk+ = Г2uk.

Г2X1 = {Г2xi : xi Ï Г2uk & xi Î X Ú 2xi · uk} : xi Î Г2uk & xi Î X Ú uk : xi Î Г2uk & xi Ï X Ú Æ : xi Ï Г2uk & xi Ï X xi Î X1, Г2xi Î Г2X}.

5. Формируем множество образов Г2U1 и прообразов Г1U1 ребер:

– копируя Г2uj и Г1uj из Г2U и Г1U, если uj uk;

– объединяя их с подмножествами Xk+ и Xk соответственно, если uj = uk и ребро uk принадлежало ультраграфу HU (X, U);

– записывая множества Xk+ и Xk, если ребро uk не принадлежало ультраграфу HU (X, U):

Г2U1 = {Г2uj : uj uk Ú Г2uj È Xk+ : uj = uk & uk Î U ÚXk+ : uj = uk & uk Ï U uj Î U1, Г2uj Î Г2U} и

Г1U1 = {Г1uj : uj uk Ú Г1uj È Xk : uj = uk & uk Î U Ú Xk : uj = uk & uk Ï Uuj Î U1, Г1uj Î Г1U}.

6. Определяем множество образов вершин F1X1 относительно предиката смежности F1(X1, X1), занося в него:

– образ F1xi из F1X для всех xi Î X, если вершине xi не инцидентно ребро uk, и объединяя F1xi с Xk+ в противном случае,

– для вершины, не принадлежащей множеству X, образом будет множество вершин, инцидентных ребру uk, если оно инцидентно этой вершине, и пустое множество в противном случае:

F1X1 = {{F1xi : xi Ï Г1uk Ú F1xi È Xk+ : xi Î Г1uk xi Î X, xi Î F1X} · F1xj xj Î Xk & xj Ï X}, где Xk = Xk+ È Xk,

ì Г2uk : xj Î Г1uk,

F1xj = í

î Æ : xj Ï Г1uk.

7. Формируем множество прообразов F1-1X1, занося в него:

– для вершины, принадлежащей множеству X, прообраз F1-1xi из F1-1X, если вершина xi не инцидентна ребру uk, и объединяя F1-1xi с Xk в противном случае,

– для вершины, не принадлежащей множеству X, прообразом будет множество вершин, которым инцидентно ребро uk, если вершина инцидентна этому ребру, и пустое множество в противном случае:

F1-1X1 = {{ F1-1xi : xi Ï Г2uk Ú F1-1xi È Xk : xi Î Г2uk xi Î X, xi Î F1-1X} ·

F1-1xj xj Î Xk & xj Ï X}, где Xk = Xk+ È Xk,

ì Г1uk : xj Î Г2uk,

F1-1xj = í

î Æ : xj Ï Г2uk.

8. Определяем множество образов ребер F2U1:

– для ребер множества U копируем F2uj из F2U, если ни одной из вершин, инцидентных ребру uj, не инцидентно ребро uk, т. е. образ Г2uj ребра uj и прообраз Г1uk ребра uk не имеют общих вершин. В противном случае добавляем в F2uj ребро uk;

– для ребра uk по выражению (18) из работы [1] определяем образ и заносим его в F2U1:

F2U1 = {{F2uj : Г2uj Ç Г1uk = Æ Ú F2uj · uk : Г2uj Ç Г1uk ¹ Æ uj Î U, Г2uj Î Г2U, F2uj Î F2U}· F2uk},

где F2uk = È Г1xi, Г1xi Î Г1X.

xi Î Г2uk

9. Создаем множество прообразов ребер F2-1U1:

– для ребер множества U занося в него F2-1uj из F 2-1U, если ни одна из вершин, которым инцидентно ребро uj, не инцидентна ребру uk. В противном случае добавляем в F2-1uj ребро uk;

– для ребра uk по выражению (19) из работы [1] определяем прообраз и заносим его в F2-1U1:

F2-1U1 = {{F2-1uj : Г1uj Ç Г2uk = Æ Ú F2-1uj · uk : Г1uj Ç Г2uk ¹ Æuj Î U, Г1uj Î Г1U, F2-1uj Î F2-1U} · F2-1uk},

где F2-1uk = È Г2xi, Г2xi Î Г2X.

xi Î Г1uk

Если не заданы образы и прообразы вершин и ребер ультраграфа относительно предикатов F1(X, X) и F2(U, U) , они определяются по формулам (16), (17), (18) и (19) работы [1].

В случае, если результатом операции будет кусок ультраграфа HU1к, множества X1к, U1к, Г1X1к, Г2X1к, Г2U1к, Г1U1к, F1X, F1-1X определяются по тем же формулам, что и для ультраграфа, а множество ребер U1к разбивается на подмножества U1кint и U1кext, где U1кint = U, U1кext = {uk}.

Формальное описание операции над гиперграфом H (X, U).

Множества аналитического представления гиперграфа H1 (X1, U1) получаются по формулам:

X1 = X È Xk, где Xk – то же, что и выше; U1 = U È uk;

Г1X1 = {Г1xi : xi Ï Г2uk Ú 1xi · uk} : xi Î Г2uk & xi Î X Ú uk : xi Ï Xxi Î X1, Г1xi Î Г1X};

Г2U1 = {Г2uj : uj uk Ú Г2uj È Xk : uj = uk & uk Î U Ú Xk : uj = uk & uk Ï Uuj Î U1, Г2uj Î Г2U};

F1X1 = {{F1xi : xi Ï Г2uk Ú F1xi È Xk \ xi : xi Î Г2uk xi Î X, F1xi Î F1X} ·

F1xj xj Î Xk & xj Ï X}, где F1xj = Xk \ xj;

F2U1 = {{F2uj : Г2uj Ç Г2uk = Æ Ú F2uj · uk : Г2uj Ç Г2uk ¹ Æuj Î U,

Г2uj Î Г2U, F2uj Î F2U} · F2uk},

где F2uk = È Г1xi, Г1xi Î Г1X.

xi Î Г2uk

Если результатом операции будет кусок гиперграфа H1к, множества X1к, U1к, Г1X1к, Г2U1к, F1X1к, F2U1к определяются аналогично множествам X1, U1, Г1X1, Г2U1, F1X1, F2U1. Множество U1к разбивается на два подмножества U1кint = U и U1кext = {uk}.

Асимптотическая оценка вычислительной сложности этой операции над ультраграфом равна:

·        в худшем О(n3) при n > m, если |Xk| или |Xk+| ограничены n, или О(n2 × m) при m > n, если|Г2uj| и |Xk| или |Г1uj| и |Xk+| ограничены n;

·        в лучшем О(n) при n > m, если |Xk|, |Xk+|, |F1xi| и |F1-1xi| ограничены константой, или О(m) при m > n, если|Г2uj|, |Г1uj|, |Xk|, |Xk+|, |F2uj| и |F2-1uj| ограничены константой.

Асимптотическая оценка вычислительной сложности операции над гиперграфом имеет тот же порядок.

Объектом операции может быть кусок ультра- или гиперграфа. В этом случае результатом будет:

ультраграф HU1 (X1, U1) = HUк (Xк, Uк) + uk (Xk+, Xk), если Uкext = {uk},

Xk+ = Г2uk Î Г2U и Xk = Г1uk Î Г1U , где U – множество ребер ультраграфа, куском которого является HUк (Xк, Uк), или кусок ультраграфа HU1к (X1к, U1к) = HU (X, U) + uk (Xk+, Xk), если не удовлетворяется хотя бы одно из указанных выше условий.

При выполнении операции над куском ультраграфа необходимо определять U1кext и U1кint:

U1кext = Uкext \ {uk}, если Xk+ = Г2uk Î Г2U и Xk = Г1uk Î Г1U или

U1кext = Uкext È {uk}, если не удовлетворяется хотя бы одно из этих условий;

U1кint = U1к \ U1кext.

Полученные результаты легко распространить на кусок гиперграфа.

Вырожденный случай операции: при Xk+ = Xk = Æ для ультраграфа и Xk = Æ для гиперграфа операция приводит к увеличению количества компонент связности за счет тривиального куска HUк (Æ, uk) ультра- или Hк (Æ, uk) гиперграфа.

Пример. Введем в схему, показанную на рис. 2, а, цепь с3 и подключим ее к выходу элемента э1 и входам элементов э2 и э4. При представлении схемы ультраграфом (смотри рис. 2, б) это реализуется операцией добавления ребра u3, у которого Г2u3 = {x2, x4} и Г1u3 = {x1}.

В результате выполнения операции HU1 (X1, U1) = HU (X, U) + uk (Xk+, Xk) получим ультраграф HU1, у которого:

X1 = {x1, x2, x3, x4, x5}; U1 = {u1, u2} È u3 = {u1, u2, u3};

Г1X1: Г1x1 = {u1} · u3 = {u1, u3}, Г1x2 = Æ, Г1x3 = Æ, Г1x4 = {u2}, Г1x5 = Æ;

Г2X1: Г2x1 = Æ, Г2x2 = {u1} · u3 = {u1, u3}, Г2x3 = {u1, u2}, Г2x4 = Æ · u3 = {u3}, Г2x5 = {u2};

Г2U1 = {Г2u1, Г2u2, Г2u3}, где Г2u3 = {x2, x4};

Г1U1 = Г1u1, Г1u2, Г1u3}, где Г1u3 = {x1};

F1X1: F1x1 = {x2, x3} È {x2, x4} = {x2, x3, x4}, F1x2 = F1x3 = F1x5 = Æ, F1x4 = {x3, x5};

F1-1X1: F1-1x1 = Æ, F1-1x2 = {x1}, F1-1x3 = {x1, x4}, F1-1x4 = Æ È {x1} = {x1}, F1-1x5 = {x4}.

F1U1: F1u1 = Æ, F1u2 = Æ.

F1-1U1: F1-1u1 = Æ, F1-1u2 = Æ, F1-1u3 = {u2}.

При введении в схему цепи с3 и подключении ее только к входу элемента э2, т. е. при добавлении ребра u3 такого, что Г2u3 = {x2} и Г1u3 = Æ, результатом операции

HU1к (X1к, U1к, Г1X1к, Г2X1к, Г2U1к, Г1U1к) = HU (X, U, Г1X, Г2X, Г2U, Г1U) + uk (Xk+, Xk) будет кусок ультраграфа HU1к, заданный множествами:

X1к = {x1, x2, x3, x4, x5}; U1к = {u1, u2, u3}, U1кint = {u1, u2}, U1кext = {u3};

Г1X1к: Г1x1 = {u1}, Г1x2 = Æ, Г1x3 = Æ, Г1x4 = {u2}, Г1x5 = Æ;

Г2X1к: Г2x1 = Æ, Г2x2 = {u1} · u3 = {u1, u3}, Г2x3 = {u1, u2}, Г2x4 = Æ, Г2x5 = {u2};

Г2U1к = {Г2u1, Г2u2, Г2u3}, где Г2u3 = {x2};

Г1U1к = {Г1u1, Г1u2, Г1u3}, где Г1u3 = Æ.

Если моделью схемы является гиперграф (смотри рис. 2, в), операция

H1 (X1, U1) = H (X, U) + uk (Xk) добавления ребра u3, такого, что Г2u3 = {x1, x2, x4}, дает результат в виде гиперграфа H1, у которого:

X1 = {x1, x2, x3, x4, x5}; U1 = {u1, u2} È u3 = {u1, u2, u3};

Г1X1: Г1x1 = Г1x2 = {u1} · u3 = {u1, u3}, Г1x3 = {u1, u2}, Г1x4 = {u2} · u3 =

{u2, u3}, Г1x5 = {u2};

Г2U1 = {Г2u1, Г2u2, Г2u3}, где Г2u3 = {x1, x2, x4};

F1X1 : F1x1 = {x2, x3} È {x1, x2, x4} \ x1 = {x2, x3, x4}, F1x2 = {x1, x3} È {x1, x2, x4} \ x2 = {x1, x3, x4}, F1x3 = {x1, x3}, F1x4 = {x3, x5} È {x1, x2, x4} \ x4 = { x3, x5, x1, x2}, F1x3 = {x3, x4}.

F2U1: F2u1 = {u2} · u3 = {u2, u3}, F2u2 = {u1} · u3 = {u1, u3}, F2u3 = {u1} È {u1} È {u2} = {u1, u2}.

При подключении цепи с3 только к входу элемента э2, получаем кусок гиперграфа, который в результате выполнения операции H1к (X1к, U1к, Г1X1к, Г2U1к) = H(X, U, Г1X1, Г2U1) + uk (Xk) будет представлен множествами:

X1к = {x1, x2, x3, x4, x5}; U1к = {u1, u2, u3}, U1кint = {u1, u2}, U1кext = {u3};

Г1X1к: Г1x1 = {u1}, Г1x2 = {u1} · u3 = {u1, u3}, Г1x3 = {u1, u2}, Г1x4 = Г1x5 = {u2};

Г2U1к = {Г2u1, Г2u2, Г2u3}, где Г2u3 = {x2}.

Удаление вершины xk из ультраграфа HU или гиперграфа H рис. 3. Реализует проектную операцию исключения компоненты из структуры объекта, например элемента из схемы.

Рис. 3. Исходная схема и варианты удаления элементов (а), ее модель в виде ультраграфа HU и соответствующие результаты операции: ультраграф HU1 и кусок ультраграфа HU1К (б); ее модель в виде гиперграфа H и результаты операции: гиперграф H1 и кусок гиперграфа H1К (в)

Задается имя удаляемой вершины xk.

Обозначение операции: HU (X, U) – xk и H (X, U) – xk для ультра- и гиперграфа соответственно.

Условие корректности операции: xk Î X.

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

Рис. 4. Исходная схема и она же после удаления элемента э3 (а), модель схемы в виде ультраграфа HU и результат операции – две компоненты связности HU1 и HU2 (б)

Если xk не является расщепляющей вершиной, в результате выполнения операции получаем:

ультраграф HU1 (X1, U1) = HU (X, U) – xk, если

" uj Î 1xk È Г2xk} (|Г2uj| + |Г1uj| > 2), (1)

т. е. у всех ребер, инцидентных вершине xk и которым инцидентна эта вершина, суммарное количество вершин образа и прообраза ребра больше двух (смотри, например, вершину x2 на рис. 3, б);

– кусок ультраграфа HU1к (X1к, U1к) = HU (X, U) – xk, если

$ uj Î 1xk È Г2xk} (|Г2uj| + |Г1uj| = 2), (2)

т. е. среди ребер, инцидентных удаляемой вершине и которым инцидентна эта вершина, есть ребро, суммарное количество вершин образа и прообраза которого равно двум (смотри, например, вершину x3 на рис. 3, б);

– гиперграф H1 (X1, U1) = H(X, U) – xk, если

" uj Î Г1xk (|Г2uj| > 2), (3)

– кусок гиперграфа H1к (X1к, U1к) = H(X, U) – xk, если

$ uj Î Г1xk (|Г2uj| = 2). (4)

Содержательно-формальное описание выполнения операции над ультраграфом HU (X, U), если вершина xk не является расщепляющей и справедливо условие (1).

Аналитическое представление ультраграфа HU1 (X1, U1) получаем в результате выполнения следующих пунктов:

1. Формируем множества X1, Г1X1 и Г2X1, удаляя при копировании из X вершину xk, а из Г1X и Г2X подмножества Г1xk и Г2xk соответственно:

X1 = X \ xk; Г1X1 = Г1X \ Г1xk; Г2X1 = Г2X \ Г2xk.

2. Копируем множество U под именем U1: U1 = U.

3. Создаем множество образов ребер Г2U1, занося в него Г2uj из множества Г2U, если ребро uj не принадлежит множеству ребер, которым инцидентна вершина xk, и удаляя вершину xk из образов ребер, которым она инцидентна:

Г2U1 = {Г2uj : uj Ï Г2xk Ú Г2uj \ xk : uj Î Г2xkuj Î U1, Г2xk Î Г2X,

Г2uj Î Г2U}.

4.     Определяем множество прообразов ребер Г1U1, занося в него Г1uj из множества Г1U, если ребро uj не инцидентно вершине xk, и удаляя вершину xk из прообраза ребра, если оно инцидентно ей:

Г1U1 = {Г1uj : uj Ï Г1xk Ú Г1uj \ xk : uj Î Г1xk uj Î U1, Г1xk Î Г1X,

Г1uj Î Г1U}.

5. Формируем множество образов вершин F1X1 относительно предиката смежности F1(X1, X1), занося в F1X1 образ вершины xi Î X1 из F1X, если вершина xk не смежна вершине xi, и её образ без вершины xk в противном случае:

F1X1 = {F1xi : xk Ï F1xi Ú F1xi \ xk : xk Î F1xi xi Î X1, F1xi Î F1X}.

Примечание 1Если дополнение элемента до множества и проверка принадлежности ему элемента являются операциями языка, в котором реализуются рассматриваемые преобразования, то для уменьшения количества операций формирования F1X1 целесообразно использовать следующую формулу:

F1X1 = {F1xi \ xk xi Î X1, F1xi Î F1X}.

6. Создаем множество прообразов F1-1X1, занося в него прообраз вершины xi Î X1 из F1-1X, если вершине xk не смежна вершина xi, и её прообраз без вершины xk в противном случае:

F1-1X1 = {F1-1xi : xk Ï F1-1xi Ú F1-1xi \ xk : xk Î F1-1 xi xi Î X1, F1-1xi Î F1-1X}

или F1-1X1 = {F1-1xi\ xk xi Î X1, F1-1xi Î F1-1X}.

7. Определяем множество образов ребер F2U1, для чего переписываем в него F2uj из F2U, если вершина xk не инцидентна ребру uj, в противном случае удаляем из F2uj подмножество тех ребер, которые не инцидентны ни одной из вершин множества Г2uj кроме вершины xk:

F2U1 = {F2uj uj Î U1}, здесь

ìF2uj Î F2U : uj Ï Г2xk,

F2uj = í

îF2uj \ Uk¢ : uj Î Г2xk, где Uk¢ = {ut Î Г1xk : Г1ut Ç2uj \ xk} = Æ},

F2uj Î F2U, Г2xk Î Г2X, Г1xk Î Г1X, Г1ut Î Г1U, Г2uj Î Г2U.

Примечание 2 Условие «вершина xk не инцидентна ребру uj» естественным образом формулируется как xk Ï Г2uj. Однако запись условия в таком виде усложняет оценку «в худшем» количества операций, необходимых для определения F2U1. В связи с этим условие xk Ï Г2uj заменено логически эквивалентным uj Ï Г2xk. Аналогично будем поступать и в дальнейшем.

8. Создаем множество прообразов ребер F2-1U1, копируя в него F2-1uj из F2-1U, если вершине xk не инцидентно ребро uj, и удаляя, в противном случае, из F2-1uj подмножество тех ребер, которым не инцидентна ни одна из вершин множества Г1uj кроме вершины xk:

F2-1U1 = {F2-1uj uj Î U1}, здесь

ìF2-1uj Î F2-1U : uj Ï Г1xk, где Г1xk Î Г1X,

F2-1uj = í

îF2-1uj \ Uk² : uj Î Г1xk, где Uk² = {ut Î Г2xk : Г2ut Ç1uj \ xk} = Æ},

F2-1uj Î F2-1U, Г 1xk Î Г1X, Г2xk Î Г2X, Г2ut Î Г2U, Г1uj Î Г1U.

При выполнении условия (2) получаем кусок ультраграфа HU1к (X1к, U1к). Множества X1к, U1к, Г1X1к, Г2X1к, Г2U1к, Г1U1к, F1X1, F1-1X1, F2U1 и F2-1U1 определяются по тем же формулам, что и для ультраграфа HU1 (X1, U1), а множество ребер U1к разбивается на подмножества U1кint и U1кext, такие, что

U1кext = {uj Î 1xk È Г2xk} : (|Г2uj| + |Г1uj|) = 2 ∕ Г2uj Î Г2U, Г1xk Î Г1X, Г2xk Î Г2X}; U1кint = U1к \ U1кext.

Формальное описание операции над гиперграфом H (X, U) при выполнении условия (3).

Множества гиперграфа H1 (X1, U1) (смотри рис. 3, в) будут:

X1 = X \ xk; U1 = U; Г1X1 = Г1X \ Г1xk;

Г2U1 = {Г2uj : uj Ï Г1xk Ú Г2uj \ xk : uj Î Г1xk uj Î U1, Г1xk Î Г1X, Г2uj Î Г2U};

F1X1 = {F1xi : xk Ï F1xi Ú F1xi \ xk : xk Î F1xi xi Î X1, F1xi Î F1X};

F2U1 = {F2uj uj Î U1}, здесь

ì F2uj Î F2U : uj Ï Г1xk, где Г1xk Î Г1X,

F2uj = í

î F2uj \ Uk : uj Î Г1xk, где Uk = {ut Î Г1xk : Г2ut Ç2uj \ xk} = Æ},

F2uj Î F2U, Г1xk Î Г1X, Г2ut Î Г1U, Г2uj Î Г2U.

При выполнении условия (4) получаем кусок гиперграфа H1к (X1к, U1к).

Множества X1к, U1к, Г1X1к, Г2U1к, F1X1к, F2U1к определяются аналогично множествам X1, U1, Г1X1, Г2U1, F1X1, F2U1 гиперграфа H1 (X1, U1). Множество U1к разбивается на два подмножества U1кext = {uj Î Г1xk:|Г2uj| = 2 ∕ Г1xk Î Г1X, Г2uj Î Г2U} и U1кint = U1к \ U1кext.

Если вершина xk является расщепляющей (смотри рис. 4, а) и определены множества вершин Xl некоторой компоненты связности, то остальные множества, например, ультраграфа HUl (Xl, Ul, Г1Xl, Г2Xl, Г2Ul, Г1Ul) будут:

Ul = {uj Î È 1xi È Г2xi } ∕ Г1xi Î Г1X, Г2xi Î Г2X};

xi Î Xl

Г1Xl = {Г1xi Î Г1X xi Î Xl};

Г2Xl = {Г2xi Î Г2X xi Î Xl};

Г2Ul = {Г2uj : uj Ï Г2xk Ú Г2uj \ xk : uj Î Г2xk uj Î Ul, Г2uj Î Г2U};

Г1Ul = {Г1uj : uj Ï Г1xk Ú Г1uj \ xk : uj Î Г1xk uj Î Ul, Г1uj Î Г1U}.

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

Операция может выполняться над куском HUк (Xк, Uк) ультра- или Hк (XкUк) гиперграфа. При этом среди компонент связности может появиться граф (графы) вида G®(Æ, u), если для внешних ребер куска HUк (XкUк) выполняется условие

$ uj Î1xk È Г2xk} (|Г2uj| + |Г1uj| = 1),

или вида G~ (Æ, u), если для внешних ребер куска Hк (Xк, Uк) выполняется условие $ uj Î Г1xk (|Г2uj| = 1).

Пример. Удалим из схемы, показанной на рис. 3, а, элемент э2. При представлении схемы ультраграфом (смотри рис. 3, б) это реализуется операцией удаления вершины x2, у которой Г1x2 = {u2} и Г2x2 = {u1}. Так как

Г2u2 = {x4, x5, x6}, Г1u2 = {x2}, Г2u1 = {x2, x4} и Г1u1 = {x1}, то |Г2u2| + |Г1u2| = 4 и |Г2u1| + |Г1u1| = 3, следовательно условие (1) выполняется.

В результате выполнения операции HU1 (X1, U1) = HU (X, U) – xk получим ультраграф, у которого в соответствии с приведенными выше выражениями:

X1 = {x1, x2, x3, x4, x5, x6} \ x2 = {x1, x3, x4, x5, x6}; U1 = {u1, u2, u3};

Г1X1 = Г1X \ Г1x2 : Г1x1 = {u1}, Г1x3 = {u3}, Г1x4 = Г1x5 = Г1x6 = Æ;

Г2X1 = Г2X \ Г2x2 : Г2x1 = Æ, Г2x3 = {u1}, Г2x4 = Г2x6 = {u2}, Г2x5 = {u2, u3};

Г2U1: Г2u1 = {x2, x3} \ x2 = {x3}, Г2u2 = {x4, x5, x6}, Г2u3 = {x5};

Г1U1: Г1u1 = {x1}, Г1u2 = {x2} \ x2 = Æ, Г1u3 = {x3};

F1X1: F1x1 = {x2, x3} \ x2 = {x3}, F1x3 = {x5}, F1x4 =F1x5 = F1x6 = Æ;

F1-1X1: F1-1x1 = Æ, F1-1x3 = {x1}, F1-1x4 = F1-1x6 = {x2} \ x2 = Æ ,

F1-1x5 = {x2, x3} \ x2 = {x3};

F2U1: F2u1 = {u2, u3} \ u2 = {u3}, F2u2 = F2u3 = Æ;

F2-1U1: F2-1u1 = Æ, F2-1u2 = {u1} \ u1 = Æ, F2-1u3 = {u1}.

При удалении вершины x3 выполняется условие (2), так как у ребра u3, инцидентного этой вершине, |Г2u3| + |Г1u3| = 2, следовательно, результатом операции будет кусок ультраграфа HU1к, у которого:

X1к = {x1, x2, x3, x4, x5, x6} \ x3 = {x1, x2, x4, x5, x6};

U1к = {u1, u2, u3}; U1кext = {u3}, так как Г1x3 = {u1, u3} и |Г2u1| + |Г1u1| = 3, U1кint = {u1, u2};

Г1X1к = Г1X \ Г1x3 : Г1x1 = {u1}, Г1x2 = {u2}, Г1x4 = Г1x5 = Г1x6 = Æ;

Г2X1к = Г2X \ Г2x3 : Г2x1 = Æ, Г2x2 = {u1}, Г2x4 = Г2x6 = {u2}, Г2x5 = {u2, u3};

Г2U1к: Г2u1 = {x2, x3} \ x3 = {x2}, Г2u2 = {x4, x5, x6} Г2u3 = {x5};

Г1U1к: Г1u1 = {x1}, Г1u2 = {x2}, Г1u3 = {x3} \ x3 = Æ.

При использовании в качестве модели схемы гиперграфа, показанного на рис. 3, а, и удалении из него вершины x2 множества Г1x2 = {u1, u2}, Г2u1 =

{x1, x2, x3}, образ ребра u2 – Г2u2 = {x2, x4, x5, x6}, т. е. условие (3) выполняется. Тогда для операции H1 (X1, U1, Г1X1, Г2U1) = H (X, U, Г1X, Г2U) – xk получаем:

X1 = {x1, x3, x4, x5, x6}; U1 = {u1, u2, u3};

Г1X1 = Г1X \ Г1x2: Г1x1 = {u1}, Г1x3 = {u1,u3}, Г1x4 = Г1x6 = {u2},

Г1x5 = {u2, u3};

Г2U1: Г2u1 = {x1, x2, x3} \ x2 = {x1, x3}, Г2u2 = {x2, x4, x5, x6} \ x2 = {x4, x5, x6}, Г2u3 = {x3, x5}.

При xk = x3 в результате операции H1к (X1к, U1к, Г1X1к, Г2U1к) = H (X, U, Г1X, Г2U) – xk получим кусок гиперграфа, заданный множествами:

X1к = X \ x3 = {x1, x2, x4, x5, x6};

U1к = {u1, u2, u3}, U1кext = {u3}, так как Г1x3 = {u1, u3} и |Г2u1| = 3,

а |Г2u3| = 2, U1кint = {u1, u2};

Г1X1к = Г1X \ Г1x3;

Г2U1к : Г2u1 = {x1, x2, x3} \ x3 = {x1, x2}, Г2u2 = {x2, x4, x5, x6},

Г2u3 = {x3, x5} \ x3 = {x5}.

Удаление элемента э3 из фрагмента схемы, показанной на рис. 4, а, осуществляется операцией удаления вершины x3 из ультраграфа, представленного на рис. 4, б. Поскольку вершина x3 является расщепляющей, в результате операции получаем две компоненты связности HU1 и HU2. Пусть Xl = X2 = {x4, x5, x6}. Для компоненты связности HU2 (Xl, Ul, Г1Xl, Г2Xl, Г2Ul, Г1Ul) получим:

Ul = {u2};

Г1Xl = {Г1x4, Г1x5, Г1x6}, где Г1x4 = {u2}, Г1x5 = Г1x6 = Æ;

Г2Xl = {Г2x4, Г2x5, Г2x6}, где Г2x6 = Æ, Г1x5 = Г1x6 = {u2};

Г2Ul = {Г2u2}, где Г2u2 = {x3, x5, x6} \ x3 = {x5, x6};

Г1Ul = {Г1u2}, где Г1u2 = {x4}.

Удаление ребра uk из ультраграфа HU или гиперграфа Hрис. 5. Соответствует проектной операции отключения соединения от компонент объекта, например цепи от соединяемых ею элементов.

Рис. 5. Фрагмент схемы до и после удаления цепи с2 (а), модель схемы в виде ультраграфа HU и результат удаления ребра u2 – ультраграф HU1 (б), модель схемы в виде гиперграфа H и результат операции – гиперграф H1 (в)

Задается имя удаляемого ребра uk.

Обозначение операции: HU (X, U) – uk для ультраграфа и H (X, U) – uk для гиперграфа.

Условие корректности операции: uk Î U.

В результате применения операции будет получена одна компонента связности, если:

– ребро uk не является перешейком, (5)

– ни одна из вершин, инцидентных удаляемому ребру и которым это ребро инцидентно, не является висячей, т. е.

для ультраграфа "xi Î 2uk È Г1uk} (|Г1xi| + |Г2xi|) > 1 и (6)

для гиперграфа "xi Î Г2uk (|Г1xi| > 1). (7)

Невыполнение условий (5–7) приводит к появлению двух или более компонент связности. Например, отключение в схеме, показанной на рис. 6, а, цепи с2 приведет к образованию двух компонент связности (смотри рис. 6, б). В этом случае в алгоритме необходимо предусмотреть процедуру определения компонент связности и множеств их вершин.

Рис. 6. Исходная схема и она же после удаления цепи с2 (а), модель схемы в виде ультраграфа HU и результат операции HU1 и HU2 (б)

Результатом выполнения операции при удовлетворении указанных выше условий является ультра- HU1 (X1, U1) = HU (X, U) – uk или гиперграф H1 (X1, U1) = H (X, U) – uk.

Содержательно-формальное описание выполнения операции над ультраграфом HU (X, U).

Для получения результата операции – ультраграфа HU1 (X1, U1):

1. Копируем множество X под именем X1: X1 = X.

2. Исключаем ребро uk из множества U: U1 = U \ uk.

3. Определяем множество образов вершин Г1X1, занося в него Г1xi из множества Г1X, если вершина xi не принадлежит множеству вершин, которым инцидентно ребро uk, и удаляя ребро uk из образов тех вершин, которым инцидентно это ребро:

Г1X1 = {Г1xi : xi Ï Г1uk Ú Г1xi \ uk : xi Î Г1ukxi Î X1, Г1xi Î Г1X, Г1uk Î Г1U}.

4. Формируем множество прообразов вершин Г2X1, занося в него Г2xi из множества Г2X, если вершина xi не инцидентна ребру uk, и удаляя ребро uk из прообраза вершины в противном случае:

Г2X1 = {Г2xi : xi Ï Г2uk Ú Г2xi \ uk : xi Î Г2ukxiÎ X1, Г2xi Î Г2X,

Г2uk Î Г2U};

5.     Создаем множество образов Г2U1 и прообразов Г1U1 ребер, копируя их из Г2U и Г1U, исключая при этом Г2uk и Г1uk соответственно:

Г2U1 = Г2U \ Г2uk; Г1U1 = Г1U \ Г1uk.

6. Формируем множество образов вершин F1X1 относительно предиката смежности F1(X1, X1), занося в F1X1 образ вершины xi Î X1 из F1X, если она не принадлежит множеству вершин, которым инцидентно ребро uk, и её образ без таких вершин, которые не инцидентны ни одному из ребер Г1xi, кроме ребра uk, в противном случае:

F1X1 = {F1xi : xi Î X1}, где

ì F1xi Î F1X : xi Ï Г1uk, где Г1uk Î Г1U,

F1xi = í

î F1xi \ Xk : xi Î Г1uk, где Xk = {xt Î F1xi : Г2xt Ç1xi \ uk} = Æ},

F1xi Î F1X, Г2xt Î Г2X, Г1 xi Î Г1X.

7. Определяем множество прообразов вершин F1-1X1, копируя прообраз вершины F1-1xi из F1-1X, если она не инцидентна ребру uk, в противном случае удаляя из F1-1xi те вершины, которым не инцидентны ни одно из ребер Г2xi, кроме ребра uk:

F1-1X1 = { F1-1xi : xi Î X1}, здесь

ì F1-1xi Î F1-1X : xi Ï Г2uk, где Г2uk Î Г2U,

F1-1xi = í

î F1-1xi \ Xk: xi Î Г2uk, где Xk = {xt Î F1-1xi : Г1xt Ç2xi \ uk} = Æ},

F1-1xi Î F1-1X, Г1xt Î Г1X, Г2xi Î Г2X.

8. Формируем множество образов ребер F2U1 относительно предиката смежности F2(U1, U1), занося в F2U1 образ ребра uj Î U1 из F2U, если ребро uk не смежно ребру uj, и его образ без ребра uk в противном случае:

F2U1 = {F2uj \ uk uj Î U1, F2uj Î F2U}.

9. Создаем множество прообразов F2-1U1, занося в него прообраз ребра uj Î U1 из F2-1U, если ребру uj не смежно ребро uk, и его прообраз без ребра uk в противном случае:

F2-1U1 = {F2-1uj \ uk uj ÎU1, F2-1uj Î F2-1U}.

Формальное описание операции над гиперграфом H (X, U).

Множества гиперграфа H1 (X1, U1) получаем по формулам:

X1 = X; U1 = U \ uk;

Г1X1 = {Г1xi : xi Ï Г2uk Ú Г1xi \ uk : xi Î Г2uk xi Î X1, Г1xi Î Г1X, Г2uk Î Г2U};

Г2U1 = Г2U \ Г2uk;

F1X1 = {F1xi : xi Î X1}, здесь

ì F1xi Î F1X : xi Ï Г2uk, где Г2uk Î Г2U,

F1xi = í

î F1xi \ Xk : xi Î Г2uk, где F1xi Î F1X,

Xk = {xt Î F1xi : Г1xt Ç1xi \ uk} = Æ}, Г1xt, Г1 xi Î Г1X.

F2U1 = {F2uj \ uk uj Î U1, F2uj Î F2U}.

Если операция применяется для получения нескольких компонент связности, например ультраграфа, и определено множество вершин Xl некоторой компоненты HUl, то остальные множества, например, ультраграфа HUl (Xl, Ul, Г1Xl, Г2Xl, Г2Ul, Г1Ul) будут:

Ul = { uj Î È { Г1xi È Г2xi } ∕ Г1xi Î Г1X, Г2xi Î Г2X} \ uk;

xi Î Xl

Г1Xl = {Г1xi : uk Ï Г1xi Ú Г1xi \ uk : uk Î Г1xi xi Î X1, Г1xi Î Г1X};

Г2Xl = {Г2xi : xi Ï Г2uk Ú Г2xi \ uk : xi Î Г2uk xi Î Xl, Г2xi Î Г2X,

Г2uk Î Г2U};

Г2Ul = {Г2uj Î Г2U uj Î Ul}; Г1Ul = {Г1uj Î Г1U uj Î Ul}.

Аналогичные выражения нетрудно получить и для гиперграфа Hl.

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

Операция применима к кускам ультра- и гиперграфа HUк (Xк, Uк) и

Hк (Xк, Uк). Решающие правила те же, что и для ультра- или гиперграфа. Результатом операции над куском ультраграфа или гиперграфа будет:

ультраграф HU1 (X1, U1) или гиперграф H1 (X1, U1), если Uкext = {uk}, и кусок ультраграфа HU1к (Xк, Uк) или гиперграфа H1к (X1к, U1к), если ïUкext ï>1.

Пример. Отключим от элементов схемы, показанной на рис. 5, цепь с2. В ультраграфе схемы (смотри рис. 5, б) это реализуется операцией удаления ребра u2, которое не является перешейком. У этого ребра Г2u2 È Г1u2 = {x2, x1, x4}, Г2u1 = {x2, x3} и |Г1x2|+|Г2x2| = 2, |Г1x3|+|Г2x3| = 2, |Г1x1|+|Г2x1| = 2, т. е. условие (6) выполняется.

В результате выполнения операции HU1 (X1, U1) = HU (X, U) – uk получим ультраграф HU1, у которого:

X1 = X; U1 = U \ u2 = {u1, u3};

Г1X1: Г1x1 = {u1, u2} \ u2 = {u1}, Г1x2 = Æ, Г1x3 = {u3}, Г1x4 = {u2} \ u2 = Æ;

Г2X1: Г2x1 = Æ, Г2x2 = {u1, u2} \ u2 = {u1}, Г2x3 = {u1}, Г2x4 = {u3};

Г2U1 = {Г2u1, Г2u3}, где Г2u1 = {x2, x3}, Г2u3 = {x4};

Г1U1 = {Г1u1, Г1u3}, где Г1u1 = {x1}, Г1u3 = {x3};

F1X1: F1x1 = {x2, x3}, F1x3 = {x4}, F1x2 = F1x4 = Æ;

F1-1X1: F1-1x1 = Æ, F1-1x2 = {x1, x4} \ x4 = {x1}, F1-1x3 = {x1}, F1-1x4 = {x3};

F2U1: F2u1 = {u3}, F2u3 = {u2} \ u2 = Æ;

F2-1U1: F2-1u1 = Æ, F2-1u3 = {u1}.

Удалим из гиперграфа, показанного на рис. 5, в, ребро u2. Тогда после операции H1 (X1, U1, Г1X1, Г2U1) = H (X, U, Г1X, Г2U) – uk получим гиперграф, заданный множествами:

X1 = {x1, x2, x3, x4}; U1 = {u1, u3};

Г1X1: Г1x1 = Г1x2 = {u1, u2} \ u2 = {u1}, Г1x3 = {u1, u3}, Г1x4 = {u2, u3} \ u2 = {u3};

Г2U1 = {Г2u1, Г2u2, Г2u3} \ Г2u2 = {Г2u1, Г2u3}, где Г2u1 = {x1, x2, x3}, Г2u3 = {x3, x4}.

Продолжение и окончание работы будут опубликованы в последующих выпусках.

 

Литература

1. Овчинников В.А. Математические модели объектов задач структурного синтеза: Наука и образование. Инженерное образование: Эл. науч. издание. – 2009. – ╧ 4.

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2024 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)