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

 

УДК 004.3 +519.6

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

 

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

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

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

Стягивание рёбер u_f и u_k ультраграфа H_U или гиперграфа H – рис. 7. Соответствует проектной операции соединения двух цепей.

Рисунок 7 – Фрагмент схемы до и после соединения цепей с₁ и с₂ (а), ее модель в виде ультраграфа H_U и результат H_U1 стягивания рёбер u₁ и u₂ (б), гиперграф схемы H и

результат операции H₁ (в)

Задаются имена стягиваемых рёбер u_f, u_k и заменяющего их ребра u_t.

Обозначение операции: ╣(H_U (X, U), u_f, u_k, u_t) для ультраграфа и

╣(H (X, U), u_f, u_k, u_t) для гиперграфа.

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

В результате выполнения операции получаем ультра- или гиперграф

H_U1 (X₁, U₁) = ╣(H_U (X, U), u_f, u_k, u_t) или

H₁ (X₁, U₁) = ╣(H (X, U), u_f, u_k, u_t).

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

Для получения ультраграфа H_U1 (X₁, U₁):

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

2.     Формируем множество рёбер U₁, исключая из множества U рёбра u_f и u_k и добавляя в него ребро u_t: U₁ = {U \ {u_f, u_k} _· u_t}.

3.     Получаем множество образов вершин Г₁X₁, занося в него Г₁x_i из множества Г₁X, если рёбра u_f и u_k не инцидентны вершине x_i, в противном случае:

– удаляя из Г₁x_i ребро u_f и добавляя ребро u_t, если вершине x_i инцидентно ребро u_f,

– удаляя из Г₁x_i ребро u_k и добавляя ребро u_t, если вершине x_i инцидентно ребро u_k,

– удаляя из Г₁x_i рёбра u_f и u_k и добавляя ребро u_t, если оба ребра инцидентны этой вершине:

Г₁X₁ = {Г₁x_i ∕ x_i Î X₁}, здесь

ìГ₁x_i, если x_i Ï Г₁u_f & x_i Ï Г₁u_k,

çГ₁x_i \ u_{f ·} u_t, если x_i Î Г₁u_f & x_i Ï Г₁u_k,

Г₁x_i = íГ₁x_i \ u_{k ·} u_t, если x_i Î Г₁u_k & x_i Ï Г₁u_f,

îГ₁x_i \ {u_f, u_k} _· u_t, если x_i Î Г₁u_k & x_i Î Г₁u_f,

где Г₁x_i Î Г₁X, Г₁u_f, Г₁u_k Î Г₁U.

Приведенные для Г₁x_i выражения очевидны и просты для понимания. Однако их целесообразно записать в более компактном виде, а именно:

ìГ₁x_i : x_i Ï Г₁u_f & x_i Ï Г₁u_k,

Г₁x_i = í

îГ₁x_i \ {u_f, u_k} _· u_t : x_i Î {Г₁u_f È Г₁u_k}.

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

4.     Формируем множество прообразов вершин Г₂X₁, занося в него Г₂x_i из множества Г₂X, если рёбра u_f и u_k не являются рёбрами, которым инцидентна вершина x_i, в противном случае:

– удаляя из Г₂x_i ребро u_f и добавляя ребро u_t, если ребру u_f инцидентна вершина x_i,

– удаляя из Г₂x_i ребро u_k и добавляя ребро u_t, если ребру u_k инцидентна эта вершина,

– удаляя из Г₂x_i рёбра u_f и u_k и добавляя ребро u_t, если вершина инцидентна этим рёбрам:

Г₂X₁ = {Г₂x_i ∕ x_i Î X₁}, здесь

ìГ₂x_i : x_i Ï Г₂u_f & x_i Ï Г₂u_k,

Г₂x_i = í

îГ₂x_i \ {u_f, u_k} _· u_t : x_i Î {Г₂u_f È Г₂u_k},

где Г₂x_i Î Г₂X, Г₂u_f, Г₂u_k Î Г₂U.

5.     Формируем множество образов и прообразов рёбер Г₂U₁ и Г₁U₁, копируя их из Г₂U и Г₁U, исключая при этом Г₂u_f, Г₂u_k и Г₁u_f, Г₁u_k и добавляя образ Г₂u_t и прообраз Г₁u_t нового ребра u_t соответственно:

Г₂U₁ = {Г₂U \ {Г₂u_f, Г₂u_k} _· Г₂u_t},

где Г₂u_t = Г₂u_f È Г₂u_k, Г₂u_f и Г₂u_k Î Г₂U;

Г₁U₁ = {Г₁U \ {Г₁u_f, Г₁u_k } _· Г₁u_t},

где Г₁u_t = Г₁u_f È Г₁u_k, Г₁u_f и Г₁u_k Î Г₁U.

6.     Создаем множество образов F₁X₁ вершин X₁ относительно предиката смежности F₁(X₁, X₁),

– копируя образ F₁x_i из F₁X, если вершине x_i не инцидентны рёбра u_f и u_k или инцидентны оба,

– определяя образ вершины как объединение её образа F₁x_i Î F₁X и множества Г₂u_k Î Г₂U вершин, которые инцидентны ребру u_k, если вершине x_i инцидентно ребро u_f,

– объединяя её образ и множество Г₂u_f Î Г₂U вершин, которые инцидентны ребру u_f, если вершине x_i инцидентно ребро u_k:

F₁X₁ = {F₁x_i ∕ x_i Î X₁}, где

ìF₁x_i : x_i Ï Г₁u_f & x_i Ï Г₁u_k Ú x_i Î Г₁u_f & x_i Î Г₁u_k,

F₁x_i = íF₁x_i È Г₂u_k : x_i Î Г₁u_f,

îF₁x_i È Г₂u_f : x_i Î Г₁u_k,

где F₁x_i Î F₁X, Г₁u_f и Г₁u_k Î Г₁U, Г₂u_f и Г₂u_k Î Г₂U.

7.     Получаем множество прообразов F₁^-1X₁ вершин X₁ относительно предиката смежности F₁(X₁, X₁),

– копируя прообраз F₁^-1x_i из F₁^-1X, если вершина x_i не инцидентна рёбрам u_f и u_k или инцидентна тому и другому,

– определяя прообраз вершины как объединение её прообраза F₁^-1x_i Î F₁^-1X и множества Г₁u_k Î Г₁U вершин, которым инцидентно ребро u_k, если вершина x_i инцидентна ребру u_f,

– объединяя её прообраз и множество Г₁u_f Î Г₁U вершин, которым инцидентно ребро u_f, если вершина x_i инцидентна ребру u_k:

F₁^-1X₁ = {F₁^-1x_i ∕ x_i Î X₁ }, где

ì F₁^-1x_i: x_i ÏГ₂u_f & x_i Ï Г₂u_k Ú x_i ÎГ₂u_f & x_i Î Г₂u_k,

F₁^-1x_i = í F₁^-1x_i È Г₁u_k : x_i Î Г₂u_f,

î F₁^-1x_i È Г₁u_f : x_i Î Г₂u_k,

где F₁^-1x_i Î F₁^-1X, Г₂u_f и Г₂u_k Î Г₂U, Г₁u_f и Г₁u_k Î Г₁U.

8.     Формируем множество образов F₂U₁ рёбер U₁ относительно предиката смежности F₂(U₁, U₁). При j ¹ t:

– копируя F₂u_j из множества F₂U, если ребру u_j не смежны рёбра u_f и u_k,

– удаляя из F₂u_j Î F₂U ребро u_f или ребро u_k, если ребру u_j смежно ребро u_f или u_k соответственно, и добавляя ребро u_t,

– удаляя из F₂u_j Î F₂U рёбра u_f и u_k и добавляя ребро u_t, если ребру u_j смежны рёбра u_f и u_k,:

F₂U₁ = { F₂u_j ∕ u_j Î U₁}, здесь

ìF₂u_j : u_f Ï F₂u_j & u_k Ï F₂u_j,

F₂u_j = í

îF₂u_j \ {u_f, u_k} _· u_t : u_f Î F₂u_j Ú u_k Î F₂u_j,

где F₂u_j Î F₂U.

Образ ребра u_t будет:

F₂u_t = {F₂u_f È F₂u_k}, если u_f и u_k не смежны, и F₂u_t = {F₂u_f È F₂u_k} \ {u_f, u_k} _· u_t, если они смежны, т. е. u_f Î F₂u_k Ú u_k Î F₂u_f Ú u_f Î F₂u_k & u_k Î F₂u_f.

9.     Создаем множество F₂^-1U₁ прообразов ребер U₁. При j ¹ t:

– копируя F₂^-1u_j из множества F₂^-1U, если ребро u_j не смежно ни ребру u_f , ни ребру u_k,

– удаляя из F₂^-1u_j Î F₂^-1U ребро u_f или ребро u_k, если ребро u_j смежно ребру u_f или u_k соответственно, и добавляя ребро u_t,

– удаляя из F₂^-1u_j Î F₂^-1U рёбра u_f и u_k и добавляя ребро u_t, если ребро u_j смежно рёбрам u_f и u_k:

F₂^-1U₁ = {F₂^-1u_j ∕ u_j Î U₁}, здесь

ìF₂^-1u_j : u_f Ï F₂^-1u_j & u_k Ï F₂^-1u_j,

F₂^-1u_j = í

îF₂^-1u_j \ {u_f, u_k} _· u_t : u_f Ï F₂^-1u_j Ú u_k Ï F₂^-1u_j,

где F₂^-1u_j Î F₂^-1U.

Прообраз ребра u_t будет:

F₂^-1u_t = {F₂^-1u_f È F₂^-1u_k}, если рёбра u_f и u_k не смежны, и

F₂^-1u_t = {F₂^-1u_f È F₂^-1u_k} \ {u_f, u_k} _· u_t, если они смежны.

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

Множества гиперграфа H₁ (X₁, U₁) определяются как:

X₁ = X ; U₁ = {U \ {u_f, u_k} _· u_t};

Г₁X₁ = {Г₁x_i : x_i ÏГ₂u_f & x_i Ï Г₂u_k Ú Г₁x_i \ {u_f, u_k} _· u_t : x_i Î {Г₂u_f È Г₂u_k} ∕ x_i Î X₁, Г₁x_i Î Г₁X, Г₂u_f, Г₂u_k Î Г₂U};

Г₂U₁ = {Г₂U \ {Г₂u_f, Г₂u_k} _· Г₂u_t}, где Г₂u_t = Г₂u_f È Г₂u_k, Г₂u_f и Г₂u_k Î Г₂U;

F₁X₁ = {F₁x_i ∕ x_i Î X₁}, здесь

ìF₁x_i : x_i Ï Г₂u_f & x_i Ï Г₂u_k Ú x_i Î Г₂u_f & x_i Î Г₂u_k,

F₁x_i = íF₁x_i È Г₂u_k : x_i Î Г₂u_f,

îF₁x_i È Г₂u_f : x_i Î Г₂u_k,

где F₁x_i Î F₁X, Г₂u_f и Г₂u_k Î Г₂U.

F₂U₁ = {F₂u_j ∕ u_j Î U₁}, здесь для j ¹ t

ìF₂u_j : u_f Ï F₂u_j & u_k Ï F₂u_j,

F₂u_j = í

îF₂u_j \ {u_f, u_k} _· u_t : u_f Î F₂u_j Ú u_k Î F₂u_j,

где F₂u_j Î F₂U.

Образ ребра u_t будет:

ì{F₂u_f È F₂u_k} : u_f Ï F₂u_k & u_k Ï F₂u_f,

F₂u_t = í

î{F₂u_f È F₂u_k} \ {u_f, u_k} : u_f Î F₂u_k (u_k Î F₂u_f).

С процедурной точки зрения образ ребра u_t целесообразно определять по формуле:

F₂u_t = {F₂u_f È F₂u_k} \ {u_f, u_k} (смотри примечание 1 в операции «удаление вершины»).

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

Операция может выполняться над куском ультра- или гиперграфа. Если оба стягиваемые ребра внутренние, то в п. 2 определяется

U₁^к_int = {U^к_int \ {u_f, u_k} _· u_t} и U₁^к_ext = U^к_ext.

Если хотя бы одно из этих рёбер является внешним, должна быть задана информация о виде заменяющего ребра и соответствующим образом сформированы U₁^к_int и U₁^к_ext.

Пример. Выполним соединение цепей с₁ и с₂ в цепь с₄ в схеме, показанной на рис. 7, а. В результате операции H_U1 (X₁, U₁) = ╣(H_U (X, U), u_f, u_k, u_t) стягивания ребер u₁ и u₂ ультраграфа схемы, изображенной на рис. 7, б, получим

X₁ = {x₁, x₂,. . . , x₆};

U₁ = U \ {u₁, u₂} _· u₅} = {u₃, u₄, u₅};

Г₁X₁: Г₁x₁ = {u₁} \ {u₁, u₂} _· u₅ = {u₅}, Г₁x₂ = {u₂} \ {u₁, u₂} _· u₅ = {u₅}, Г₁x₃ = Æ; Г₁x₄ = {u₂} \ {u₁, u₂} _· u₅ = {u₅}, Г₁x₅ = {u₂, u₄} \ {u₁, u₂} _· u₅ = {u₄, u₅}, Г₁x₆ = {u₃};

Г₂X₁: Г₂x₁ = Æ, Г₂x₂ = {u₁} \ {u₁, u₂} _· u₅ = {u₅}, Г₂x₃ = {{u₁, u₂} \ {u₁, u₂} _· u₅} = {u₅}, Г₂x₄ = Æ, Г₂x₅ = {u₃} Г₁x₆ = {u₄};

Г₁U₁ = {Г₁u₃, Г₁u₄, Г₁u₅}, где Г₁u₅ = {x₁} È {x₂, x₄, x₅} = {x₁, x₂, x₄, x₅};

Г₂U₁ = {Г₂u₃, Г₂u₄, Г₂u₅}, где Г₂u₅ = {x₂, x₃} È {x₂, x₃} = {x₂, x₃};

F₁X₁: F₁x₁ = {x₂, x₃} È {x₃} = {x₂, x₃}, F₁x₂ = {x₃} È {x₂, x₃} = {x₃, x₂}, F₁x₃ = Æ, F₁x₄ = {x₃} È {x₂, x₃} = {x₃, x₂}, F₁x₅ = {x₃, x₆} È {x₂, x₃} = {x₃, x₆, x₂}, F₁x₆ = {x₅};

F₁^-1X₁: F₁^-1x₁ = Æ, F₁^-1x₂ = {x₁} È {x₂, x₄, x₅} = {x₁, x₂, x₄, x₅}, F₁^-1x₃ = {x₁, x₂, x₄, x₅}, F₁^-1x₄ = Æ, F₁^-1x₅ = {x₆}, F₁^-1x₆ = {x₅};

F₂U₁: F₂u₃ = {u₂, u₄} \ {u₁, u₂}} _· u₅ = {u₄, u₅}, F₂u₄ = {u₃}, F₂u₅ = {u₅};

F₂^-1U₁: F₂^-1u₃ = {u₄}, F₂^-1u₄ = {u₃}, F₂^-1u₅ = {u₅}.

Для гиперграфа той же схемы, представленного на рис. 7, в, после операции H₁ (X₁, U₁) = ╣(H (X, U), u_f, u_k, u_t) получим:

X₁ = {x₁, x₂,. . . , x₆};

U₁ = U \ {u₁, u₂} _· u₅} = {u₃, u₄, u₅};

Г₁X₁: Г₁x₁ = {u₁} \ {u₁, u₂} _· u₅ = {u₅}, Г₁x₂ = Г₁x₃ = {u₁,u₂} \ {u₁,u₂} _· u₅ = {u₅}, Г₁x₄ = {u₂} \ {u₁,u₂} _· u₅ = {u₅}, Г₁x₅ = {u₂, u₃, u₄} \ {u₁,u₂} _· u₅ = {u₃, u₄, u₅}, Г₁x₆ = {u₃, u₄};

Г₂U₁ = {Г₂u₃, Г₂u₄, Г₂u₅}, где Г₂u₅ = {x₁, x₂, x₃} È {x₂, x₃, x₄, x₅} = {x₁, x₂, x₃, x₄, x₅};

F₁X₁: F₁x₁ = {x₂, x₃} È {x₂, x₃, x₄, x₅} = {x₂, x₃, x₄, x₅}, F₁x₂ = {x₁, x₃, x₄, x₅}, F₁x₃ = {x₁, x₂, x₄, x₅}, F₁x₄ = {x₁, x₂, x₃, x₅}, F₁x₅ = {x₂, x₃, x₄} È {x₆} = {x₂, x₃, x₄, x₆}, F₁x₆ = {x₅}.

F₂U₁: F₂u₃ = {u₂, u₄} \ {u₁, u₂}} _· u₅ = {u₄, u₅}, F₂u₄ = {u₂, u₃} \ {u₁, u₂} _· u₅ = {u₃, u₅}, F₂u₅ = {{u₂} È {u₁, u₃, u₄}} \ {u₁, u₂} = {u₃, u₄}.

Подразбиение ребра u_k ультраграфа H_U или гиперграфа H – рис. 8. Соответствует проектной операции разрыва цепи и подключения двух новых к вводимому элементу.

Рисунок 8 – Исходная схема до и после введения элемента э₇ в цепь с₁ (а), ее модель в виде ультраграфа H_U и результат H_U1 выполнения операции подразбиения ребра u₁ (б), гиперграф схемы H и результат той же операции H₁ (в)

Осуществляется введением вершины, образуются два новых ребра u_r и u_t. Задаются разбиваемое ребро u_k, вводимая вершина x_f, имена новых ребер u_r и u_t, а также:

·        для ультраграфа указываются: ребро, инцидентное вершине x_f, и ребро, которому она инцидентна, например, Г₁x_f = u_r и Г₂x_f = u_t; X_r⁺ = Г₂u_r и X_t⁺ = Г₂u_t – вершины, инцидентные ребрам u_r и u_t соответственно; X_r^– = Г₁u_r и X_t^– = Г₁u_t – вершины, которым инцидентны указанные ребра;

·        для гиперграфа указываются подмножества X_r = Г₂u_r и X_t = Г₂u_t вершин, инцидентных ребрам u_r и u_t.

Обозначение операции:

╠ (H_U (X, U), u_k, x_f, u_r, X_r⁺, X_r^–, u_t, X_t⁺, X_t^–)для ультраграфа и

╠ (H (X, U), u_k, x_f, u_r, X_r, u_t, X_t) для гиперграфа.

Условие корректности операции:

·        для ультраграфа – u_k Î U; X_r⁺ Ç X_t⁺ = Æ; X_r⁺ È X_t⁺ = Г₂u_{k ·} x_f ; X_r^– Ç X_t^– = Æ; X_r^– È X_t^– = Г₁u_{k ·} x_f; X_r⁺ Ç X_t^– Ú X_r^– Ç X_t⁺ = x_f;

·        для гиперграфа – u_k Î U, X_r È X_t = Г₂u_{k ·} x_f; X_r Ç X_t = x_f.

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

– ультраграф H_U1 (X₁, U₁) = ╠ (H_U (X, U), u_k, x_f, u_r, X_r⁺, X_r^–, u_t, X_t⁺, X_t^–) или

– гиперграф H₁ (X₁, U₁) = ╠ (H (X, U), u_k, x_f, u_r, X_r, u_t, X_t).

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

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

Для получения ультраграфа H_U1 (X₁, U₁):

1.     Определяем множество X₁, добавляя в X вершину x_f: X₁ = X _· x_f.

2.     Формируем множество рёбер U₁, исключая из множества U ребро u_k и добавляя в него рёбра u_r и u_t: U₁ = U \ u_{k ·} {u_r, u_t}.

3.     Получаем множество образов Г₁X₁, копируя Г₁x_i из множества Г₁X, если ребро u_k не инцидентно вершине x_i. Если вершине x_i инцидентно одно из новых рёбер, то из ее образа в Г₁X исключаем ребро u_k и добавляем то, которое ей инцидентно в соответствии с исходными данными операции, т. е. u_r или u_t. Образ вводимой вершины x_f – Г₁x_f:

Г₁X₁ = {Г₁x_i ∕ x_i Î X₁}, где

ìГ₁x_i Î Г₁X : x_i Ï Г₁u_k, где Г₁u_k Î Г₁U,

çГ₁x_i \ u_{k ·} u_r : x_i Î Г₁u_r, где Г₁x_i Î Г₁X,

Г₁x_i = íГ₁x_i \ u_{k ·} u_t : x_i Î Г₁u_t, где Г₁x_i Î Г₁X,

îГ₁x_f : x_i = x_f.

4.     Формируем множество прообразов Г₂X₁, копируя Г₂x_i из множества Г₂X, если вершина не инцидентна ребру u_k. Если вершина инцидентна одному из новых рёбер, то из ее прообраза в Г₂X исключаем ребро u_k и добавляем то, которому она инцидентна. Прообраз вводимой вершины x_f – Г₂x_f:

Г₂X₁ = {Г₂x_i ∕ x_i Î X₁}, где

ìГ₂x_i Î Г₂X : x_i Ï Г₂u_k, где Г₂u_k Î Г₂U,

÷Г₂x_i \ u_{k ·} u_r : x_i Î Г₂u_r, где Г₂x_i Î Г₂X,

Г₂x_i = íГ₂x_i \ u_{k ·} u_t : x_i Î Г₂u_t, где Г₂x_i Î Г₂X,

îГ₂x_f : x_i = x_f.

5.     Создаем множества образов Г₂U₁ и прообразов Г₁U₁ рёбер, копируя их из Г₂U и Г₁U₁, исключая при этом Г₂u_k и Г₁u_k и добавляя в соответствующие множества образы и прообразы новых рёбер u_r и u_t:

Г₂U₁ = Г₂U \ Г₂u_{k ·} {Г₂u_r, Г₂u_t}, где Г₂u_r = X_r⁺, Г₂u_t = X_t⁺;

Г₁U₁ = Г₁U \ Г₁u_{k ·} {Г₁u_r, Г₁u_t}, где Г₁u_r = X_r^–, Г₁u_t = X_t^–.

6.     Определяем множество образов F₁X₁ вершин X₁ для чего для x_i ¹ x_f:

– копируем F₁x_i из F₁X, если вершине x_i не инцидентно ребро u_k,

– удаляем из F₁x_i множество вершин, инцидентных ребру u_k, и добавляем множество вершин, инцидентных ребру u_r, если вершине x_i инцидентно ребро u_r,

– удаляем из F₁x_i множество вершин, инцидентных ребру u_k, и добавляем множество вершин, инцидентных ребру u_t, если вершине x_i инцидентно это ребро.

При x_i = x_f записываем в F₁x_f множество вершин, инцидентных ребру u_r, если оно инцидентно вводимой вершине, или ребру u_t, если данное ребро инцидентно этой вершине:

F₁X₁ = {F₁x_i ∕ x_i Î X₁}, здесь для i ¹ f

ìF₁x_i Î F₁X : x_i Ï Г₁u_k, где Г₁u_k Î Г₁U,

F₁x_i = í{F₁x_i \ Г₂u_k} _· Г₂u_r : x_i Î Г₁u_r, где F₁x_i Î F₁X,

î{F₁x_i \ Г₂u_k} _· Г₂u_t : x_i Î Г₁u_t, где F₁x_i Î F₁X,

F₁x_f = Г₂u_r : Г₁x_f = u_r Ú Г₂u_t : Г₁x_f = u_t.

7.     Создаем множество прообразов F₁^-1X₁ вершин X₁ для чего:

– копируем F₁^-1x_i из F₁^-1X, если вершине x_i не смежно ребро u_k,

– удаляем из F₁^-1x_i множество вершин, которым инцидентно ребро u_k, и добавляем множество вершин, которым инцидентно ребро u_r, если вершина x_i инцидентна ребру u_r,

– удаляем из F₁^-1x_i множество вершин, которым инцидентно ребро u_k, и добавляем множество вершин, которым инцидентно ребро u_t, если вершина x_i инцидентна этому ребру,

При x_i = x_f заносим в F₁^-1x_f множество вершин, которым инцидентно ребро u_r, если ему инцидентна вводимая вершина, или множество вершин, которым инцидентно ребро u_t, если ему инцидентна вводимая вершина:

F₁^-1X₁ = {F₁^-1x_i ∕ x_i Î X₁}, здесь для i ¹ f

ìF₁^-1x_i Î F₁^-1X : x_i Ï Г₂u_k, где Г₂u_k Î Г₂U,

F₁^-1x_i = í{F₁^-1x_i \ Г₁u_k} _· Г₁u_r : x_i Î Г₂u_r, где F₁^-1x_i Î F₁^-1X,

î{F₁^-1x_i \ Г₁u_k} _· Г₁u_t : x_i Î Г₂u_t, где F₁^-1x_i Î F₁^-1X,

F₁^-1x_f = Г₁u_r : Г₂x_f = u_r ÚГ₁u_t : Г₂x_f = u_t.

8.     Формируем множество образов F₂U₁ ребер U₁ относительно предиката смежности F₂(U₁, U₁), для j ¹ r ¹ t:

– копируя F₂u_j из множества F₂U, если ребро u_k не смежно ребру u_j,

– удаляя из F₂u_j Î F₂U ребро u_k и добавляя ребро u_r, если эти рёбра смежны ребру u_j,

– удаляя из F₂u_j Î F₂U ребро u_k и добавляя ребро u_t, если эти рёбра смежны ребру u_j,

– удаляя из F₂u_j Î F₂U ребро u_k и добавляя рёбра u_r, u_t , если все эти рёбра смежны ребру u_j:

F₂U₁ = {F₂u_j ∕ u_j Î U₁}, здесь

ìF₂u_j : u_k Ï F₂u_j,

ç{F₂u_j \ u_k} _· u_r : u_k Î F₂u_j & Г₂u_j Ç Г₁u_r ¹ Æ,

F₂u_j = í{F₂u_j \ u_k} _· u_t : u_k Î F₂u_j & Г₂u_j Ç Г₁u_t ¹ Æ,

î{F₂u_j \ u_k} _· {u_r, u_t} : u_k Î F₂u_j & Г₂u_j Ç Г₁u_r ¹ Æ & Г₂u_j Ç Г₁u_t ¹ Æ, где F₂u_j Î F₂U.

Рёбра, смежные рёбрам u_r и u_t, определяются по формулам:

F₂u_r = È Г₁x_i и F₂u_t = È Г₁x_i, Г₁x_i Î Г₁X.

x_i Î Г₂u x_i Î Г₂u_t

9.     Определяем множество прообразов F₂^-1U₁ рёбер множества U₁ относительно предиката смежности F₂ (U₁, U₁), для j ¹ r ¹ t:

– копируя F₂^-1u_j из множества F₂^-1U, если ребру u_k не смежно ребро u_j,

– удаляя из F₂^-1u_j Î F₂^-1U ребро u_k и добавляя ребро u_r, если этим ребрам смежно ребро u_j,

– удаляя из F₂^-1u_j Î F₂^-1U ребро u_k и добавляя ребро u_t, если этим ребрам смежно ребро u_j,

– удаляя из F₂^-1u_j Î F₂^-1U ребро u_k и добавляя ребра u_r, u_t , если всем этим ребрам смежно ребро u_j:

F₂^-1U₁ = {F₂^-1u_j ∕ u_j Î U₁}, здесь

ì F₂^-1u_j : u_k Ï F₂^-1u_j,

ç{F₂^-1u_j \ u_k}_· u_r : u_k Î F₂^-1u_j & Г₁u_j Ç Г₂u_r ¹ Æ,

F₂^-1u_j = í{F₂^-1u_j \ u_k} _· u_t : u_k Î F₂^-1u_j & Г₁u_j Ç Г₂u_t ¹ Æ,

î{F₂^-1u_j \ u_k} _· {u_r, u_t} : u_k Î F₂^-1u_j & Г₁u_j Ç Г₂u_r ¹ Æ & Г₁u_j Ç

Г₂u_t ¹ Æ, где F₂^-1u_j Î F₂^-1U.

Прообразы рёбер u_r и u_t определяются по формулам:

F₂^-1u_r = È Г₂x_i и F₂^-1u_t = È Г₂x_i, Г₂x_i Î Г₂X.

x_i Î Г₁u_r x_i Î Г₁u_t

Формальное описание выполнения операции над гиперграфом.

Множества гиперграфа H₁ (X₁, U₁) получаем по выражениям:

X₁ = X _· x_f; U₁ = U \ u_{k ·} {u_r, u_t};

Г₁X₁ = (Г₁x_i ∕ x_i Î X₁}, где Г₁x_f = {u_r, u_t} и для i ¹ f

ìГ₁x_i Î Г₁X, если u_k Ï Г₁x_i,

Г₁x_i = íГ₁x_i \ u_{k ·} u_r, если u_r Î Г₁x_i, где Г₁x_i Î Г₁X,

îГ₁x_i \ u_{k ·} u_t, если u_t Î Г₁x_i, где Г₁x_i Î Г₁X;

Г₂U₁ = Г₂U \ Г₂u_{k ·} {Г₂u_r, Г₂u_t}, где Г₂u_r = X_r, Г₂u_t = X_t;

F₁X₁ = {F₁x_i ∕ x_iÎX₁}, здесь F₁x_f = X_{r ·} X_t \ x_f и для i ¹ f

ìF₁x_i Î F₁X : x_i Ï Г₂u_k, где Г₂u_k Î Г₂U,

F₁x_i = í{F₁x_{i ·} Г₂u_r }\ Г₂u_k : x_i Î Г₂u_r, где F₁x_i Î F₁X,

î{F₁x_{i ·} Г₂u_t} \ Г₂u_k : x_i Î Г₂u_t, где F₁x_i Î F₁X;

F₂U₁ = {F₂u_j ∕ u_j Î U₁}, здесь для j ¹ r ¹ t

ì F₂u_j : u_k Ï F₂u_j,

ç{F₂u_j \ u_k} _· u_r : u_k Î F₂u_j & Г₂u_j Ç Г₂u_t = Æ,

F₂u_j = í{F₂u_j \ u_k}_· u_t : u_k Î F₂u_j & Г₂u_j Ç Г₂u_r = Æ,

î{F₂u_j \ u_k} _· {u_r, u_t} : u_k Î F₂u_j & Г₂u_j Ç Г₂u_r ¹ Æ & Г₂u_j Ç Г₂u_t ¹ Æ, где F₂u_j Î F₂U.

Рёбра, смежные ребрам u_r и u_t, определяются по формулам:

F₂u_r = È {Г₁x_i \ u_r : |Г₂u_r| > 1 Ú Г₁x_i : |Г₂u_r| = 1},

x_i Î Г₂u_r

F₂u_t = È {Г₁x_i \ u_t : | Г₂u_t| > 1 Ú Г₁x_i : |Г₂u_t| = 1}.

x_i Î Г₂u_t

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

Операция может быть распространена на кусок ультра- или гиперграфа. Если разбиваемое ребро является внешним, должна быть задана информация о виде новых рёбер и соответствующим образом сформированы U₁^к_int и U₁^к_ext.

Пример. Выполним подразбиение ребра для варианта модификации схемы, показанного на рис. 8, а. Тогда для операции подразбиения ребра ультраграфа (смотри рис. 8, б) u_k = u₁, x_f = x₇, u_r = u₃, u_t = u₄ и Г₁x₇ = {u₄}, Г₂x₇ = {u₃}, Г₂u₃ = {x₂, x₇}, Г₂u₄ = {x₃, x₄}, Г₁u₃ = {x₁}, Г₁u₄ = {x₇}.

В результате выполнения H_U1 (X₁, U₁) = ╠ (H_U (X, U), u_k, x_f, u_r, u_t) операции получим ультраграф H_U1, у которого:

X₁ = X _· x₇ = {x₁, x₂, …, x₇}; U₁ = U \ u_{1 ·} {u₃, u₄} = {u₂, u₃, u₄};

Г₁X₁: Г₁x₁ = {u₁} \ {u₁} _· u₃ = {u₃}, Г₁x₂ = Г₁x₄ = Г₁x₅ = Г₁x₆ = Æ,

Г₁x₃ = {u₂}, Г₁x₇ = {u₄};

Г₂X₁: Г₂x₁ = Æ, Г₂x₂ = {u₁} \ {u₁} _· u₃ = {u₃}, Г₂x₃ = {u₁} \ {u₁} _· u₄ = {u₄}, Г₂x₄ = {u₁} \ {u₁} _· u₄ = {u₄}, Г₂x₅ = {u₂}, Г₂x₆ = {u₂}, Г₁x₇ = {u₃};

Г₂U₁ = {Г₂u₂, Г₂u₃, Г₂u₄}, где: Г₂u₂ = {x₅, x₆}, Г₂u₃ = {x₂, x₇}, Г₂u₄ = {x₃, x₄};

Г₁U₁ = {Г₁u₂, Г₁u₃, Г₁u₄}, где: Г₁u₂ = {x₃}, Г₁u₃ = {x₁}, Г₁u₄ = {x₇};

F₁X₁: F₁x₁ = {x₂, x₃, x₄} \ {x₂, x₃, x₄} _· {x₂, x₇} = {x₂, x₇}, F₁x₂ = F₁x₄ = F₁x₅ = F₁x₆ = Æ, F₁x₃ = {x₅, x₆}, F₁x₇ = Г₂u₄ = {x₃, x₄};

F₁^-1X₁ : F₁^-1x₁ = Æ , F₁^-1x₂ = {x₁}, F₁^-1x₃ = F₁^-1x₄ = {x₇}, F₁^-1x₅ = F₁^-1x₆ ={x₃}, F₁^-1x₇ = Г₁u₃ = {x₁};

F₂U₁: F₂u₂ = Æ, F₂u₃ = È Г₁x_i = Г₁x₂ È Г₁x₇ = {u₄}, F₂u₄ = È Г₁x_i =

x_i Î Г₂u₃ x_i Î Г₂u₄

Г₁x₃ È Г₁x₄ = {u₂};

F₂^-1U₁: F₂^-1u₂ = {u₁} \ {u₁} _· {u₄} = {u₄}, F₂^-1u₃ = Г₂x₁ = Æ,

F₂^-1u₄ = Г₂x₇ = {u₃}.

Для гиперграфа показанного на рис. 8, в, операция H₁ (X₁, U₁, Г₁X₁, Г₂U₁) =╠ (H (X, U, Г₁X, Г₂U), u_k, x_f, u_r, u_t) подразбиения ребра u₁ на рёбра u₃ и u₄ введением вершины x_f = x₇ так, что X₃ = Г₂u₃ = {x₁, x₂, x₇} и X₄ = Г₂u₄ = {x₃, x₄, x₇}, дает гиперграф H₁, у которого:

X₁ = {x₁, x₂, …, x₇}; U₁ = {u₂, u₃, u₄};

Г₁X₁: Г₁x₁ = Г₁x₂ = {{u₁ \ u₁} _· u₃} = {u₃}, Г₁x₃ = {{{u₁, u₂} \ u₁} _· u₄} = {u₂, u₄}, Г₁x₄ = {{{u₁} \ u₁} _· u₄} = {u₄}, Г₁x₅ = Г₁x₆ = {u₂}, Г₁x₇ = {u₃, u₄};

Г₂U₁ = {Г₂u₂, Г₂u₃, Г₂u₄}, где: Г₂u₂ = {x₃, x₅, x₆}, Г₂u₃ = {x₁, x₂, x₇},

Г₂u₄ = {x₃, x₄, x₇}.

Удаление вершины x_k из образов и прообразов ребер ультраграфа H_U или образов ребер гиперграфа H – рис. 9. Реализует проектную опера-цию отключения элемента схемы э_k от множества цепей С_t.

Рисунок 9 – Фрагмент схемы до и после отключения элемента Э₃ от цепей с₁ и с₂ (а), модель схемы в виде ультраграфа H_U и результат операции H_U1 (б), модель схемы в виде гиперграфа H и результат операции в виде гиперграфа H₁и куска H₁^к (в)

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

·  для ультраграфа – подмножество U_k' инцидентных ей ребер, из прообразов которых следует удалить вершину x_k, и подмножество U_k² ребер, которым инцидентна эта вершина и из чьих образов её надо удалить;

·  для гиперграфа – подмножество U_k' инцидентных вершине x_k ребер, из образов которых её следует удалить.

Обозначение операции: H_U (X, U) : {Г₁U_k', Г₂U_k²}\ x_k для ультраграфа и

H(X, U) : Г₂U_k' \ x_k для гиперграфа.

Условия корректности операции:

– для ультраграфа x_k Î X, U_k' Í U_k⁺ & U_k² Ì U_k^– Ú U_k² Í U_k^– & U_k' Ì U_k⁺ Ú U_k' Ì U_k⁺ & U_k²Ì U_k^– , где U_k⁺ = Г₁x_k, U_k^– = Г₂x_k;

– для гиперграфа x_k Î X, U_k' Ì Г₁x_k.

При применении операции образуется одна компонента связности, если x_k не является вершиной, расщепляющей граф в отношении ребер множества {U_k' È U_k²} для ультраграфа и U_k' для гиперграфа. В противном случае граф распадается на компоненты связности и при преобразовании графа необходимо определять компоненты связности и множества их вершин.

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

– ультраграф H_U1 (X₁, U₁) = H_U (X, U) : {Г₁U_k' , Г₂U_k²} \ x_k , если

" u_j Î{U_k' È U_k²} (|Г₂u_j| + |Г₁u_j| > 2), (8)

– кусок ультраграфа H_U1^к (X₁^к, U₁^к) = H_U (X, U) : {Г₁U_k', Г₂U_k²} \ x_k, если

$ u_j Î {U_k' È U_k²} (|Г₂u_j| + |Г₁u_j| = 2), (9)

– гиперграф H₁ (X₁, U₁) = H (X, U) : {Г₂U_k' }\ x_k, если

" u_l Î U_k' (|Г₂u_l| > 2), (10)

– кусок гиперграфа H₁^к (X₁^к, U₁^к) = H (X, U) : {Г₂U_k'} \ x_k, если

$ u_l Î U_k' (|Г₂u_l| = 2). (11)

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

над ультраграфом при справедливости условия (8).

Для получения множеств ультраграфа H_U1 (X₁, U₁):

1.     Копируем множества X и U под именами X₁ и U₁ соответственно:

X₁=X ; U₁= U.

2.     Формируем множество образов вершин Г₁X₁, копируя их из множества Г₁X, если i ¹ k. Из образа Г₁x_k удаляем ребра множества U_k':

Г₁X₁ = {Г₁x_i : i ¹ k Ú Г₁x_i \ U_k' : i = k ∕ x_i Î X₁, Г₁x_i Î Г₁X}.

3.     Создаем множество прообразов вершин Г₂X₁, копируя их из множества Г₂X₁, если i ¹ k. Из прообраза Г₂x_k удаляем ребра множества U_k²:

Г₂X₁ = {Г₂x_i : i ¹ k Ú Г₂x_i \ U_k² : i = k ∕ x_i Î X₁, Г₂x_i ÎГ₂X}.

4.     Формируем множество образов ребер Г₂U₁, копируя их из Г₂U и удаляя при этом вершину x_k из образов ребер множества U_t^–:

Г₂U₁ = {Г₂u_j : u_j Î U_k²Ú Г₂u_j \ x_k : u_j Î U_k² ∕ u_j Î U₁, Г₂u_j Î Г₂U}.

5.     Определяем множество прообразов ребер Г₁U₁, копируя их из Г₁U и удаляя при этом вершину x_k из прообразов ребер множества U_k':

Г₁U₁ = {Г₁u_j : u_j Î U_k' Ú Г₁u_j \ x_k : u_j Î U_k' ∕ u_j Î U₁, Г₁u_j Î Г₂U}.

6.     Создаем множество F₁X₁ образов вершин X₁ относительно предиката смежности F₁(X₁, X₁) для чего при i ¹ k:

– копируем F₁x_i из F₁X, если вершина x_k не была смежна вершине x_i или была и остается смежной после её удаления из образов ребер U_k²,

– удаляем из образа F₁x_i вершину x_k, если она становится не смежной x_i после её удаления из образов ребер U_k².

Образ F₁x_k вершины x_k получаем как объединение образов Г₂u_j ребер, инцидентных этой вершине после удаления из её образа Г₁x_k множества ребер U_k':

F₁X₁ = {F₁x_i ∕ x_i Î X₁}, где при i ¹ k:

ìF₁x_i : x_k Ï F₁x_i Ú x_k Î F₁x_i & Г₁x_i Ç {Г₂x_k \ U_k²} ¹ Æ,

F₁x_i = í

îF₁x_i \ x_k : x_k Î F₁x_i & Г₁x_i Ç {Г₂x_k \ U_k²} = Æ,

здесь: F₁x_i Î F₁X, Г₁x_i Î Г₁X, Г₂x_k Î Г₂X.

F₁x_k = È Г₂u_j, где Г₁x_k Î Г₁X, Г₂u_j Î Г₂U.

u_j Î Г₁x_k \ U_k'

Например (смотри рис. 9, б), вершина x₃ осталась бы смежной вершине x₁ после удаления x₃ из образа Г₂u₁ ребра u₁, т. е. F₁x₁ = {x₂, x₃}, если бы существовало ребро u₅, показанное на рисунке точками. Так как в схеме нет цепи с₅ « u₅, то после удаления вершины x₃ из образа Г₂u₁ условие

Г₁x₁ Ç {Г₂x₃ \ u₁} = Æ выполняется и F₁x₁ = {x₂, x₃}\ x₃ = {x₂}.

7.     Создаем множество F₁^-1X₁ прообразов вершин X₁, для чего при i ¹ k:

– копируем F₁^-1x_i из F₁^-1X, если вершине x_k не была смежна вершина x_i или была и остается смежной после её удаления из образов ребер U_k',

– удаляем из прообраза F₁^-1x_i вершину x_k, если этой вершине была и остается смежной вершина x_i после удаления x_k из прообразов ребер U_k'.

Прообраз F₁^-1x_k вершины x_k получаем как объединение образов Г₁u_j ребер, которые инцидентны этой вершине после удаления из её образа Г₁x_k множества ребер U_k²:

F₁^-1X₁ = {F₁^-1x_i ∕ x_i Î X₁}, где при i ¹ k:

ìF₁^-1x_i : x_k Ï F₁^-1x_i Ú x_k Î F₁^-1x_i & Г₂x_i Ç { Г₁x_k \ U_k'} ¹ Æ,

F₁^-1x_i = í

îF₁^-1x_i \ x_k : x_k Î F₁^-1x_i & Г₂x_i Ç { Г₁x_k \ U_k'} = Æ,

здесь: F₁^-1x_i Î F₁^-1X, Г₂x_i Î Г₂X, Г₁x_k Î Г₁X.

F₁^-1x_k = È Г₁u_j, где Г₂x_k Î Г₂X, Г₁u_j Î Г₁U.

u_j Î Г₂x_k \ U_k²

8.     Формируем множество образов F₂U₁ ребер U₁ относительно предиката смежности F₂(U₁, U₁):

– копируя F₂u_j из множества F₂U, если ребру u_j не инцидентна вершина x_k, либо была и остается инцидентной, но не удаляется из прообразов смежных ей ребер,

– получая F₂u_j как объединение ребер, инцидентных вершинам множества Г₂u_j \ x_k, если ребро u_j удаляется из прообраза Г₂x_k вершины x_k, т. е. вершина становится не смежной ему,

– определяя F₂u_j как объединение множества ребер, полученного по предыдущему правилу, и ребер, инцидентных вершине x_k без множества U_k', если ребро u_j не принадлежит множеству ребер, из образов которых удаляется вершина x_k, т. е. эта вершина в результате выполнения операции остается инцидентной ребру u_j и множество ребер, из прообразов которых удаляется вершина x_k, не пусто:

F₂U₁ = {F₂u_j ∕ u_j Î U₁}, здесь

ì F₂u_j : u_j Ï Г₂x_k Ú u_j Î Г₂x_k \ U_k² & U_k' = Æ,

F₂u_j = í È Г₁x_i : u_j Î U_k²,

x_i Î Г₂u_j \ x_k

î {È Г₁x_i} È {Г₁x_k \ U_k'} : u_j Ï U_k² & U_k' ¹ Æ,

x_i Î Г₂u_j \ x_k

 

где F₂u_j Î F₂U, Г₂x_k Î Г₂X, Г₂u_j Î Г₂U, Г₁x_i , Г₁x_k Î Г₁X.

9.     Формируем множество прообразов F₂^-1U₁ ребер U₁ относительно предиката смежности F₂(U₁,U₁):

– копируя F₂^-1u_j из множества F₂^-1U, если ребро u_j не инцидентно вершине x_k,

– удаляя из F₂^-1u_j Î F₂^-1U множество ребер U_k², если ребро u_j было и остается инцидентным вершине x_k,

– удаляя из F₂^-1u_j Î F₂^-1U множество ребер, которым инцидентна вершина x_k, если ребро u_j принадлежит множеству ребер, из прообразов которых удаляется вершина x_k, т. е. этой вершине в результате выполнения операции становится не инцидентно ребро u_j:

F₂^-1U₁ = {F₂^-1u_j ∕ u_j Î U₁}, здесь

ìF₂^-1u_j : u_j Ï Г₁x_k Ú u_j Î Г₁x_k \ U_k' & U_k² = Æ,

F₂^-1u_j = í È Г₂x_i : u_j Î U_k',

x_i Î Г₁u_j \ x_k

î {È Г₂x_i} È {Г₂ x_k \ U_k²} : u_j Ï U_k' & U_k² ¹ Æ,

x_i Î Г₁u_j \ x_k

где F₂^-1u_j Î F₂^-1U, Г₁x_k Î Г₁X, Г₂x_i, Г₂x_k Î Г₂X, Г₁u_j Î Г₁U .

Для куска ультраграфа H_U1^к дополнительно формируем множество внешних ребер U₁^к_ext, в него включаем те из ребер множества U_t, для которых после выполнения операции сумма количества вершин, инцидентных ему, и количества вершин, которому оно инцидентно, равна единице. Определяем также множество внутренних ребер куска U₁^к_int, исключая из U₁^к внешние.

При выполнении условия (9), получаем кусок ультраграфа H_U1^к. Множества X₁^к, U₁^к, Г₁X₁^к, Г₂X₁^к, Г₂U₁^к, Г₁U₁^к, F₁X₁^к, F₁^-1X₁^к, F₂U₁^к, F₂^-1U₁^к определяются по тем же формулам, что и множества ультраграфа H_U1 (X₁, U₁). Множество ребер U₁^к разбивается на подмножества U₁^к_int и U₁^к_ext, такие, что

U₁^к_ext = {u_j Î { U_k² È U_k' }:(|Г₂u_j| + |Г₁u_j|) = 1 ∕ Г₂u_j Î Г₂U₁, Г₁u_j Î Г₁U₁};

U₁^к_int = U₁^к \ U₁^к_ext.

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

При выполнении условия (10) получаем гиперграф H₁ (X₁, U₁):

X₁ = X; U₁ = U;

Г₁X₁ = {Г₁x_i : i ¹ k Ú Г₁x_i \ U_k' : i = k ∕ x_i Î X₁, Г₁x_i Î Г₁X};

Г₂U₁ = {Г₂u_j : u_j Î U_k' Ú Г₂u_j \ x_k : u_j Î U_k' ∕ u_j Î U₁, Г₂u_j Î Г₂U};

F₁X₁ = {F₁x_i ∕ x_i Î X₁}, где при i ¹ k:

ìF₁x_i : x_k Ï F₁x_i Ú x_k Î F₁x_i & Г₁x_i Ç { Г₁x_k \ U_k'} ¹ Æ,

F₁x_i = í

îF₁x_i \ x_k : x_k Î F₁x_i & Г₁x_i Ç { Г₁x_k \ U_k' } = Æ,

здесь: F₁x_i Î F₁X, Г₁x_i, Г₁x_k Î Г₁X,

F₁x_k = È{ Г₂u_j \ x_i : | Г₂u_j | > 1 Ú Г₂u_j : | Г₂u_j| = 1}, где Г₁x_k Î Г₁X, Г₂u_j Î Г₂U;

u_j Î Г₁x_k \ U_k'

F₂U₁ = {F₂u_j ∕ u_j Î U₁}, здесь

ìF₂u_j : u_j Ï Г₁x_k,

F₂u_j = íF₂u_j \ u_i Î U_k' : u_j Î Г₁x_k \ U_k' & Г₂u_j Ç Г₂u_i \ x_k = Æ,

îF₂u_j \ u_i Î Г₁x_k \ U_k' : u_j Î U_k' & Г₂u_j \ x_k Ç Г₂u_i = Æ,

где F₂u_j Î F₂U, Г₁x_k Î Г₂X, Г₂u_j, Г₂u_i Î Г₂U.

Если справедливо условие (11), получаем кусок гиперграфа H₁^к (X₁^к, U₁^к). Множества X₁^к, U₁^к, Г₁X₁^к, Г₂U₁^к , F₁X₁^к, F₂U₁^к формируются по тем же правилам, что и для гиперграфа H₁ (X₁, U₁), а U₁^к_ext = {u_j Î U_k' : |Г₂u_j| = 1 ∕ Г₂u_j Î Г₂U₁^к}, U₁^к_int = U₁^к \ U₁^к_ext.

Если вершина x_k является расщепляющей в отношении множества рёбер {U_k' È U_k²} для ультраграфа (U_k' для гиперграфа) и определено множество вершин X_l некоторой компоненты связности, то множество её рёбер

U_l = {u_j Î È{Г₁x_i È Г₂x_i} ∕ Г₁x_i Î Г₁X, Г₂x_i Î Г₂X},

x_iÎX_l

а остальные множества находим по формулам для компоненты соответствующего вида с учетом того, что x_i и u_j определены на множествах X_l и U_l соответственно (x_i Î X_l и u_j Î U_l).

Поскольку анализ вычислительной сложности данной операции несколько сложнее, чем предыдущих, приведем исходные и промежуточные данные для него по схеме: «наименование формируемого множества» : «количество операций сравнения/копирования в функции от мощности обрабатываемых множеств». Вычислительную сложность будем оценивать для операции над ультраграфом без учета получения образов и прообразов вершин и ребер ультраграфа относительно предикатов смежности F₁(X₁, X₁) и F₂(U₁, U₁).

X₁: |X | = n; U₁: |U| = m;

Г₁X₁: (|X| - 1) × |Г₁x_i| + |Г₁x_i| × |U_k'| + |Г₁x_i|;

Г₂X₁: (|X| -1) × |Г₂x_i| + |Г₂x_i| × |U_k²| + |Г₂x_i|;

Г₂U₁: (|U_k²| + |Г₂u_j|) × (|U| – |U_k²|) + (|Г₂u_j| + |Г₂u_j|) × |U_k²| = (|U| – | U_k²|) × |U_k²| + |Г₂u_j| × (|U| + |U_k²|);

Г₁U₁: (|U_k'| + |Г₁u_j|) × (|U| – |U_k'|) + (|Г₁u_j| + |Г₁u_j|) × |U_k'| = (|U| –

|U_k'|) × | U_k' + |Г₁u_j| × (|U| + |U_k'|).

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

·        в худшем – О(m²) при m > n, если |Г₁x_i| или |U_k'| (|Г₂x_i| или |U_k²|) ограничены величиной m, или – О(n × m), если |Г₂u_j| или|Г₁u_j| ограничены величиной n либо |Г₁x_i| или |Г₂x_i| ограничены величиной m и n> m;

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

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

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

$ u_jÎ {U_k' È U_k²}(|Г₂u_j| + |Г₁u_j| = 1),

или вида G^~ (Æ, u), если для внешних ребер куска H^к (X^к, U^к) выполняется условие

$ u_jÎ U_k' (|Г₂u_j| = 1).

Пример. Отключим в схеме, показанной на рис. 9, а, элемент э₃ от цепей с₁ и с₂. Над моделью схемы в виде ультраграфа (смотри рис. 9, б) выполняется операция удаления вершины x₃ из образов ребер u₁ и u₂, т. е. U_k' = {u₂}и U_k² = {u₁}. Вершина x₃ не является расщепляющей и выполняется условие (8), так как |Г₂u₁| + |Г₁u₁| = 3 и |Г₂u₂| + |Г₁u₂| = 4.

В результате выполнения операции H_U1 (X₁, U₁) = H_U (X, U) : {Г₁U_k', Г₂U_k²} \ x_k получим ультраграф H_U1, у которого:

X₁ = X = {x₁, x₃, x₄, x₅}; U₁ = U = {u₁, u₂, u₃, u₄};

Г₁X₁: Г₁x₁ = {u₁}, Г₁x₂ = {u₄}, Г₁x₃ = {u₂, u₃} \ {u₂} = {u₃}, Г₁x₄ = Æ,

Г₁x₅ = {u₂};

Г₂X₁: Г₂x₁ = Æ, Г₂x₂ = {u₁, u₂}, Г₂x₃ = {u₁, u₄} \ {u₁} = {u₄}, Г₂x₄ = {u₂, u₃}, Г₂x₅ = Æ;

Г₂U₁: Г₂u₁ = {x₂, x₃} \ x₃ = {x₂}, Г₂u₂ = {x₂, x₄}, Г₂u₃ = {x₄}, Г₂u₄ = {x₃};

Г₁U₁: Г₁u₁ = {x₁}, Г₁u₂ = { x₃, x₅} \ x₃ = {x₅}, Г₁u₃ = {x₃}, Г₁u₄ = {x₂};

F₁X₁: F₁x₁ = {x₂, x₃} \ x₃ = {x₂}, F₁x₂ = {x₃}, F₁x₃ = Г₂u₃ = {x₄}, F₁x₄ = Æ, F₁x₅ = {x₂, x₄};

F₁^-1X₁: F₁^-1x₁ = Æ, F₁^-1x₂ = {x₁, x₃, x₅} \ x₃ = {x₁, x₅}, F₁^-1x₃ = Г₁u₄ = {x₂},

F₁^-1x₄ = {x₃, x₅}, F₁^-1x₅ = Æ;

F₂U₁: F₂u₁ = Г₁x₂ = {u₄}, F₂u₂ = {u₄}, F₂u₃ = Æ, F₂u₄ = {u₂, u₃} \ {u₂} = {u₃};

F₂^-1U₁: F₂^-1u₁ = Æ, F₂^-1u₂ = Г₂{Æ} = Æ, F₂^-1u₃ = {u₁, u₄} \ {u₁} = {u₄},

F₂^-1u₄ = {u₁, u₂}.

В гиперграфе, показанном на рис. 9, в, удалим вершину x₃ из образов ребер u₁ и u₂, т. е. U_k' = {u₁, u₂}. Так как |Г₂u₁| = 3 и |Г₂u₂| = 4, в результате выполнения операции

H₁ (X₁, U₁, Г₁X₁, Г₂U₁) = H (X, U, Г₁X, Г₂U) : {Г₂U_k' } \ x_k

получаем гиперграф H₁, в котором:

X₁ = X = {x₁, x₃, x₄, x₅}; U₁ = U = {u₁, u₂, u₃, u₄};

Г₁X₁: Г₁x₁ = {u₁}, Г₁x₂ = {u₁, u₂, u₄}, Г₁x₃ = {u₁, u₂, u₃} \ {u₁, u₂} = {u₃},

Г₁x₄ = {u₂, u₃, u₄}, Г₁x₅ = {u₂};

Г₂U₁: Г₂u₁ = {x₁, x₂, x₃} \ x₃ = {x₁, x₂}, Г₂u₂ = {x₂, x₃, x₄, x₅} \ x₃ = {x₂, x₄, x₅}, Г₂u₃ = {x₃, x₄}, Г₂u₄ = {x₂, x₄}.

При удалении вершины x₃ из образа ребра u₃ получим кусок гиперграфа H₁^к, в котором:

X₁^к = X; U₁^к = U; U₁^к_ext = {u₃}, U₁^к_int = {u₁, u₂};

Г₁X₁^к: Г₁x₁ = {u₁}, Г₁x₂ = {u₁, u₂, u₄}, Г₁x₃ = {u₁, u₂, u₃} \ {u₃} = {u₁, u₂},

Г₁x₄ = {u₂, u₃, u₄}, Г₁x₅ = {u₂};

Г₂U₁: Г₂u₁ = {x₁, x₂, x₃}, Г₂u₂ = {x₂, x₃, x₄, x₅}, Г₂u₃ = {x₃, x₄} \ x₃ = {x₄}, Г₂u₄ = {x₂, x₄}.

Удаление ребра u_k из образов и прообразов вершин ультраграфа H_U и образов вершин гиперграфа H – рис. 10. Соответствует проектной операции отключения цепи с_k от заданного множества элементов схемы.

Рисунок 10 – Фрагмент схемы до и после отключения цепи с₁ от элементов э₃ и э₄ (а), модель схемы в виде ультраграфа H_U и результат операции H_U1 (б), модель в виде гиперграфа H и результаты операции H₁ и H₁^к для вариантов отключения цепи с₁ от элементов э₃, э₄ и э₂, э₃, э₄ (в)

Задается имя удаляемого ребра u_k и:

·  для ультраграфа – подмножество X_k' инцидентных ему вершин, из прообразов которых надо удалить это ребро, и подмножество X_k² вершин, которым инцидентно это ребро и из чьих образов следует его удалить;

·  для гиперграфа – подмножество X_k' инцидентных ребру вершин, из образов которых оно удаляется.

Обозначение операции: H_U (X, U) : {Г₁X_k², Г₂X_k'} \ u_k для ультраграфа и

H(X, U) : Г₁X_k' \ u_k для гиперграфа.

Условия корректности операции:

– для ультраграфа: u_k Î U, X_k' Í Г₂u_k и X_k² Ì Г₁u_k или X_k' Ì Г₂u_k и X_k² Í Г₁u_k или X_k' Ì Г₂u_k и X_k² Ì Г₁u_k;

– для гиперграфа u_k Î U, X_k' Ì Г₂u_k.

При применении операции образуется одна компонента связности, если ни одна из вершин множества {X_k' È X_k²} в ультраграфе (X_k' в гиперграфе) не является расщепляющей и для каждой из них |Г₁x_i| + |Г₂x_i| >1 для ультраграфа и |Г₁x_i| > 1 для гиперграфа. В противном случае граф распадается на компоненты связности и при преобразовании графа необходимо определять компоненты связности и множества их вершин.

Если вершины множества {X_k' È X_k²} или X_k' не являются расщепляю-щими, в результате выполнения операции получаем:

– ультраграф H_U1 (X₁, U₁) = H_U (X, U) : {Г₁X_k², Г₂X_k'} \ u_k, если

|Г₂u_k\ X_k'| + |Г₁u_k\ X_k²| ³ 2, (12)

– кусок ультраграфа H_U1^к (X₁^к, U₁^к) = H_U (X, U) : { Г₁X_k², Г₂X_k'} \ u_k, если

|Г₂u_k \ X_k'| + |Г₁u_k \ X_k²| = 1, (13)

– гиперграф H₁ (X₁, U₁) = H (X, U) : Г₁X_k' \ u_k, если

|Г₂u_k \ X_k'| ³ 2 , (14)

– кусок гиперграфа H₁^к (X₁^к, U₁^к) = H (X, U) : Г₁X_k' \ x_k, если

|Г₂u_k \ X_k'| = 1 . (15)

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

Для получения результата – ультраграфа H_U1 (X₁, U₁):

1.     Копируем множества X и U под именами X₁ и U₁ соответственно:

X₁ = X; U₁ = U.

2.     Формируем множество образов вершин Г₁X₁, копируя их из множества Г₁X и удаляя u_k из образов вершин множества X_k²:

Г₁X₁ = {Г₁x_i : x_i Ï X_k² Ú Г₁x_i \ u_k : x_i Î X_k² ∕ x_i Î X₁, Г₁x_i Î Г₁X}.

3.     Получаем множество прообразов вершин Г₂X₁, копируя их из множества Г₂X и удаляя u_k из прообразов вершин множества X_k':

Г₂X₁ = {Г₂x_i : x_i Ï X_k' Ú Г₂x_i \ u_k : x_i Î X_k' ∕ x_i Î X₁, Г₁x_i Î Г₁X}.

4.     Формируем множество образов ребер Г₂U₁, копируя их из Г₂U, если j ¹ k, и удаляя из образа Г₂u_k вершины, принадлежащие множеству X_k':

Г₂U₁ = {Г₂u_j : j ¹ k Ú Г₂u_j \ X_k' : j = k ∕ u_j Î U₁, Г₂u_j Î Г₂U}.

3.     Создаем множество прообразов ребер Г₁U₁, копируя их из Г₁U, если j ¹ k, и удаляя из прообраза Г₁u_k вершины, принадлежащие множеству X_k²:

Г₁U₁ = {Г₁u_j : j ¹ k Ú Г₁u_j \ X_k² : j = k ∕ u_j Î U₁, Г₁u_j Î Г₁U}.

4.     Определяем множество образов F₁X₁ для чего:

– копируем F₁x_i из F₁X, если вершине x_i не инцидентно ребро u_k или было и остается инцидентным после своего удаления из образов вершин множества X_k² и при этом оно не удаляется из прообразов инцидентных ей вершин, т. е. X_k' = Æ,

– получаем F₁x_i как объединение множества вершин, инцидентных рёбрам образа Г₁x_i без ребра u_k, если оно удаляется из образа вершины x_i, т.е.

x_i Î X_k²,

– находим F₁x_i как объединение множества вершин, сфомированного по предыдущему правилу, и множества вершин, инцидентных ребру u_k, без множества X_k', если ребро u_k не удаляется из образа вершины x_i, т. е. x_i Ï X_k², и X_k' ¹ Æ:

F₁X₁ = { F₁x_i ∕ x_i Î X₁}, где

ì F₁x_i : x_i Ï Г₁u_k Ú x_i Î Г₁u_k \ X_k² & X_k' = Æ,

F₁x_i = í È Г₂u_j : x_i Î X_k²,

u_j Î Г₁x_i \ u_k

î {È Г₂u_j} È {Г₂u_k \ X_k'} : x_i Ï X_k² & X_k' ¹ Æ,

u_j Î Г₁x_i \ u_k

где F₁x_i Î F₁X, Г₁u_k Î Г₁U, Г₂u_j, Г₂u_k Î Г₂U, Г₁x_i Î Г₁X.

5.     Формируем множество прообразов F₁^-1X₁ для чего:

– копируем F₁^-1x_i из F₁^-1X, если вершина x_i не инцидентна ребру u_k или была и остается инцидентной после удаления ребра из прообразов вершин множества X_k' и при этом ребро не удаляется из образов вершин, которым она инцидентна, т. е. X_k² = Æ,

– получаем F₁^-1x_i как объединение множества вершин, которым инци-дентны ребра прообраза Г₂x_i без ребра u_k, если это ребро удаляется из прообраза вершины x_i, т. е. x_i Î X_k',

– находим F₁^-1x_i как объединение множества вершин, определенного по предыдущему правилу, и множества вершин, которым инцидентно ребро u_k, без множества X_k², если ребро u_k не удаляется из прообраза вершины x_i, т. е. x_i Ï X_k', и X_k² ¹ Æ:

F₁^-1X₁= { F₁^-1x_i ∕ x_iÎX₁}, где

ì F₁^-1x_i : x_i Ï Г₂u_k Ú x_i Î Г₂u_k \ X_k' & X_k² = Æ,

F₁^-1x_i = í È Г₁u_j : x_i Î X_k',

u_j Î Г₂x_i\ u_k

î{È Г₁u_j } È {Г₁u_k \ X_k²} : x_i Ï X_k' & X_k² ¹ Æ,

u_j Î Г₂x_i \ u_k

где F₁^-1x_i Î F₁^-1X, Г₂u_k Î Г₂U, Г₁u_k, Г₁u_j Î Г₁U, Г₂x_i Î Г₂X.

6.     Получаем множество образов F₂U₁ ребер U₁ относительно предиката смежности F₂(U₁, U₁) для чего при i ¹ k:

– копируем F₂u_j из F₂U₁, если ребро u_k не было смежно ребру u_j или было и остается смежным после его удаления из образов вершин X_k²,

– удаляем из образа F₂u_j ребро u_k, если оно становится не смежным ребру u_j после его удаления из образов вершин X_k².

Образ F₂u_k ребра u_k получаем как объединение образов Г₁x_i вершин, инцидентных этому ребру после удаления из его образа Г₂u_k множества вершин X_k':

F₂U₁ = {F₂u_j ∕ u_j Î U₁}, где при i ¹ k:

ìF₂u_j : Г₂u_j Ç X_k² = Æ,

F₂u_j = í

îF₂u_j \ u_k : u_k Î F₂u_j & Г₂u_j Ç {Г₁u_k \ X_k²} = Æ,

здесь: F₂u_j Î F₂U, Г₂u_j Î Г₂U, Г₁u_k Î Г₁U.

F₂u_k = È Г₁x_i, где Г₁x_i Î Г₁X, Г₂u_k Î Г₂U.

x_i Î Г₂u_k \ X_k'

7.     Получаем множество прообразов F₂^-1U₁ ребер U₁ относительно предиката смежности F₂(U₁, U₁) для чего при i ¹ k:

– копируем F₂^-1u_j из F₂^-1U₁, если ребру u_k не было смежно ребро u_j или было и остается смежным после удаления u_k из прообразов вершин X_k',

– удаляем из прообраза F₂^-1u_j ребро u_k, если ребро u_j становится не смежным ребру u_k после его удаления из прообразов вершин множества X_k'.

Прообраз F₂^-1u_k ребра u_k получаем как объединение прообразов Г₂x_i рёбер, которым инцидентна вершина x_i после удаления множества вершин X_k²из прообраза Г₁u_k ребра u_k:

F₂^-1U₁ = {F₂^-1u_j ∕ u_j Î U₁}, где при i ¹ k:

ìF₂^-1u_j : Г₁u_j Ç X_k' = Æ,

F₂^-1u_j = í

îF₂^-1u_j \ u_k : u_k Î F₂^-1u_j & Г₁u_j Ç {Г₂u_k \ X_k'} = Æ,

здесь: F₂^-1u_j Î F₂^-1U, Г₁u_j Î Г₁U, Г₂u_k Î Г₂U.

F₂^-1u_k = È Г₂x_i, где Г₂x_i Î Г₂X, Г₁u_k Î Г₁U.

x_i Î Г₁u_k \ X_k²

Множества аналитического представления куска ультраграфа H_U1^к получаем по таким же формулам; дополнительно формируем множество внешних рёбер U₁^к_ext, в которое включаем ребро u_k, и определяем множество внутренних рёбер куска U₁^к_int, исключая из U₁^к ребро u_k:

U₁^к_ext = {u_k }, U₁^к_int = U₁^к \ u_k.

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

При выполнении условия (14) получаем множества гиперграфа H₁:

X₁ = X; U₁ = U;

Г₁X₁ = {Г₁x_i : x_i Ï X_k' Ú Г₁x_i \ u_k : x_i Î X_k' ∕ x_i Î X₁, Г₁x_i Î Г₁X};

Г₂U₁ = {Г₂u_j : j ¹ k Ú Г₂u_j \ X_k' : j = k ∕ u_j Î U₁, Г₂u_j Î Г₂U};

F₁X₁ = { F₁x_i ∕ x_i Î X₁}, здесь:

ìF₁x_i : x_i Ï Г₂u_k,

F₁x_i = í

î È {Г₂u_j \ x_i : |Г₂u_j| > 1 Ú Г₂u_j : |Г₂u_j| = 1} : x_i Î X_k',

u_j Î Г₁x_i \ u_k

F₁x_i Î F₁X, Г₂u_j, Г₂u_k Î Г₂U, Г₁x_i Î Г₁X;

F₂U₁ = { F₁u_j ∕ u_j Î U₁}, здесь для u_j ¹ u_k

ìF₂u_j : Г₂u_j Ç X_k' = Æ,

F₂u_j = í

î F₂u_j \ u_k : u_j Î F₂u_k & Г₂u_j Ç {Г₂u_k \ X_k'} = Æ,

здесь: F₂u_j Î F₂U, Г₂u_j, Г₂u_k Î Г₂U и

F₂u_k = È {Г₁x_i \ u_k : | Г₂u_k| >1 Ú Г₁x_i : |Г₂u_k | = 1},

x_i Î Г₂u_k \ X _k'

здесь: F₂u_j Î F₂U, Г₂u_j, Г₂u_k Î Г₂U, Г₁x_i Î Г₁X.

В случае выполнения условия (15) получаем кусок гиперграфа

H_U1^к (X₁^к, U₁^к), в котором множества X₁^к, U₁^к, Г₁X₁^к, Г₂U₁^к, F₁X₁^к, F₂U₁^к формируются по тем же правилам, что и множества гиперграфа H₁ (X₁, U₁), а U₁^к_ext = {u_k}, U₁^к_int = U₁^к \ u_k.

Если результатом операции является несколько компонент связности и определены множества их вершин {X_l}, множество ребер каждой компоненты будет:

U_l = {u_j Î È {Г₁'x_i È Г₂'x_i} ∕ Г₁x_i Î Г₁X, Г₂x_i Î Г₂X},

x_iÎX_l

где Г₁'x_i = Г₁x_i, если x_i Ï X_k² и Г₁'x_i = Г₁x_i \ u_k, если x_i Î X_k², Г₁x_i Î Г₁X,

Г₂'x_i = Г₂x_i, если x_i Ï X_k' и Г₂'x_i = Г₂x_i \ u_k, если x_i Î X_k', Г₂x_i Î Г₂X.

Остальные множества аналитческого задания компоненты определяются по соответствующим формулам для компоненты данного вида.

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

·        в худшем – О(n × m) при m > n, если|Г₁x_i| или|Г₂x_i| ограничены m либо|Г₂u_j| или |Г₁u_j| ограничены n; О(n²) при n > m, если |Г₂u_j| и |X_k'| либо |Г₁u_j| и |X_k²| ограничены величинами m и n соответственно;

·        в лучшем О(n) при n> m и О(m) при m > n, если|Г₁x_i|,|Г₂x_i|,|Г₂u_j| , |Г₁u_j|, |X_k'| и |X_k²| ограничены константой.

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

Операция может быть применена к куску ультра- или гиперграфа. Результатом будет кусок H_U1^к или H₁^к соответственно. Если ребро u_k было внутренним и выполнялось условие (13) для ультраграфа или (15) для гиперграфа, то это ребро исключается из множесва внутренних и добавляется в множество внешних.

Пример. В схеме, показанной на рис. 10, а, отсоединим цепь с₁ от эле-ментов э₃ и э₄. Для модели схемы в виде ультраграфа (смотри рис. 10, б) множества X_k² = {x₄}, X_k' = {x₃}, т.е. будет выполняться операция удаления ребра u₁ из образа вершины x₄ и прообраза вершины x₃.

Результатом операции H_U1 (X₁, U₁) = H_U (X, U) : { Г₁X_k², Г₂X_k'} \ u_k будет ультраграф H_U1, так как вершины x₃ и x₄ не являются расщепляющими и выполняется условие (12). Образы и прообразы вершин и ребер ультраграфа H_U1 относительно предикатов инцидентности и смежности будут:

Г₁X₁: Г₁x₁ = {u₁, u₂}, Г₁x₂ = Г₁x₃ = Æ, Г₁x₄ = {u₁} \ u₁ = Æ;

Г₂X₁: Г₂x₁ = Æ, Г₂x₂ = {u₁, u₂}, Г₂x₃ = {u₁, u₂} \ u₁ = {u₂}, Г₂x₄ = {u₂};

Г₂U₁: Г₂u₁ = {x₂, x₃} \ {x₃} = {x₂}, Г₂u₂ = {x₂, x₃, x₄};

Г₁U₁: Г₁u₁ = {x₁, x₄} \ {x₄} = {x₁}, Г₁u₂ = {x₁};

F₁X₁: F₁x₁ = Г₂u₂ È Г₂u₁ \ {x₃} = {x₂, x₃, x₄}; F₁x₂ = F₁x₃ = Æ, F₁x₄ = Æ;

F₁^-1X₁: F₁^-1x₁ = Æ, F₁^-1x₂ = Г₁u₂ È Г₁u₁ \ {x₄} = {x₁}, F₁^-1x₃ = Г₁u₂ = {x₁},

F₁^-1x₄ = {x₁};

F₂U₁: F₂u₁ = Г₁x₂ = Æ, F₂u₂ = F₂u₂ \ u₁ = Æ;

F₂^-1U₁: F₂^-1u₁ = Г₂x₁ = Æ, F₂^-1u₁ = Æ.

В гиперграфе, показанном на рис. 10, в, удалим ребро u₁ из образов вершин x₃ и x₄. Так как |Г₂u₁ \ {x₃, x₄}| = 2, в результате выполнения операции H₁ (X₁, U₁) = H (X, U) : {Г₁X_k², Г₂ X_k'} \ u_k получаем гиперграф H₁, изображенный на том же рисунке, в котором:

Г₁X₁: Г₁x₁ = Г₁x₂ = {u₁, u₂}, Г₁x₃ = Г₁x₄ = {u₁, u₂} \ u₁ = {u₂};

Г₂U₁: Г₂u₁ = {x₁, x₂, x₃, x₄} \ {x₃, x₄} = {x₁, x₂}, Г₂u₂ = {x₁, x₂, x₃, x₄};

F₁X₁: F₁x₁ = {x₂, x₃, x₄}, F₁x₂ ={x₁, x₃, x₄}, F₁x₃ ={x₁, x₁, x₄},

F₁x₄ = {x₁, x₂, x₃};

F₂U₁: F₂u₁ = {u₂}, F₂u₂ = {u₁}.

При удалении ребра u₁ из образов вершин x₂, x₃, x₄ получим кусок ультра- H_U1^к или гиперграфа H₁^к, аналитическое представление которых читателю нетрудно получить самостоятельно.

Формирование части ультраграфа H_U или гиперграфа H – рис. 11. Реализует проектную операцию определения (локализации) части схемы по заданному множеству элементов Э₁ É Э, где Э – множество элементов схемы.

Рисунок 11 – Схема и выделенный фрагмент (а); модель в виде ультраграфа H_U, сформированные кусок H_U1^к – две компоненты связности и подграф H_U1 – три компоненты связности (б); модель в виде гиперграфа, кусок и подграф гиперграфа H₁^к и H₁ – две и три компоненты связности соответственно (в)

Операция имеет две модификации: формирование куска H_U1^к ультраграфа H_U или H₁^к гиперграфа H и формирование подграфа H_U1 ультраграфа или подграфа H₁ гиперграфа.

Задается множество X₁ вершин формируемой части графа.

Обозначение операции: H_U (X, U) ¤ X₁ или H (X, U) ¤ X₁ для формирования куска ультра- или гиперграфа и H_U (X,U) ○ X₁ или H (X, U) ○ X₁ для формирования подграфов тех же графов.

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

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

– кусок ультраграфа H_U1^к (X₁^к, U₁^к) = H_U (X, U) ¤ X₁или

– гиперграфа H₁^к (X₁^к, U₁^к) = H (X, U) ¤ X₁ либо

– подграф ультраграфа H_U1 (X₁, U₁) = H_U (X, U) ○ X₁ или

– подграф гиперграфа H₁ (X₁, U₁) = H (X, U) ○ X₁.

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

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

получении куска H_U1^к (X₁^к, U₁^к) ультраграфа H_U (X, U).

1.     Копируем множество X₁ под наименованием X₁^к : X₁^к = X₁.

2.     Формируем множество U₁^к, включая в него при копировании те рёбра множества U, которые инцидентны вершинам множества X₁ и которым инцидентны эти вершины:

U₁^к = Г₁(X₁^к) È Г₂(X₁^к), где Г₁(X₁^к) = È Г₁x_i, Г₂(X₁^к)= È Г₂x_i,

x_i Î X₁^к x_i Î X₁^к

где Г₁x_i Î Г₁X, Г₂x_i Î Г₂X, Г₁(X₁^к) – множество ребер, которые инцидентны вершинам множества X₁, Г₂(X₁^к) – множество ребер, которым инцидентны эти вершины.

Примечание: множество U₁^к можно определить другим способом, а именно:

U₁^к = {u_j Î U : {Г₂u_j È Г₁u_j} Ç X₁^к ¹ Æ / Г₂u_j Î Г₂U, Г₁u_j Î Г₁U}.

Однако использование этой формулы в данном случае нецелесообразно, так как это приведет к тому, что вычислительная сложность операции «в лучшем» будет О(m) даже при |Г₂u_j| = |Г₁u_j| = |X₁^к | = const. Аналогичная формула будет использована для определения U₁ подграфа ультраграфа. Читателю предлагается самому продумать основания для её применения.

3.     Определяем множество U₁^к_int внутренних ребер, включая в него те ребра из U₁^к, у которых все вершины их образов и прообразов принадлежат множеству вершин X₁^к:

U₁^к_int = {u_j Î U₁^к : {Г₂u_j È Г₁u_j} Í X₁^к / Г₂u_j Î Г₂U, Г₁u_j Î Г₁U}.

4.     Создаем множество U₁^к_ext внешних ребер, исключая из множества U₁^к внутренние ребра куска ультраграфа:

U₁^к_ext = U₁^к \ U₁^к_int.

5.     Получаем множество Г₁X₁^к образов вершин куска H_U1^к, записывая в него из Г₁X образы x_i Î X₁^к:

Г₁X₁^к = {Г₁x_i Î Г₁X / x_i Î X₁^к }.

6.     Формируем множество Г₂X₁^к прообразов вершин куска H_U1^к, записывая в него из Г₂X прообразы x_i Î X₁^к:

Г₂X₁^к = {Г₂x_i Î Г₂X / x_i Î X₁^к }.

7.     Создаем множество Г₂U₁^к образов ребер куска H_U1^к так, что образом внутреннего ребра является образ Г₂u_j одноименного ребра в Г₂U ультраграфа H_U, а образ внешнего ребра определяется как Г₂u_j Ç X₁^к, т. е. удалением вершин, не принадлежащих X₁^к:

Г₂U₁^к = {Г₂u_j Ç X₁^к / u_j Î U₁^к, Г₂u_j Î Г₂U}.

8.     Создаем множество Г₁U₁^к прообразов ребер куска H_U1^к так, что прообразом внутреннего ребра является прообраз Г₁u_j одноименного ребра в Г₁U ультраграфа H_U, а прообраз внешнего ребра определяется как Г₁u_j Ç X₁^к, т. е. удалением вершин, не принадлежащих X₁^к:

Г₁U₁^к = {Г₁u_j Ç X₁^к / u_j Î U₁^к, Г₁u_j Î Г₁U}.

9.     Определяем множество F₁X₁^к образов и прообразов F₁^-1X₁^к вершин относительно предиката смежности F₁(X₁^к, X₁^к), оставляя в F₁x_i Î F₁X и F₁^-1x_i Î F₁^-1X только те вершины, которые принадлежат множеству X₁^к:

F₁X₁^к = {F₁x_i Ç X₁^к / x_i Î X₁^к, F₁x_i Î F₁X},

F₁^-1X₁^к = {F₁^-1x_i Ç X₁^к / x_i Î X₁^к, F₁^-1x_i Î F₁^-1X}.

10.      Формируем множество F₂U₁^к образов и прообразов F₂^-1U₁^к рёбер относительно предиката смежности F₂(U₁^к, U₁^к), оставляя в F₂u_j Î F₂U и F₂^-1u_j Î F₂^-1U только те ребра, которые принадлежат множеству U₁^к:

F₂U₁^к = { F₂u_j Ç U₁^к / u_j Î U₁^к, F₁u_j Î F₂U },

F₂^-1U₁^к = { F₂^-1u_j Ç U₁^к / u_j Î U₁^к, F₂^-1 u_j Î F₂^-1U }.

Для данной операции целесообразно подробно рассмотреть определение количества операций формирования множества ребер куска ультраграфа U₁^к.

Формирование множества U₁^к подразумевает:

– определение множества ребер Г₁(X₁^к), которые инцидентны вершинам множества X₁, и множества ребер Г₂(X₁^к), которым инцидентны эти вершины. В предположении, что все ребра в U_i = Г₁x_i для всех x_i Î X₁^к различны, реализация выражений

È Г₁x_i и È Г₂x_i

x_i Î X₁^к x_i Î X₁^к

потребует (|Г₁x_i|² + |Г₂x_i|²) ´ St операций , где t = 1, |X₁^к|;

– определение множества ребер U₁^к = Г₁(X₁^к) È Г₂(X₁^к), что потребует |Г₁(X₁^к)| ´ |Г₂(X₁^к)| операций сравнения.

Мощности получаемых множеств будут:

– |Г₁(X₁^к)| и |Г₂(X₁^к)| ограничены m или константой, если |Г₁x_i| и |Г₂x_i| ограничены теми же величинами;

– |U₁^к| – ограничена m или константой, если |Г₁(X₁^к)| и |Г₂(X₁^к)| ограничены теми же величинами.

Таким образом асимптотическая оценка сложности формирования множества U₁^к в худшем будет О(m²×n²), если |Г₁x_i|, |Г₂x_i| ограничены m и |X₁^к| ограничена n, и в лучшем О(1), если они ограничены константой.

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

·        в худшем О(n²×m²), если |Г₁x_i|, |Г₂x_i| ограничены m и |X₁^к| ограничена n;

·        в лучшем О(m×n), если |Г₂u_j| = const, а |U₁^к| и |X₁^к| ограничены m и n соответственно или О(1), если |X₁^к|, |U₁^к_ext| и |Г₂u_j| ограничены константой.

Формальное описание выполнения операции получения подграфа H_U1 (X₁, U₁) ультраграфа H_U (X, U):

U₁ = {u_j Î U : {Г₂u_j È Г₁u_j} Í X₁ / Г₂u_j Î Г₂U, Г₁u_j Î Г₁U}(в отличие от куска ультраграфа у подграфа в множество U₁ входят только внутренние ребра);

Г₁X₁ = {Г₁x_i Ç U₁ / x_i Î X₁, Г₁x_i Î Г₁X};

Г₂X₁ = {Г₂x_i Ç U₁ / x_i Î X₁, Г₂x_i Î Г₂X};

Г₂U₁ = {Г₂u_j Î Г₂U / u_j Î U₁};

Г₁U₁ = {Г₁u_j Î Г₁U / u_j Î U₁};

F₁X₁ = {F₁x_i : F₁x_i Í X₁ Ú È Г₂u_j : F₁x_i Ë X₁ / x_i Î X₁, F₁x_i Î F₁X,

u_j Î Г₁x_i Ç U₁

Г₂u_j Î Г₂U, Г₁x_i Î Г₁X };

F₁^-1X₁ = {F₁^-1x_i : F₁^-1x_i Í X₁ Ú È Г₁u_j : F₁^-1x_i Ë X₁ / x_i Î X₁, F₁^-1x_i Î F₁^-1X,

u_j Î Г₂x_i Ç U₁

Г₁u_j ÎГ₁U, Г₂x_i Î Г₂X };

F₂U₁ = {F₂u_j Ç U₁ / u_j Î U₁, F₁u_j Î F₂U};

F₂^-1U₁ = {F₂^-1u_j Ç U₁ / u_j Î U₁, F₂^-1u_j Î F₂^-1U}.

Формальное описание выполнения операции получения куска

H₁^к (X₁^к, U₁^к) гиперграфа H (X, U).

X₁^к = X₁; U₁^к = Г₁(X₁^к), где Г₁(X₁^к) = È Г₁x_i, Г₁x_i Î Г₁X;

x_iÎX₁^к

U₁^к_int = {u_j Î U₁^к : Г₂u_j Í X₁^к / Г₂u_j Î Г₂U}, U₁^к_ext = U₁^к \ U₁^к_int;

Г₁X₁^к = {Г₁x_i Î Г₁X / x_i Î X₁^к};

Г₂U₁^к = {Г₂u_j : u_j Î U₁^к_int Ú Г₂u_j Ç X₁^к : u_j Î U₁^к_ext / u_j Î U₁^к, Г₂u_j Î Г₂U};

F₁X₁^к = {F₁x_i Ç X₁^к / x_i Î X₁^к, F₁x_i Î F₁X};

F₂U₁^к = {F₂u_j Ç U₁^к / u_j Î U₁^к, F₁u_j Î F₂U}.

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

U₁ = {u_j Î U : Г₂u_j Í X₁ / Г₂u_j Î Г₂U};

Г₁X₁ = {U_1i Ç U₁ / x_i Î X₁, U_1i = Г₁x_i Î Г₁X};

Г₂U₁ = {Г₂u_j Î Г₂U / u_j Î U₁};

F₁X₁ = {F₁x_i / x_i Î X₁}, где

ìF₁x_i : F₁x_i Í X₁, здесь и далее F₁x_i Î F₁X,

F₁x_i = í È X_i : F₁x_i Ë X₁, где X_i = Г₂u_j \ x_i : |Г₂u_j | >1 Ú Г₂u_j : | Г₂u_j| = 1,

îu_j Î Г₁x_i Ç U₁

Г₁x_i Î Г₁X, Г₂u_j Î Г₂U;

F₂U₁ = { F₂u_j Ç U₁ / u_j Î U₁, F₁u_j Î F₂U}.

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

Операция может быть применена для выделения части из куска ультра- или гиперграфа. В этом случае при определении множества внутренних ребер U₁^к_int необходимо дополнительно проверять не было ли ребро внешним в куске H_U^к. Тогда при выполнении операции, например над куском ультраграфа, выражение в п.п. 3 должно иметь вид:

U₁^к_int = {u_j Î U₁^к & u_j Ï U^к_ext : {Г₂u_j È Г₁u_j} Í X₁^к / Г₂u_j Î Г₂U,

Г₁u_j Î Г₁U}.

Пример. В схеме, показанной на рис. 11, а, выделим фрагмент, включающий элементы э₁, э₂, э₃, э₄, э₅. Тогда множество вершин формируемого куска ультраграфа H_U1^к – X₁^к = X₁ = {x₁, x₂, x₃, x₄, x₅}. Остальные множества аналитического представления этого куска в результате выполнения операции H_U1^к (X₁^к,U₁^к) = H_U (X,U) ¤ X₁ будут:

U₁^к = Г₁(X₁) È Г₂(X₁) = {u₄, u₃, u₁ } È {u₄, u₁} = { u₄, u₃, u₁}, U₁^к_int = {u₄}, так как только для ребра u₄ справедливо условие Г₂u₄ È Г₁u₄ = { x₂, x₅, x₁} Í X₁, и U₁^к_ext = {u₃, u₁ };

Г₁X₁^к = {Г₁x_i Î Г₁X / x_i Î X₁} = {{u₄}, {u₃}, Æ, {u₁}, Æ};

Г₂X₁^к = {Г₂x_i Î Г₂X / x_i Î X₁} = {Æ, {u₄}, {u₁}, Æ, {u₄}};

Г₂U₁^к : Г₂u₄ = {x₂, x₅}, Г₂u₃ = {x₁₀, x₁₁} Ç X₁^к = Æ,

Г₂u₁ = {x₃, x₆} Ç X₁^к = {x₃};

Г₁U₁^к : Г₁u₄ = {x₁}, Г₁u₃ = {x₂} Ç X₁^к = {x₂}, Г₁u₁ = {x₄} Ç X₁^к ={x₄};

F₁X₁^к : F₁x₁ = {x₂, x₅} Ç X₁^к = {x₂, x₅}, F₁x₂ = {x₁₀, x₁₁} Ç X₁^к = Æ, F₁x₃ = Æ, F₁x₄ = {x₃, x₆} Ç X₁^к = {x₃}, F₁x₅ = Æ;

F₁^-1X₁^к : F₁^-1x₁ = Æ, F₁^-1x₂ = {x₁} Ç X₁^к = {x₁}, F₁^-1x₃ = {x₄} Ç X₁^к = {x₄},

F₁^-1x₄ = Æ, F₁^-1x₅ = {x₁} Ç X₁^к = {x₁};

F₂U₁^к : F₂u₄ = {u₃} Ç U₁^к = {u₃}, F₂u₃ = Æ, F₂u₁ = {u₂} Ç U₁^к =Æ;

F₂^-1U₁^к : F₂^-1u₄ =Æ, F₂^-1u₃ = {u₄} Ç U₁^к = {u₄}, F₂^-1u₁ = Æ.

Для подграфа ультраграфа при том же X₁ получим:

U₁ = {u₄};

Г₁X₁ = {{u₄}, Æ, Æ, Æ, Æ}; Г₂X₁ = {Æ, {u₄}, Æ, Æ, {u₄}};

Г₂U₁ : Г₂u₄ = {x₂, x₅}; Г₁U₁ : Г₁u₄ = {x₁};

F₁X₁ : F₁x₁ = {x₂, x₅}, F₁x₂ = F₁x₃ = F₁x₄ = F₁x₅ = Æ;

F₁^-1X₁ : F₁^-1x₁ = Æ, F₁^-1x₂ = {x₁} , F₁^-1x₃ = Æ, F₁^-1x₄ = Æ, F₁^-1x₅ = {x₁};

F₂U₁ : F₂u₄ = {u₃} Ç U₁ = Æ; F₂^-1U₁^к : F₂^-1u₄ = Æ.

При использовании в качестве модели схемы гиперграфа множества аналитического представления куска H₁^к (X₁^к, U₁^к, Г₁X₁^к, Г₂U₁^к) будут:

X₁ = {x₁, x₂, x₃, x₄, x₅};

U₁^к = Г₁(X₁) = {u₄, u₃, u₁}, U₁^к_int = {u₄}, U₁^к_ext = {u₃, u₁};

Г₁X₁^к = {Г₁x_i Î Г₁X / x_i Î X₁} = {{u₄}, {u₃,u₄}, {u₁}, {u₁}, u₄}};

Г₂U₁^к : Г₂u₄ = {x₁, x₂, x₅}, Г₂u₃ = {x₂, x₁₀, x₁₁} Ç X₁^к = {x₂},

Г₂u₁ = {x₃, x₄, x₆} Ç X₁ = {x₃, x₄};

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

 

Литература

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