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

УДК 004.3 +519.6  

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

gsivanova@gmail.com

                                                                          

 

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

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

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

Предикаты Г₁ (X, U) и Г₂ (U, X)  таковы, что для всех графов

при X ¹ Æ и U ¹ Æ  справедливо:   

   Г₁(x_i,u_j) = «и» ® ( Г₂(u_j,x_k) = «и» Ú Г₂(u_j,x_i) = «и»).                        (1)

Положим X = {x₁,x₂}, U = {u₁}. Тогда, изображая вершины кружками, ребра – отрезком дуги или овалом, истинность предиката Г₁(x_i,u_j) – стрелкой, идущей от x_i  к u_j, а истинность предиката  Г₂(u_j, x_i) – стрелкой, идущей от  u_j к x_i, получим, если Г₁(x₁,u₁) = «и» и Г₂(u₁,x₁) = «л», геометрическую интерпретацию выражения (1), представленную на рисунке 1,а. При  Г₁(x₁,u₁) = «и» и Г₂(u₁,x₁) = «и» геометрическая интерпретация этого выражения показана на рисунке 1,б.

Рисунок 1 – Геометрическая интерпретация выражения (1)

На элементах  множеств X и U определены также двуместные предикаты-отношения смежности F₁ (X, X) и  F₂ (U, U). Вершине x_i смежна вершина x_t, если существует ребро u_j, инцидентное вершине x_i, такое, что вершина x_t инцидентна этому же ребру. Ребру u_j смежно ребро u_k, если существует вершина x_i, инцидентная ребру u_j, такая, что ребро u_k инцидентно этой же вершине. Таким образом, понятие смежности вторично по отношению к понятию инцидентности.

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

Ультраграфы. Определенный выше граф называется ультраграфом  H_U (X, U, Г₁, Г₂), если предикаты Г₁ (X, U) и Г₂ (U, X) обладают следующим свойством

                         $ u_j Î U  (|Г₁u_j| + |Г₂u_j| ) >2,                                        (2)

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

         Если допустить возможность существования в ультраграфе петель, то наличие петли устанавливается условием

                        $ u_j Î U (Г₁u_j = Г₂u_j = x _i).                                           (3)

На рисунке 2 приведено изображение ультраграфа, у которого  X = {x₁, x₂, x₃, x₄, x₅}, U = {u₁, u₂, u₃ }, причем u₃ – петля при вершине x₅.

Рисунок 2 – Ультраграф

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

Рисунок 3 – Изображение ультраграфа, показанного на рисунке 2, в виде двудольного графа (а) и геометрическая интерпретация предикатов Г₂^-1 (X, U) и Г₁^-1 (U, X) этого же ультраграфа (б)

Представление ультраграфа матрицами инцидентности. Полным и достаточно наглядным способом формального задания ультраграфа является его представление через две матрицы инцидентности А₁ и A₂, где А₁ – матрица истинности предиката Г₁ (X, U) и А₂ – матрица истинности предиката Г₂ (U, X).

Матрица инцидентности А₁, задающая связь между вершинами и ребрами, – это прямоугольная  матрица размером n ´ m,  где n = |X|, m = |U|. Элементы этой матрицы определяются по правилу

                         ì 1 – если Г₁(x_i,u_j) = «и»

             a_{1 i,j}  = í                                              ,

                           î 0 – если Г₁(x_i,u_j) = «л»

где i = 1, n;   j = 1, m.

Матрица инцидентности А₂ задает связь между ребрами и вершинами. Ее строки соответствуют ребрам, а столбцы – вершинам (размер матрицы m ´ n). Элементы матрицы А₂ определяются по правилу

                       ì 1 – если Г₂ (u_j,x_i) = «и»,

             a_{2 j,i} = í

                         î 0 – если Г₂ (u_j,x_i) = «л».

Матрицы  А₁ и А₂  ультраграфа, показанного на рисунке 2, имеют вид:

			u1	u2	u3
		x1	1	1	0					x1	x2	x3	x4	x5
		x2	0	0	0				u1	0	1	1	0	0
A1	=	x3	0	0	0	,	A2	=	u2	0	0	0	1	0	.
		x4	0	0	0				u3	0	0	0	0	1
		x5	1	0	1

Аналитическое представление ультраграфа – образами и прообразами множеств вершин и ребер относительно предикатов Г₁ (X, U) и Г₂ (U, X). Аналитически ультраграф будет задан полностью, если заданы множества вершин X, ребер U и образы этих множеств относительно предикатов Г₁ (X, U) и Г₂ (U, X) соответственно. Рассмотрим сначала данный способ представления.

 Образом множества X относительно предиката Р(X,Y) является множество подмножеств

              РX = {Рx_i / x_i Î X},    Рx_i = {y_j Î Y: Рx_i (y_j) = «и»},

где Рx_i – характеристическое подмножество предиката-свойства Рx_i(Y), т. е. образ элемента x_i Î X  относительно этого предиката.

Зафиксировав в Г₁ (X, U) некоторую вершину x_i Î X, получим предикат-свойство Г₁x_i (U) – «вершине x_i инцидентны ребра множества U», истинность которого задает i-я строка матрицы А₁ предиката Г₁ (X, U). Таким образом образ вершины x_i Î X относительно предиката Г₁ (X, U) – это подмножество U_i⁺ Í U инцидентных ей ребер. Оно является характеристическим множеством Г₁x_i предиката-свойства Г₁x_i (U):

            U_i⁺ = Г₁x_i = {u_j Î U : Г₁x_i (u_j) = «и»}, U_i⁺ Í U .

Множество подмножеств ребер, инцидентных вершинам x_i Î X, т. е. образ множества X относительно предиката  Г₁, будет

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

 Подставив в предикат Г₂ (U, X) ребро u_j, получим предикат-свойство Г₂u_j (X) – «ребру u_j инцидентны вершины множества X», истинность которого задает j-я строка матрицы предиката Г₂ (U, X). Образом ребра u_j Î U относительно предиката Г₂ (U, X) является подмножество X_j⁺ Í X вершин, инцидентных этому ребру:

                     X_j⁺ = Г₂u_j = {x_i Î X : Г₂u_j (x_i) = «и»},       X_j⁺ Í X .

Образ множества ребер U относительно того же предиката будет задаваться множеством характеристических подмножеств предикатов-свойств Г₂u_j (X), т. е. строк матрицы А₂:

                              Г₂U = { Г₂u_j / u_j Î U}.

Ультраграф данным способом будет задан, если заданы множества вершин X, ребер U и их образы, т. е. множества подмножеств Г₁X и Г₂U. Ультраграф при данном способе представления будем обозначать как H_U (X, U, Г₁X, Г₂U). Ультраграф, изображенный на рисунке 2, этим способом будет задан через:

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

Г₁X = {Г₁x_i / i = 1, 5},

где Г₁x₁ = {u₁,u₂}, Г₁x₂ = Г₁x₃ = Г₁x₄ = Æ, Г₁x₅ = {u₁, u₃}, 

Г₂U = {Г₂u_j / j = 1, 3},

где Г₂u₁ = {x₂, x₃}, Г₂u₂ = {x₄}, Г₂u₃ = {x₅}.   

     Рассмотренное представление ультраграфа, так же как и матричное, является полным, однако затрудняет выполнение формальных преобразований и просмотр структуры ультраграфа. Например, для того чтобы определить, каким вершинам инцидентно ребро u_j Î U, необходимо проверить принадлежность этого ребра всем Г₁x_i и сформировать подмножество вершин согласно выражению:

                                     X_j^– = { x_i Î X : u_j Î Г₁x_i }.

Аналогичное замечание справедливо и для определения множества ребер, которым инцидентна вершина x_i Î X.

Для задания таких множеств воспользуемся понятием «прообраз множества относительно предиката». По определению прообраз множества – это его образ относительно обратного предиката.

Рассмотрим определение множества ребер, которым инцидентна некоторая вершина x_i ультраграфа. Инцидентность ребрам множества U вершин множества  X задает предикат-отношение Г₂ (U, X), что наглядно иллюстрирует рисунок 3,а. Ребра, которым инцидентны вершины множества X, определяет предикат-отношение Г₂^-1 (X, U) «вершины множества X инцидентны ребрам множества U». Он является обратным к предикату Г₂ (U, X). Элементы предиката Г₂^-1 (X, U) определяются по правилу:

      " u_j Î U, "x_i Î X (Г₂ (u_j, x_i) = «и» ® Г₂^-1 (x_i, u_j) = «и»).

Для ультраграфа, изображенного на рисунке 2, геометрическая интерпретация предиката  Г₂^-1 (X, U) показана на рисунке 3,б, а матрица истинности A₂^-1 имеет вид

Зафиксировав в предикате Г₂^-1 (X, U) вершину x_i, получим предикат-свойство Г₂^-1x_i (U) – «вершина x_i инцидентна ребрам множества U», характеристическое множество которого является прообразом вершины x_i относительно предиката Г₂ (X, U), т. е. множеством ребер, которым она инцидентна. Истинность предиката-свойства Г₂^-1x_i (U) задает i-й вектор-строка матрицы предиката Г₂^-1 (X, U). Из правила определения элементов предиката Г₂^-1 (X, U) следует, что таблица истинности этого предиката получается транспонированием матрицы инцидентности A₂. Отсюда множество ребер U_i^–, которым инцидентна вершина x_i Î X – ее прообраз относительно предиката Г₂ (U, X), – это характеристическое множество i-го вектора-столбца матрицы А₂, т. е. предиката-свойства Г₂x_i (U):

              U_i^– = Г₂x_i ={u_j Î U : Г₂x_i (u_j) = «и» },     U_i^– Í U .

Прообразом множества X относительно предиката Г₂ (U, X) будет множество характеристических подмножеств предикатов-свойств Г₂x_i (U):

                             Г₂X = {Г₂x_i / x_i Î X}.

Аналогично множество вершин, которым инцидентно ребро u_j Î U – его прообраз Г₁u_j относительно предиката Г₁ (X, U) – это характеристическое множество X_j^– предиката-свойства Г₁^-1u_j (X), соответствующего j-у вектору-строке матрицы истинности  А₁^-1 предиката Г₁^-1 (U, X), или предиката-свойства Г₁u_j (X), задаваемого j-м вектором-столбцом матрицы А₁:

                      X_j^– = Г₁u_j  = {x_i Î X : Г₁u_j (x_i) = «и»},       X_j^– Í X.  

Прообразом множества U относительно предиката Г₁ (X, U) является множество характеристических подмножеств предикатов-свойств   Г₁u_j (X):

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

Для ультраграфа, изображенного на рисунке 2, геометрическая интерпретация предиката  Г₁^-1 (U, X) показана на рисунке 3,б, а матрица истинности A₁^-1 имеет вид

У ультраграфа, показанного на рисунке 2,

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

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

Для данного способа представления ультраграф будем обозначать      H_U (X, U, Г₁X, Г₂X, Г₂U, Г₁U).

Предикаты смежности F₁ (X, X) вершин и F₂ (U, U) ребер ультраграфа. Установим связь предиката смежности вершин F₁ (X, X) с предикатами инцидентности Г₁ (X, U) и Г₂ (U, X). Рассмотрим для этого пару вершин x_i, x_t Î X. Для этих вершин связь F₁ (X, X) с Г₁ (X, U) и Г₂ (U, X) определяется выражением

F₁(x_i, x_t) = «и» : $u_j Î U (Г₁(x_i, u_j) = «и» & Г₂(u_j, x_t) = «и»).       (4)

Здесь x_t – вершина, смежная вершине x_i, u_j – ребро, инцидентное вершине x_i, этому ребру инцидентна вершина x_t (смотри рисунок 4, а).

Инцидентные вершине x_i ребра задает характеристическое множество U_i⁺ = Г₁x_i предиката-свойства Г₁x_i (U). Вершины, инцидентные ребру u_j Î U_i⁺, определяет предикат-свойство Г₂u_j (X). Таким образом, подставляя в Г₂ (U, X) ребра множества U_i⁺ Í U, получаем множество предикатов-свойств {Г₂u_j (X)}, u_j Î U_i⁺ = Г₁x_i, каждый из которых задает вершины, смежные вершине x_i по ребру u_j.

Поскольку в общем случае |U_i⁺| >1 и вершина x_t Î X будет смежна вершине x_i Î X, если x_t инцидентна хотя бы одному ребру из U_i⁺ = Г₁x_i , вершины, смежные вершине x_i в ультраграфе, будут задаваться предикатом – свойством

                           F₁x_i (X) =   Ú Г₂ u_j(X).                                                (5)

                                                 u_j Î  U_i⁺

У ультраграфа, показанного на рисунке 4, а, U_i⁺ = {u_j, u_k}. Пусть X  = {x_i, x_t, x_r, x_p}, т. е. элементы множества X записаны в указанной последовательности. Тогда характеристические вектора предикатов Г₂u_j (X),  Г₂u_k (X) и    F₁x_i (X)  будут:

Г₂u_j (X) ={0, 1, 1, 0}, Г₂u_k (X) = {0, 1, 0, 1}  и

F₁x_i (X) =  Г₂u_j (X) Ú Г₂u_k (X) ={0, 1, 1, 1}.

Рисунок 4 – К определению смежности вершин ультраграфа: вершине x_i смежны вершины x_t, x_r, x_p (а); вершине x_i не смежны вершины x_t, x_r (б);

Распространяя выкладки для "x_i Î X, получим предикат-отношение смежности вершин ультраграфа

                          F₁ (X, X) = { F₁x_i  (X) / x_i Î X }.                                       (6)

        Матрица истинности этого предиката является матрицей смежности R₁ вершин ультраграфа. Элементы этой матрицы по матрицам инцидентности А₁ и А₂ определяются по правилу:

                           ì 1 – если  $ a_1i,j =1 & a_2j,t=1,

                  r_1i,t = í  

 î0 – в противном случае,             

где  i, t = 1, n;    n = | X |,    j = 1, m;  m = | U |.

Матрица смежности R₁ вершин x_i Î X  ультраграфа, изображенного на рисунке 2, будет:

Наглядно смежность вершин множества X ультраграфа H_U (X, U) может быть представлена графом смежности G (X, X). Граф смежности, соответствующий матрице R₁, показан на рисунке 5. На этом рисунке вершины ультраграфа изображены кружками, а истинность F₁ (x_i, x_t) – стрелками.

        Рисунок 5 – Граф смежности вершин ультраграфа, изображенного на рисунке 2

При выполнении некоторых преобразований ультраграфа и просмотре его структуры бывает необходимо знать, каким вершинам смежна данная. Эта связь задается предикатом F₁^-1 (X, X) обратным к предикату F₁ (X, X). Установим связь предиката F₁^-1 (X, X) с предикатами инцидентности Г₁ (X, U) и Г₂ (U, X). Рассмотрим для этого пару вершин x_i, x_t Î X. Для этих вершин связь F₁^-1 (X, X) с Г₁ (X, U) и Г₂ (U, X) определяется выражением

F₁^-1 (x_i, x_t) = «и» : $u_j Î U (Г₂ ( u_j, x_i) = «и» & Г₁ (x_t, u_j) = «и»).    (7)

Здесь x_t – вершина, которой смежна вершина x_i,  u_j – ребро, которому  инцидентна вершина x_i, это ребро инцидентно вершине x_t ( смотри рисунок 4, б).

Ребра, которым инцидентна вершина x_i, задают характеристическое множество U_i^– = Г₂x_i предиката-свойства Г₂x_i (U). Вершины, которым инцидентно ребро u_j Î U_i⁺ , определяет предикат-свойство Г₁u_j (X). Таким образом, подставляя в Г₁ (X, U) ребра множества U_i^– Í U, получаем множество предикатов-свойств {Г₁u_j (X)}, u_j Î U_i^– = Г₂x_i, каждый из которых определяет вершины, которым смежна вершина x_i по ребру u_j.

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

                           F₁^-1x_i (X) =   Ú Г₁u_j (X).                                            (8)

                                            u_j Î U_i^–

У ультраграфа, показанного на рисунке 4, б, U_i^– = {u_j}. Пусть X = {x_i, x_t, x_r}, т. е. элементы множества X записаны в указанной последовательности. Тогда характеристические вектора предикатов  Г₁u_j (X) и F₁^-1x_i (X)  будут:

Г₁u_j (X) = {0, 1, 0}  и   F₁^-1x_i (X) = Г₁u_j(X) = { 0, 1, 0}.

Распространяя выкладки для "x_i Î X, получим обратный предикат-отношение смежности вершин ультраграфа

                          F₁^-1 (X, X) = { F₁^-1x_i (X) / x_i Î X }.                                  (9)

Матрицу истинности этого предиката обозначим через R₁^-1.  Элемент этой матрицы r₁^-1_i,j = 1  означает, что вершина  x_i  смежна вершине x_j  (r_1i,j = 1 в матрице R₁ означает, что вершине  x_i  смежна вершина x_j ).

По определению обратного предиката F₁^‑1(X,X) область его истинности при заданном предикате F₁(X, X) задается  правилом

       "x_i , x_j Î X  (F₁ (x_i, x_j) = «и» ® F₁^-1(x_j, x_i) = «и»).               (10)

Таким образом, матрица смежности R₁^-1 ультраграфа (матрица истинности предиката F₁^-1) получается транспонированием матрицы R₁. Матрица   R₁^-1 ультраграфа, показанного на рисунке 2, будет:

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

F₂ (u_j, u_k) = «и»: $ x_i Î X ( Г₂(u_j, x_i) = «и» & Г₁(x_i, u_k) = «и»).         (11)

Здесь u_k – ребро, смежное ребру u_j., а x_i – вершина, инцидентная ребру u_j, этой вершине инцидентно ребро u_k (смотри рисунок 6, а).

Вершины, инцидентные ребру u_j Î U, задает характеристическое множество X_j⁺ = Г₂u_j  предиката-свойства Г₂u_j (X). Ребра, инцидентные вершине x_i Î X, определяет предикат-свойство Г₁x_i (U). Подставляя в Г₁(X,U) вершины множества X_j⁺ Í X , получаем множество предикатов-свойств {Г₁x_i (U)}, x_i Î X_j⁺, каждый из которых задает ребра, смежные ребру u_j по вершине x_i.

Так как в общем случае | X_j⁺ | > 1 и ребро u_k будет смежно ребру u_j, если u_k инцидентно хотя бы одной вершине из  X_j⁺, то ребра, смежные ребру u_j Î U в ультраграфе, будут задаваться предикатом

              F₂u_j(U) =    Ú   Г₁x_i (U) .   (12)

                                   x_i Î X_j⁺

У ультраграфа, показанного на рисунке 6, а, X_j⁺ = Г₂u_j = {x_i, x_r, x_p}.

Рисунок 6 – К определению смежности ребер ультраграфа: ребру u_j смежны ребра u_k, u_d, u_t (а); ребро u_j смежно ребру u_k, ребра u_k  и u_d не смежны (б)

Пусть U = {u_j, u_k, u_d, u_t}. Тогда характеристические вектора предикатов-свойств Г₁x_i (U), Г₁x_r (U), Г₁x_p (U) и F₂u_j (U) будут:

Г₁x_i (U) = {0, 1, 0, 1},

Г₁x_r (U) = {0, 0, 0, 1},

Г₁x_p (U) = {0, 0, 1, 0} и

F₂u_j (U) = Г₁x_i (U) Ú Г₁x_r (U) Ú Г₁x_p (U) = {0, 1, 1, 1}.

       Для " x_i Î X получим предикат-отношение смежности ребер ультраграфа

                         F₂ (U, U) = { F₂u_j (U) / u_j Î U } .   

Элементы матрицы смежности  R₂ ребер ультраграфа определяются по правилу:

                    ì   1 – если $ a_2j,i =1 & a_1i,k =1,

                  r_2j,k = í  

 î   0 – в противном случае,

где j, k = 1, m; m = | U |, i = 1, n; n = | X |, a_2j,i и a_1i,_k – элементы матриц инцидентности А₂ и А₁ соответственно. Матрицы инцидентности  А₁, А₂  и смежности  R₂ ребер ультраграфа, изображенного на рисунке 7, будут:

Рисунок 7 – К определению матрицы смежности ребер ультраграфа

Граф смежности G (U, U) ребер ультраграфа, соответствующий матрице R₂, показан на рисунке 8. Здесь ребра ультраграфа изображены кружками, а истинность  F₂ (u_j, u_k) – стрелками.

Рисунок 8 – Граф смежности ребер ультраграфа, показанного на рисунке 7

Для всех u_j Î U ребра, которым они смежны, задаются  предикатом F₂^-1 (U, U), обратным предикату F₂ (U, U). Значения предиката F₂^-1 (U, U) по значениям предикатов Г₂ (U, X) и Г₁ (X, U) определяются по выражению:

F₂^-1 (u_j, u_k) = «и»: $ x_i Î X ( Г₁( x_i, u_j,) = «и» & Г₂( u_k , x_i) = «и»).   (13)

Здесь u_k – ребро, которому смежно ребро u_j,  x_i – вершина, которой инцидентно ребро u_j, эта вершина инцидентна ребру u_k (смотри рисунок  6,б).

Вершины, которым инцидентно ребро u_jÎU, задает характеристическое множество X_j^– = Г₁u_j  предиката-свойства  Г₁u_j (X). Ребра, которым инцидентна вершина x_i Î  X, определяет предикат-свойство Г₂x_i  (U). Подставляя в Г₂ (X, U) вершины множества  X_j^– Í X , получаем множество предикатов-свойств {Г₂x_i  (U)},  x_i Î X_j^– , каждый из которых задает ребра, которым смежно ребро u_j по вершине x_i.

Ребра, которым смежно ребро u_j Î U в ультраграфе, будут задаваться предикатом

              F₂^-1u_j  (U) =    Ú   Г₂x_i (U) .                                             (14)

                                       x_i Î X_j^–

У ультраграфа, показанного на рисунке 6, б,   X_j^– = Г₁u_j = {x_i}. Пусть U = {u_k, u_j}. тогда характеристические вектора предикатов-свойств Г₂x_i (U) и F₂^-1u_j (U) будут:

                         Г₂x_i (U) = {1, 0}  и  F₂^-1u_j (U) = {1, 0}.

Для "x_iÎX получим обратный предикат-отношение смежности ребер ультраграфа

                         F₂^-1 (U, U) = { F₂^-1u_j (U) / u_j Î U} . 

Матрицу истинности этого предиката обозначим как R₂^-1. Элемент этой матрицы r₂^-1_i,j =1  означает, что ребро  u_i  смежно ребру u_j ультраграфа.

Предикат F₂^-1 (U, U),  как обратный предикату F₂ (U, U), получается по правилу: 

         " u_j, u_k Î U (F₂ (u_j, u_k) = «и» ® F₂^-1 (u_k, u_j) = «и»).            (15)

Отсюда матрица истинности R₂^-1 предиката F₂^-1 (U, U) является транспонированной матрицей R₂. Для ультраграфа, показанного на рисунке 7, эта матрица будет:

Образы и прообразы множеств X и U относительно предикатов смежности вершин F₁ (X, X) и ребер F₂ (U, U) соответственно. Для каждой вершины x_i Î X  ультраграфа H_U (X, U) ее образ F₁x_i относительно предиката смежности F₁ (X, X) – множество смежных ей вершин X_i⁺, определяется характеристическим множеством предиката-свойства F₁x_i (X)

                    X_i⁺ = F₁x_i = {x_k Î X: F₁x_i  (x_k) = «и»}.

Истинность предиката-свойства F₁x_i (X) задается i-м вектором-строкой матрицы R₁.

Множество вершин X_i^–, которым смежна вершина x_i , т. е. ее прообраз F₁^-1x_i относительно предиката F₁ (X, X), является характеристическим множеством предиката-свойства   F₁^-1x_i ( X) :

         X_i^–  = F₁^-1x_i = { x_k Î X: F₁^-1x_i (x_k) = «и» }.

Истинность предиката-свойства F₁^-1x_i (X) задается i-м вектором-строкой матрицы R₁^-1 или соответствующим вектором-столбцом матрицы  R₁.

По аналитическому представлению ультраграфа в виде H_U (X, U, Г₁X, Г₂X, Г₁U, Г₂U) для каждой вершины x_iÎX ее образ F₁x_i определяется на основании (5) по правилу

                           F₁x_i =   È Г₂u_j ,                                                 (16)

                                          u_jÎГ₁x_i

а прообраз F₁^-1x_i в соответствии с (8) по выражению

                          F₁^-1x_i =   È Г₁u_j .                                                 (17)

                                            u_jÎГ₂x_i

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

                                 F₁X = {F₁x_i  / x_i Î X}

и                              F₁^-1X = {F₁^-1x_i / x_i Î X}.

Для ультраграфа, изображенного на рисунке 2, множества образов F₁X и прообразов  F₁^-1X его вершин относительно предиката смежности F₁ будут:

F₁X = {F₁x_i / i = 1,5}:                     F₁^-1X = {F₁^-1x_i / i = 1,5}:

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

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

F₁x₅ = {x₂, x₃, x₅},                           F₁^-1x₃ = {x₁, x₅},

Образ F₂u_j ребра u_j Î U ультраграфа H_U (X, U) относительно предиката F₂ (U, U), т. е. множество U_j⁺ смежных ему ребер, определяется характеристическим множеством предиката-свойства F₂u_j (U):

                   U_j⁺ = F₂u_j = {u_kÎU: F₂u_j (u_k) = «и»}.

Истинность предиката F₂u_j (U) задается j-м вектором-строкой матрицы R₂.

Прообраз F₂^-1u_j ребра u_jÎU относительно предиката F₂ (U, U), т. е. множество ребер U_j^–, которому это ребро смежно, является характеристическим множеством предиката-свойства F₂^-1u_j (U):

                  U_j^– = F₂^-1u_j = {u_kÎU: F₂^-1u_j (u_k) = «и»}.

Истинность предиката F₂^-1u_j (U) задается j-м вектором-строкой матрицы R₂^‑1 или соответствующим вектором-столбцом матрицы R₂.

По аналитическому представлению ультраграфа для каждого ребра  u_jÎU его образ F₂u_j определяется на основании (12) по правилу

                           F₂u_j =   È Г₁x_i ,                              (18)

                                           x_i Î Г₂u_j

а прообраз F₂^-1u_j в соответствии с (14) по выражению

                          F₂^-1u_j =   È Г₂x_i .                             (19)

                                            x_i Î Г₁u_j

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

                                 F₂U = {F₂u_j / u_j Î U}

и                              F₂^-1U = {F₂^-1u_j / u_j Î U}.

Для ультраграфа, изображенного на рисунке 7, множества образов F₂U и прообразов F₂^-1U его ребер относительно предиката смежности F₂ будет:

F₂U = {F₂u_j / j = 1,3}:                          F₂^-1U = {F₂^-1u_j / j = 1,3}:

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

F₂u₂ = { u₁, u₃},                                       F₂^-1u₂ = {u₁},

F₂u₃ = {u₃},                                              F₂^-1u₃ = {u₂, u₃}.

Отметим в заключение, что совокупность матриц смежности, а также образов и прообразов множеств вершин X и ребер U ультраграфа  H_U (X, U) относительно предикатов смежности вершин F₁ (X, X) и ребер F₂ (U, U) задает ультраграф не полностью.

 Если в ходе анализа и преобразования ультраграфа необходимо знать связи вершин и ребер, определяемые как предикатами инцидентности, так и предикатами смежности, ультраграф может быть задан в форме H_U (X, U, Г₁X, Г₂X, Г₂U, Г₁U, F₁X, F₁^-1X, F₂U, F₂^-1U) либо необходимым подмножеством образов и прообразов вершин и ребер относительно предикатов инцидентности и смежности с указанием в скобках используемого набора образов и/или прообразов. Аналогично будем поступать и в отношении гиперграфа, обыкновенного ориентированного и неориентированного графов, которые будут рассмотрены ниже.

Характеристики вершин и ребер ультраграфа. К характеристикам вершин ультраграфа относятся:

·         r⁺(x_i) – полустепень исхода, т. е. количество ребер, инцидентных вершине x_i Î X.  По матрице  инцидентности A₁ показатель рассчитывается по формуле:

                                                m

                                  r⁺(x_i) = S a_1i,j.

                                               j=1

Для ультраграфа, изображенного на рисунке 2, r⁺(x₁) =2.                                

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

                                          r⁺(x_i) = | Г₁x_i |.

Для ультраграфа, показанного на рисунке 9, U_i⁺ = Г₁x_i = {u₁} и r⁺(x_i) = 1;

·         r^- (x_i) – полустепень захода, т. е. количество ребер, которым инцидентна вершина x_i Î X.  По матрице  инцидентности A₂ показатель рассчитывается по формуле:

                                               m

                                 r^- (x_i) = S a_2j,i.

                                              j=1

Для ультраграфа, изображенного на рисунке 2, r^-(x₁) = 0.

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

                                            r^- (x_i) = | Г₂x_i |.

Для ультраграфа (смотри рисунок 9) U_i^– = Г₂x_i = {u₂, u₃} и  r^-(x_i) = 2;

·         A(x_i) ={a_k (x_i) / k = 1, |U_i⁺ |} – вектор, элемент которого a_k (x_i) равен количеству вершин, инцидентных ребру u_j Î U_i⁺ = Г₁x_i:

                      a_k (x_i) = | Г₂u_j |.

Рисунок 9 – К определению характеристик вершин ультраграфа

Для ультраграфа, показанного на рисунке 9, образ вершины x_i  будет                                              

Г₁x_i = {u₁}, а прообраз ребра u₁ – Г₂u₁ = { x_k, x_r }. Отсюда A(x_i) ={2};

·        B(x_i) = {b_k (x_i) / k=1, |U_i⁺|} – вектор, каждый его элемент b_k (x_i) равен количеству вершин, которым инцидентно ребро u_j Î U_i⁺ = Г₁x_i:

                          b_k (x_i) = | Г₁u_j | -1.

Для ребра u₁Î Г₁x_i (смотри рисунок 9) его прообраз Г₁u₁ = {x_i, x_t} тогда   B(x_i) = {1};

·        C(x_i) ={c_k (x_i) / k = 1, |U_i^–|} – вектор, элемент которого c_k (x_i) равен количеству вершин, инцидентных ребру u_f Î U_i^– = Г₂x_i:

                            c_k (x_i) = | Г₂u_f  | -1.

Для вершины x_i (смотри рисунок 9)   Г₂x_i = {u₂, u₃}. Для этих ребер их образы Г₂u₂ = {x_i, x_q}, Г₂u₃ = {x_i, x_с}. Отсюда C(x_i) = {1, 1};

·        D(x_i) = {d_k (x_i) / k = 1, |U_i^–|} – вектор, каждый его элемент d_k (x_i) равен количеству вершин, инцидентных ребру u_f Î U_i^–= Г₂x_i:

                            d_k (x_i) = | Г₁u_f | .

Для ребер u₂, u₃ Î Г₂x_i того же ультраграфа их прообразы Г₁u₂ = {x_l} и Г₁u₃ = {x_p}. Тогда D(x_i) = {1, 1};

·     s⁺(x_i) – количество вершин, смежных вершине x_i Î X. По матрице смежности R₁ этот показатель рассчитывается по формуле:

                                               m

                                  s⁺(x_i) = S r_1i,j.                                                                                                                                                    

                                              j=1

Для вершины x₁ ультраграфа, показанного на рисунке 2, s⁺( x₁) = 3.

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

                                          s⁺(x_i) = | F₁x_i |.

Для вершины  x_i  ультраграфа, изображенного на рисунке 9, Г₁x_i = {u₁},  F₁x_i  = Г₂u₁ = { x_k, x_r },  s⁺(x_i) = 2;

·     s^-(x_i)– количество вершин, которым смежна вершина x_i Î X. При матричном представлении ультраграфа показатель рассчитывается как                

                               m                                                  m

                  s^-(x_i) = S r₁^-1_i,j      или     s^-(x_i) = S r_1j,i                                                                                                                                         

          j=1                                                   j=1                         

по матрицам смежности R₁^-1 и  R₁  соответственно. Для вершины x₂ ультраграфа, изображенного на рисунке 2, s^- (x₂) = 2.

По прообразу вершины относительно предиката смежности F₁ (X, X)  показатель определяется по выражению

                                               s^- (x_i) = | F₁^-1x_i | .                                                                                                                          

Для вершины x_i ультраграфа, изображенного на рисунке 9, Г₂x_i = {u₂, u₃},  Г₁u₂ È Г₁u₃ = F₁^-1x_i = {x_l, x_p },  s^-(x_i) = 2;

·        e(x_i) = |{u_j Î U : Г₁u_j = Г₂u_j = x_i}| – количество петель вершины x_i.

Характеристики ребер ультраграфа:

·        r⁺(u_j)– количество вершин множества X_j⁺ = Г₂u_j, инцидентных ребру u_j. По матрице инцидентности А₂ этот показатель рассчитывается по формуле:

                                              n

                                 r⁺(u_j) = S a_2j,i .

                                             i=1

Для ультраграфа, изображенного на рисунке 2, r⁺(u₁) = 2.

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

                                          r⁺(u_j) = | Г₂ u_j |.

Для ребра u₁ ультраграфа (смотри рисунок 10) Г₂u₁={x_i, x_k, x_r} и             r⁺(u₁) = 3;

·         r^-(u_j) = | Г₁u_j | – количество вершин множества X_j^– = Г₁u_j, которым  инцидентно ребро u_j. По матрице  инцидентности A₁ показатель рассчитывается по формуле:

                                              n

                                  r^-(u_j) = S a_1i,j.

                                             i=1

Для ультраграфа, изображенного на рисунке 2, r^-(u₁) = 2.                                

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

                                        r^-(u_j) = | Г₁u_j |.

Для ребра u₁  ультраграфа, показанного на рисунке 10, Г₁u₁ = {x_t},           r^- (u₁) = 1;

·        A(u_j) = {a_k (u_j) / k = 1, | X_j⁺ |} – вектор, элемент которого a_k(u_j) равен количеству ребер, инцидентных вершине x_i Î X_j⁺  = Г₂u_j :

                      a_k (u_j) = | Г₁x_i |.

Рисунок 10 – К определению характеристик ребер ультраграфа

Для ребра u₁ ультраграфа, показанного на рисунке 10, Г₂u₁ ={ x_i, x_k, x_r }, и для вершин  x_i, x_k, x_r  их  образы равны Г₁x_i ={u₂, u₃}, Г₁x_k = Æ, Г₁x_r = Æ. Тогда  A(u₁) = {2, 0, 0};

·        B(u_j) = {b_k (u_j) / k =1, | X_j⁺ |} – вектор, каждый его элемент b_k (u_j) равен количеству ребер, которым инцидентна вершина x_i Î X_j⁺ = Г₂u_j:

                          b_k (u_j) = | Г₂x_i | -1.

Для всех вершин x_i, x_k, x_r Î Г₂u₁ (смотри рисунок 10) прообразы Г₂x_i = Г₂x_k = Г₂x_r = {u₁} и B(u₁) = {0, 0, 0};

·        C(u_j ) ={c_k (u_j) / k = 1, | X_j^– |} – вектор, элемент которого c_k (u_j) равен количеству ребер, инцидентных вершине x_iÎ X_j^– = Г₁u_j:

                            c_k (u_j) = | Г₁x_i  | -1.

Для ребра u₁ (смотри рисунок 10) Г₁u₁ ={x_t} и для вершины x_t ее образ Г₁x_t  = {u₁, u₄ }  и  C(u₁) ={1};

·          D(u_j) = { d_k(u_j) / k =1, | X_j^– |} – вектор, каждый его элемент d_k(u_j) равен количеству ребер, которым инцидентна вершина x_i Î X_j^– = Г₁u_j :

                            d_k (u_j) = | Г₂x_i | .

Для вершины x_t Î Г₁u₁   ее прообраз Г₂ x_t = Æ и  D(u_j) = {0};

·     s⁺(u_j) – количество ребер, смежных ребру u_j Î U. По матрице смежности R₂ этот показатель рассчитывается по формуле:

                                               m

                                  s⁺(u_j) = S r_2j,i.                                                                                                                                                    

                                              i=1

Для ребра u₂ ультраграфа, показанного на рисунке 7, s⁺(u₂) = 2.

При известных образах ребер относительно предиката смежности  F₂ (U, U):

                                          s⁺(u_j) = | F₂u_j |.

Для ребра u₁  ультраграфа, изображенного на рисунке 10, его образ Г₂u₁={x_i, x_k, x_r }, образы этих вершин Г₁x_i = {u₂, u₃}, Г₁x_k = Г₁x_r = Æ.  Множество ребер, смежных ребру u₁, F₂u₁ = Г₁x_i Ú Г₁x_k Ú Г₁x_r  и               F₂ u₁={u₂,u₃}. Тогда   r⁺(u₁) = 2;

·       s^-(u_j)  – количество ребер, которым смежно ребро u_jÎU. При известных матрицах смежности R₂ или R₂^-1 этот показатель рассчитывается по формуле:

                               m                                  m

                  s^-(u_j) = S r_2i,j     или    s^-(u_j) = S r₂^-1_j,i  .                                                                                                                                              

                              i=1                                 i=1

Для ребра u₃ ультраграфа, показанного на рисунке 7, s^-( u₃) = 2.

При известных  прообразах ребер, т. е. их образах относительно предиката смежности F₂^-1 (U, U), показатель определяется по выражению:

                                       s^-(u_j) = | F₂^-1u_j |.

Для ребра u₁ (смотри рисунок 10)  его прообраз Г₁u₁ = {x_t}. Прообраз этой вершины  Г₂x_t = Æ, отсюда   F₂^-1u₁ = Æ и s^-(u₁) = 0.

Гиперграфы. Данный вид графа получим в соответствии со сформулированным выше определением при выполнении условия (1) в том случае, когда

           "x_i, x_k Î X, u_j Î U (Г₁(x_i,u_j) = «и»®Г₂(u_j,x_i) = «и» &

                       Г₂ (u_j,x_k) = «и» ® Г₁(x_k,u_j)  = «и»)                        (20)

и                         $ u_j Î U |Г₂u_j | > 2                                                  (21) 

или                     $ u_j Î U |Г₂u_j | = 1.                                                 (22)  

Условие (20) означает, что предикат-отношение Г₂ (U, X) является обратным к предикату-отношению Г₁ (X, U). Тогда гиперграф можно определить как два непересекающихся множества вершин X и ребер U, на элементах которых задана пара двуместных предикатов-отношений  инцидентности Г₁ (X, U) и Г₂ (U, X) таких, что Г₂ (U, X) =  Г₁^-1 (X, U).

Вектор-строка таблицы истинности двуместного предиката-отношения Г₁ (X, U) – матрицы инцидентности вершины-ребра A₁ совпадает с вектором-столбцом  таблицы истинности предиката  Г₂ (U, X) – матрицы инцидентности ребра-вершины A₂. По определению предикаты эквивалентны, если их таблицы истинности совпадают. Отсюда следует, что:

·     предикат-свойство Г₁x_i (U) – «вершине x_i инцидентны ребра множества U» эквивалентен предикату-свойству Г₂x_i (U) –«вершина x_i инцидентна ребрам множества U»,

·     предикат-свойство Г₂u_j (X) – «ребру u_j инцидентны вершины множества X» эквивалентен предикату-свойству Г₁u_j (X) – «ребро u_j инцидентно вершинам множества X».

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

С учетом сказанного в гиперграфе:

– вершины x_i и x_k смежны, если существует ребро u_j, такое, что вершина x_i и ребро u_j, ребро u_j и вершина x_k инцидентны;

– ребра u_j и u_k смежны, если существует вершина x_i, такая, что ребро u_j и вершина x_i, вершина x_i и ребро u_k инцидентны.

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

 При геометрическом представлении гиперграфа вершины изображаются кружками, ребра – в виде контуров, а расположение вершины x_i внутри ребра u_j означает истинность  Г₁ (x_i,u_j), следовательно и  Г₂ (u_j,x_i). На рисунке 11,а приведено такое изображение гиперграфа, а на рисунке 11,б – его представление в виде двудольного графа (сравните с рисунками 2 и 3 соответственно).

Рисунок 11 – Гиперграф (а) и его представление в виде двудольного графа (б)

Представление гиперграфа матрицами инцидентности. Поскольку матрица истинности предиката Г₂ (U, X) является транспонированной матрицей предиката Г₁ (X, U), гиперграф при матричном представлении будет полностью задан, если определены элементы одной из них. В качестве матрицы инцидентности A_H гиперграфа будем использовать матрицу истинности предиката Г₁ (X, U), размером n´m, где n = |X|, а m = |U|. Элементы этой матрицы задают связь между вершинами и ребрами гиперграфа и определяются по правилу

                              ì 1 – если Г₁ (x_i,u_j) = «и»

                   a _i,j  = í                                              ,

                                î 0 – если Г₁(x_i,u_j) = «л»,

где i = 1, n,   j = 1, m .

Матрица инцидентности гиперграфа, изображенного на рисунке 11, имеет вид

 

Представление гиперграфа образами вершин и ребер относительно предикатов Г₁ (X, U) и Г₂ (U, X). В гиперграфе образ Г₁x_i вершины x_i Î X относительно предиката   Г₁ (X, U) – это подмножество U_i ÍU инцидентных ей ребер. Он является характеристическим множеством предиката-свойства Г₁x_i (U), т. е. вектора-строки матрицы А_H. Множество подмножеств ребер, инцидентных вершинам x_iÎX, т. е. образ множества X относительно предиката Г₁(X,U), будет

Г₁X = {Г₁x_i /x_i Î X}, где Г₁x_i = U_i Í U, Г₁x_i = {u_j Î: Г₁x_i(u_j) = «и»}. (23)

Образом Г₂u_j ребра u_j Î U относительно предиката Г₂ (U, X) является подмножество X_j Í X вершин, инцидентных этому ребру. Образ множества ребер U относительно того же предиката будет задаваться множеством характеристических подмножеств предикатов-свойств Г₂u_j (X),  т. е. столбцов матрицы А_H :

Г₂U = {Г₂u_j /u_jÎU}, где Г₂u_j = X_j Í X, Г₂u_j ={ x_i ÎX: Г₂u_j(x_i) = «и»}. (24)

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

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

Г₁X ={Г₁x_i /i=1,5},        

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

Г₂U={ Г₂u_j / j=1,3}, 

где  Г₂u₁ = { x₁, x₂, x₃, x₅}, Г₂u₂ = { x₁, x₄}, Г₂u₃ = {x₅}.

Рассмотренное представление гиперграфа, так же как и матричное, является полным. 

Предикаты смежности F₁ (X, X) вершин и F₂ (U, U) ребер гиперграфа. Установим связь предиката смежности вершин F₁ (X, X) с предикатами инцидентности Г₁ (X, U) и Г₂ (U, X). Рассмотрим для этого пару вершин x_i, x_k Î X. Для этих вершин связь F₁ (X, X) с Г₁ (X, U) и Г₂ (U, X) определяется выражением

      F₁(x_i, x_k) = «и» : $u_j Î U (Г₁(x_i, u_j) = «и» & Г₂(u_j, x_k) = «и»).   (25)

Инцидентные вершине x_i ребра задает характеристическое множество U_i =Г₁x_i предиката-свойства  Г₁x_i (U). Вершины, инцидентные ребру u_jÎU_i , определяет предикат-свойство Г₂u_j (X). Таким образом, подставляя в Г₂ (U, X) ребра множества U_i Í U, получаем множество предикатов-свойств {Г₂u_j (X)}, u_j Î U_i = Г₁x_i, каждый из которых задает вершины, смежные вершине x_i по ребру u_j.

Поскольку вершина x_k Î X будет смежна вершине x_i Î X, если она инцидентна хотя бы одному ребру из U_i = Г₁x_i , вершины, смежные вершине x_i, будут задаваться предикатом – свойством

                           F₁x_i (X) =   Ú Г₂u_j (X),        (26)

                                          u_jÎU_i

где Г₂u_j (x_i) = «л», если |Г₂u_j| > 1.

 Это вытекает из того, что в гиперграфе Г₁(x_i, u_j) = «и» ®Г₂(u_j, x_i) = «и», поэтому при определении предиката смежности  F₁x_i (X) по этой формуле без учета условия |Г₂u_j| > 1 каждая вершина будет смежна самой себе, даже если у нее нет петли (смотри рисунок 11 и матрицу A_H). Следовательно, в формуле (24) значение одноместного предиката-свойства    Г₂u_j (X) при x = x_i , т. е.  Г₂u_j  (x_i), должно принимать значение «ложь», если |Г₂u_j| > 1 (u_j не является петлей).

У гиперграфа, показанного на рисунке 11, U₁ = Г₁x₁ = {u₁, u₂} и характеристические вектора предикатов Г₂u₁ (X), Г₂u₂ (X) равны:

Г₂u₁ (X) ={1, 1, 1, 0, 1}, Г₂u₂ (X) = {1, 0, 0, 1, 0}. После присваивания Г₂u₁(x₁) и Г₂u₂(x₁) значения «0» получаем

F₁x₁ (X) =  Г₂u₁(X) Ú Г₂u₂(X) ={0, 1, 1, 1, 1},т. е. вершина x₁ смежна вершинам x₂, x₃, x₄, x₅.

Распространяя выкладки для "x_i Î X, получим предикат-отношение смежности вершин гиперграфа

                          F₁ (X, X) = {F₁x_i  (X) / x_i Î X }.                                 (27)

        Матрица истинности этого предиката является матрицей смежности R₁  вершин гиперграфа. Элементы этой матрицы по матрице инцидентности А_H  определяются по правилу:

                              ì 1 – если i ¹ k & $ a_{i, j} = 1 & a_{k, j} = 1,

                   r_1i,k  = í 1 – если i = k & $ a_{i, j} = 1 & f = 1,

    î 0 – в противном случае,       

где  i, k =1, n;    n = | X |,    j =1, m;  m = | U |,  a_{i, j} , a_{k, j}  и a_{t, j} – элементы матрицы инцидентности А_H гиперграфа, а

                                                                       n

                                                      f  = S a_t,j.  

                                                            t=1

Матрица смежности R₁ вершин  x_i Î X  гиперграфа, изображенного на рисунке 11, будет:

   В соответствии со свойством (20) матрица R₁ симметрична относительно главной диагонали. Граф смежности вершин гиперграфа, изображенного на рисунке 11, показан на рисунке 12.

Рисунок 12 – Граф смежности вершин гиперграфа, изображенного на рисунке 11

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

F₂(u_j, u_k) = «и»: $x_iÎX ( Г₂(u_j, x_i)= «и» & Г₁(x_i, u_k)= «и»).    (28)

Вершины, инцидентные ребру u_jÎU, задает характеристическое множество X_j = Г₂u_j  предиката-свойства  Г₂u_j (X). Ребра, инцидентные вершине x_iÎX, определяет предикат-свойство Г₁x_i (U). Подставляя в      Г₁ (X, U) вершины множества  X_j Í X , получаем множество предикатов-свойств {Г₁x_i (U)},  x_iÎX_j , каждый из которых задает ребра, смежные ребру u_j по вершине x_i.

Ребра, смежные ребру u_j Î U в гиперграфе, будут задаваться предикатом

                   F₂u_j(U) =    Ú   Г₁x_i (U) ,         (29)

                                   x_iÎX_j

где Г₁x_i (u_j) = «л», если |Г₂u_j| >1, так как в гиперграфе на основании (20) Г₂ (u_j, x_i) = «и»® Г₁ (x_i, u_j) = «и», поэтому, не присваивая Г₁x_i (U) значения «ложно» при u = u_j и выполнении указанного условия, получили бы, что каждое ребро, если оно и не является петлей, смежно самому себе.

 У гиперграфа, показанного на рисунке 11,  Г₂u₁ = {x₁, x₂, x₃, x₅} и характеристические вектора предикатов Г₁x₁ (U), Г₁x₂ (U), Г₁x₃ (U), Г₁x₅ (U) имеют значения:

Г₁x₁ (U) = {1, 1, 0}, Г₁x₂ (U) = {1, 0, 0}, 

Г₁x₃ (U) = {1, 0, 0},  Г₁x₅ (U) = {0, 0, 1}.

После присваивания Г₁x₁ ( u₁), Г₁x₂ ( u₁), Г₁x₃ ( u₁) и Г₁x₅ ( u₁) значения «0» получаем

F₂u₁ (U) = {0, 1, 0} Ú {0, 0, 0} Ú {0, 0, 0} Ú {0, 0, 1} = {0, 1, 1}, т. е. ребро u₁ смежно  ребрам u₂ и u₃.

Для " u_j Î U получим предикат-отношение смежности ребер гиперграфа

                         F₂ (U, U) = {F₂u_j (U) / u_jÎU} .  (30)

Элементы матрицы смежности  R₂ ребер гиперграфа определяются по правилу:

                             ì   1 – если j ¹ k & $ a_i,_j = 1 & a_i,_k = 1,

                  r_2j,_k = í   1– если j = k & $ a_i,_j = 1 & f = 1,

   î   0 – в противном случае,

где  j,k = 1, m; m = | U |,  i = 1, n; n = | X |,  a_i,_j, a_i,_k  и  a_t,_j – элементы матри-

                                                                       n

цы инцидентности А_H гиперграфа, а  f = S a_{t, j}.

                                                                    t =1

Матрица смежности R₂  ребер  u_j Î U  гиперграфа, изображенного на рисунке 11, будет:

Матрица  R₂, так же как и R₁, симметрична относительно главной диагонали. Граф смежности ребер этого же гиперграфа представлен на рисунке 13.

Рисунок 13 – Граф смежности ребер гиперграфа, изображенного на рисунке 11

Здесь ребра гиперграфа изображены кружками, а истинность  F₂(u_j, u_r) –  линиями, их соединяющими.

Образы множеств X и U относительно предикатов смежности вершин F₁ (X, X) и ребер F₂ (U, U) соответственно. Для каждой вершины x_iÎX  гиперграфа H (X, U) ее образ F₁x_i относительно предиката смежности F₁ (X, X) (множество смежных ей вершин X_i) определяется характеристическим множеством предиката-свойства F₁x_i  ( X)

                   X_i = F₁x_i = {x_k Î X : F₁x_i (x_k) = «и»}.

Истинность предиката-свойства F₁x_i (X) задается i-м вектором-строкой матрицы R₁.

По аналитическому представлению гиперграфа в форме H (X, U, Г₁X,  Г₂U) для каждой вершины x_i Î X ее образ F₁x_i на основании (26) определяется  по правилу

                      F₁x_i  = È{ Г₂u_j \ x_i : | Г₂u_j | > 1 Ú Г₂u_j : | Г₂u_j | = 1}.            (31)

                                  u_j Î Г₁x_i

Для гиперграфа, изображенного на рисунке 11, множество образов     F₁X = { F₁x_i / x_i Î X } его вершин относительно предиката смежности    F₁ (X, X) будет:

F₁X = {F₁x_i / i =1,5}:  F₁x₁ = {x₂, x₃, x₄, x₅},  F₁x₂ = {x₁, x₃, x₅}, F₁x₃ = {x₁, x₂, x₅}, F₁x₄ = { x₁},  F₁x₅ = {x₁, x₂, x₃, x₅}.                        

Образ F₂u_j ребра u_jÎU гиперграфа H (X, U) относительно предиката F₂ (U, U), т. е. множество U_j смежных ему ребер, определяется характеристическим множеством предиката-свойства F₂u_j (U):

                         U_j =  F₂u_j = { u_k Î U: F₂u_j (u_k) = «и» }.

Истинность предиката F₂u_j (U) задается j-м вектором-строкой матрицы R₂.

По аналитическому представлению гиперграфа образ каждого ребра F₂u_j определяется на основании (29) по выражению

     F₂u_j = È{Г₁x_i \ u_j : | Г₂u_j | >1 Ú Г₁x_i:| Г₂u_j | =1}.              (32)

               x_i Î Г₂u_j

 Для гиперграфа, изображенного на рисунке 11, множество образов F₂U = {F₂u_j / u_j Î U} его ребер относительно предиката смежности F₂ (U, U) будет:

F₂U = {F₂u_j / j = 1, 3}:  F₂u₁ = {u₂, u₃},  F₂u₂ = {u₁},   F₂u₃ = {u₁, u₃}.

Так же как для ультраграфа, совокупность матриц смежности, а также образов множеств вершин X и ребер U гиперграфа  H (X, U) относительно предикатов смежности вершин F₁ (X, X) и ребер F₂ (U, U) задает гиперграф не полностью.

Если в ходе анализа и преобразования гиперграфа необходимо знать связи вершин и ребер, определяемые как предикатами инцидентности, так и предикатами смежности, гиперграф может быть задан в форме  H (X, U, Г₁X, Г₁U, F₁X, F₂U) либо необходимым сочетанием образов вершин и ребер относительно предикатов инцидентности и смежности.

Характеристики вершин и ребер гиперграфа. К характеристикам вершин гиперграфа относятся:

·         r(x_i) – локальная степень вершины (количество ребер множества U_i = Г₁x_i, инцидентных вершине x_i Î X). По матрице    инцидентности A_H этот показатель рассчитывается как: 

                                                 m

                                     r(x_i) = S a_i,j.

                                                                  j=1

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

                                            r(x_i) = | Г₁x_i |.

 Для гиперграфа, изображенного на рисунке 11, r(x₁) = 2 ( Г₁x₁ ={u₁, u₂});

·        s(x_i) – количество вершин, смежных вершине x_i Î X. По матрице смежности R₁ характеристика рассчитывается по выражению:

                                               m

                                   s(x_i) = S r_1i,j.

                                                                j=1

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

                                           s(x_i) = | F₁x_i |.

 Для гиперграфа, изображенного на рисунке 11, s(x₂) = 3 (F₁x₂ ={x₁, x₃, x₅});

·          e(x_i) – количество петель при вершине гиперграфа. По матрице инцидентности A_H характеристика определяется как количество столбцов, для которых

                                                    n

                               S a_i,j = 1.

                                              i=1

При аналитическом представлении гиперграфа показатель равен:

                               e(x_i) = |{u_j Î Г₂x_i : | Г₂u_j | = 1}|.

Характеристики ребер гиперграфа:

·          r(u_j) – количество вершин множества X, инцидентных ребру u_j. По матрице инцидентности А_H этот показатель рассчитывается по формуле:

                                              n

                                 r(u_j) = S a_i,j .

                                             i=1

Для гиперграфа, изображенного на рисунке 11, s(u₁) = 4.

При аналитическом представлении гиперграфа  этот показатель определяется по выражению:

                                           r(u_j) = | Г₂ u_j |.

 Для ребра u₂  того же гиперграфа Г₂u₂ = {x₁,x₅} и  r(u₂) = 2;

·     s(u_j)– количество ребер, смежных ребру u_jÎU. По матрице смежности R₂ этот показатель рассчитывается по формуле:

                                               m

                                   s(u_j) = S r_2j,k.                                                                                                                                                    

                                              k=1

Для ребра u₁ гиперграфа, показанного на рисунке 11, s(u₁) = 2.

При известных образах ребер относительно предиката смежности         F₂ (U, U):

                                          s(u_j) = | F₂u_j |.

Для ребра u₂ гиперграфа, изображенного на рисунке 11, F₂u₂ = {u₁}, тогда s(u₁) = 1;

·          Q(u_j) = {q_k(u_j) / k = 1, | U_j|}– вектор, каждый элемент которого q_k(u_j) равен количеству вершин множества X_j = Г₂u_j, инцидентных ребру u_i Î U_j = F₂u_j:

                          q_k(u_j) = | Г₂u_j Ç Г₂u_i |.

Для ребра u₁ гиперграфа, показанного на рисунке 14,a, X₁ = Г₂u₁ = {x₁, x₂, x₃, x₄}, U₁ = F₂u₁ = {u₂, u₃}, Г₂u₂ = {x₁, x₂, x₅}, Г₂u₃ = {x₃, x₆},                       q₁(u₁) = | Г₂u₁ Ç  Г₂u₂ | = 2,  q₂(u₁) = | Г₂u₁ Ç Г₂u₃ | = 1 (сравните с гиперграфом на рисунке 14,б).

Рисунок 14 – К определению характеристики Q(u_j) ребер гиперграфа

Обыкновенные ориентированные графы. Этот вид графа получим в том случае, если предикаты Г₁ (X, U) и Г₂ (U, X) таковы, что

                         " u_j Î U (|Г₁u_j| = |Г₂u_j| = 1) ,    (33)

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

        Ребра ориентированного графа G (X, U) обычно в литературе называют дугами и изображают стрелками, соединяющими соответствующие пары вершин. С учетом (1) примем такое же изображение, имея в виду, что дуга u_j идет из вершины  x_i в вершину x_k, если  Г₁ (x_i,u_j) = «и» &       Г₂ (u_j,x_k) = «и», и соединяет вершину x_k  с вершиной x_i, если Г₁ (x_k,u_j) = «и» & Г₂ (u_j,x_i) = «и». Такое изображение ориентированного графа показано на рисунке 15,а, а в виде двудольного графа – на рисунке 15,б.

Рисунок 15 – Ориентированный граф (а) и его представление в виде двудольного (б)

Представление ориентированного графа матрицами инцидентности. Как и для ультраграфа полным способом формального задания ориентированного графа является его представление через две матрицы инцидентности А₁ и A₂, где А₁– матрица истинности предиката Г₁ (X, U) и А₂ – матрица истинности предиката Г₂ (U, X).

Элементы этих матриц определяются по тем же правилам, что и для ультраграфа. Напомним, что матрица А₁ задает инцидентность между вершинами и ребрами, а матрица А₂ –между ребрами и вершинами.

Матрицы  А₁ и А₂  ориентированного графа, показанного на рисунке 15, имеют вид:

			u1	u2	u3	u4	u 5					x1	x2	x3	x4
		x1	1	1	0	0	0				u1	0	1	0	0
		x2	0	0	1	0	0				u2	0	0	0	1
A1	=	x3	0	0	0	1	0	,	A2	=	u3	0	0	0	1	.
		x4	0	0	0	0	1				u4	0	1	0	0
											u 5	0	0	0	1

В ряде работ вместо двух матриц  инцидентности А₁ и А₂ предлагается использовать одну, обозначим ее как А. Элементы этой матрицы определяются по правилу:

                                        ì   1 – если вершина x_i является началом дуги u_j,

                  a_i ,_j = í  -1– если вершина x_i является концом дуги u_j,

 î   0 – в противном случае,

где  i = 1, n;  n = | X |,  j =1, m;  m = | U |.

Нетрудно убедиться, что матрица А является матрицей истинности предиката T(X,U) = Г₁(X,U) Ú Г₂^-1(X,U), в котором истинность значения Г₁(x_i,u_j) обозначена как «1», а значения Г₂^-1(x_i,u_j) как «-1»:

a_i,_j = 1 – если вершина x_i является началом дуги u_j, и Г₁(x_i,u_j) = «и»,если ребро u_j  инцидентно вершине x_i ;

a_i,_j = -1 – если вершина x_i является концом дуги u_j,_, и Г₂^-1 (x_i,u_j) = «и», если вершина x_i инцидентна ребру u_j .

Напомним, что предикат  Г₂^-1 (X, U) является обратным к предикату Г₂ (U, X) – «ребрам множества U инцидентны вершины множества X».

Матрицы истинности A – предиката T (X, U)  и A₂^-1 – предиката Г₂^-1 (X, U) для ориентированного графа, изображенного на рисунке 15, имеет вид

Сопоставьте матрицы истинности предиката Г₁ – A₁ , предиката Г₂^-1 – A₂^-1 и матрицу A.

При указанном определении элементов матрицы А она не может быть использована для представления графов с петлями. Данный недостаток можно устранить, если элементу матрицы присваивать значение, например ±1, если u_j петля при вершине x_i. Такая матрица, обозначим ее через A’. для ориентированного графа, изображенного на рисунке 15, имеет вид:

						u1	u2	u3	u 4	u 5
					x1	1	1	0	0	0
					x2	-1	0	1	-1	0
				A’ =	x3	0	0	0	1	0	.
					x4	0	-1	-1	0	±1

Аналитическое представление ориентированного графа – образами и прообразами множеств вершин и ребер относительно предикатов Г₁ (X, U) и Г₂ (U, X). В ориентированном графе образ  вершины x_iÎX относительно предиката  Г₁ (X, U), т. е. подмножество U_i⁺ Í U инцидентных ей ребер, определяется аналогично ультраграфу как характеристическое множество Г₁x_i предиката-свойства Г₁x_i (U), т. е. вектора-строки матрицы А₁. Множество подмножеств ребер, инцидентных вершинам x_i Î X, т. е. образ множества X относительно предиката  Г₁, будет

                                  Г₁X = {Г₁x_i / x_i Î X},

 где Г₁x_i = U_i⁺ = {u_j Î U : Г₁x_i (u_j) = «и» } .

В соответствии с (33) образом ребра u_jÎU относительно предиката Г₂ (U, X) будет одноэлементное подмножество X_j⁺. Образ множества ребер U относительно того же предиката будет задаваться множеством одноэлементных подмножеств X_j⁺ – характеристических подмножеств предикатов-свойств Г₂u_j(X),  т. е. строк матрицы А₂ :

                        Г₂U = { Г₂u_j / u_j Î U },

где Г₂u_j = X_j⁺= { x_i Î X : Г₂u_i (x_i) = «и» }  , | X_j⁺| = 1.

Ориентированный граф, заданный множествами вершин X, ребер U и их образами, т. е. множествами подмножеств Г₁ X и Г₂ U, будем обозначать как G (X, U, Г₁X, Г₂U).  Ориентированный граф, изображенный на рисунке 15, этим способом будет задан через:

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

Г₁ X = {Г₁x_i /i=1,4},

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

Г₂ U = { Г₂u_j / j = 1,5},

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

Прообраз вершины x_i, т. е. множество ребер, которым она инцидентна, является характеристическим множеством i-го вектора-строки матрицы истинности А₂^-1 предиката Г₂^-1 (X, U) или характеристическим множеством i-го вектора-столбца матрицы А₂, т. е. предиката-свойства Г₂x_i (U) – U_i^– = Г₂x_i.

Прообразом множества X относительно предиката Г₂ (U, X) будет множество характеристических подмножеств предикатов-свойств Г₂x_i (U):

                             Г₂ X = { Г₂x_i / x_i Î X },

где Г₂x_i  = U_i^– = {u_j Î U : Г₂x_i (u_j) = «и» } .

Прообразом Г₁u_j ребра u_jÎ U  ориентированного графа относительно предиката Г₁ (X, U) будет одноэлементное подмножество X_j^–. Это подмножество является характеристическим множеством предиката-свойства Г₁u_j (X), соответствующего j-у вектору-столбцу матрицы А₁.

Прообразом множества U относительно предиката Г₁ (X, U) является множество характеристических подмножеств предикатов-свойств   Г₁u _j(X):

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

где  Г₁u_j = X_j^– = {x_i Î X : Г₁u_i (x_i) = «и» }  , | X_j^– | = 1 .   

У ориентированного графа, показанного на рисунке 15,

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

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

Для данного способа представления ориентированный граф будем обозначать G (X, U, Г₁X, Г₂X, Г₁U, Г₂U).

Предикаты смежности F₁ (X, X) вершин и F₂ (U, U) ребер ориентированного графа. Связь предиката смежности F₁ (X, X) вершин ориентированного графа с предикатами инцидентности Г₁ (X, U) и Г₂ (U, X) устанавливает выражение (4). Вершины, смежные вершине x_i, задаются предикатом – свойством, который определяется по формуле (5). Например, у  ориентированного графа, показанного на рисунке 15, Г₁x₁ = {u₁, u₂}, характеристические вектора предикатов Г₂u₁ (X), Г₂u₂ (X) и F₁x₁ (X)  будут:

Г₂u₁(X) = {0, 1, 0, 0}, Г₂u₂ (X) = {0, 0, 0, 1}  и

F₁x₁(X) = Г₂u₁ (X) Ú Г₂u₂ (X) = {0, 1, 0, 1}.

Предикат-отношение смежности  F₁ (X, X) получается по выражению (6).

Значения элементов r_1i,t (i, t = 1,n ; n = |X|) матрицы смежности R₁ вершин ориентированного графа определяются по тому же правилу, что и ультраграфа. Матрица смежности R₁ ориентированного графа, изображенного на рисунке 15, имеет вид:

Изображение графа смежности вершин ориентированного графа без кратных ребер совпадает с его представлением, показанном на рисунке 15,а, так как истинность отношений инцидентности Г₁ (X, U) и Г₂ (U, X) при данном способе не отображается. Очевидно, что в графе смежности вершин ориентированного мультиграфа не будет кратных ребер.

Вершины, которым смежны вершины множества X, задает предикат              F₁^-1 (X, X). Связь предиката F₁^-1 (X, X), обратного к предикату F₁ (X, X), с предикатами инцидентности Г₁ (X, U) и Г₂ (U, X) устанавливает выражение (7). Вершины, которым смежна вершина x_i, задаются предикатом – свойством F^-1x_i (X), определяемым по формуле (8). Например, у ориентированного графа, показанного на рисунке 15, Г₂ x₄ = {u₂, u₃, u₅}, характеристические вектора предикатов Г₁u₂ (X), Г₁u₃ (X) , Г₁u₅ (X) и  F₁^-1x₄ (X)  будут:

Г₁u₂ (X) = {1, 0, 0, 0}, Г₁u₃ (X) = {0, 1, 0, 0}, Г₁u₅ (X) = {0, 0, 0, 1} и

F₁^-1x₄ (X) = Г₁u₂ (X) Ú Г₁u₃ (X) Ú Г₁u₅ (X) = {1, 1, 0, 1}.

 Предикат-отношение смежности  F₁^-1(X,X) получается по выражению (9).

Матрица истинности R₁^-1  предиката F₁^-1(X,X) по матрице смежности R₁ в соответствии с (10) получается транспонированием последней и для графа, изображенного на рисунке 15, имеет вид:

Смежность ребер ориентированного графа определяется так же, как и ультраграфа. Связь предиката F₂ (U, U) смежности ребер  ориентированного графа с предикатами инцидентности Г₁ (X, U) и Г₂ (U, X) устанавливает выражение (11), а предиката F₂^-1 (U, U) с теми же предикатами –  выражение (13). С учетом (33), т. е. того факта, что в обыкновенном ориентированном графе ребру инцидентна только одна вершина и ребро инцидентно так же одной вершине, ребра, смежные ребру u_j, будут определяться по формуле:

              F₂ u_j (U) = Г₁ x_i (U), x_i = Г₂u_j ,                                 (34)

а ребра, которым смежно ребро u_j, – по формуле:

                     F₂^-1 u_j (U) = Г₂ x_i (U), x_i = Г₁u_j                                  (35)                                 

(сравните с выражениями  (12) и (14) соответственно).

Для ребра u₃ ориентированного графа, изображенного на рисунке 16:

Г₂ u₃ = {x₁} и характеристический вектор F₂ u₃ (U) = Г₁ x₁ (U) = {1,1,0,0},

Г₁ u₃ = {x₃} и характеристический вектор F₂^-1 u₃ (U) = Г₂ x₃ (U) = {0,1,0,1}.

Предикаты-отношения смежности ребер ориентированного графа F₂(U,U) и F₂^-1(U,U)  по предикатам инцидентности Г₁ и Г₂  будут определяться по следующим выражениям:

                 F₂ (U, U) = {Г₁ x_i (U), x_i = Г₂u_j / u_j Î U }               (36)

и             F₂^-1 (U, U) = {Г₂ x_i (U), x_i = Г₁u_j / u_j Î U }  .            (37)

Рисунок 16 – Ориентированный граф (к определению смежности вершин и ребер)

Элементы матрицы смежности  R₂ ребер ориентированного графа определяются по правилу:

                            ì   1 – если  a_2j,i =1 & a_1i,k=1,

                  r_2j,k = í  

 î   0 – в противном случае,

где  j, k = 1, m;  m = | U |,  i = 1, n;  n = | X |,  a_2j,i и a_1i,_k – элементы матриц инцидентности А₂ и А₁ соответственно. Матрицы инцидентности  А₁, А₂  и смежности  R₂ ребер ориентированного графа, изображенного на рисунке 16, будут:

Граф смежности G (U, U) ребер ориентированного графа, соответствующий матрице R₂, показан на рисунке 17. Здесь ребра изображены кружками, а истинность  F₂ (u_j, u_k) – стрелками.

Рисунок 17 – Граф смежности ребер ориентированного графа, изображенного на рисунке 16

Матрица истинности R₂^-1 предиката F₂^-1 (U, U) на основании (15 ) получается транспонированием матрицы R₂.

Образы и прообразы множеств вершин  и  ребер ориентированного  графа относительно предикатов их смежности F₁ (X, X) и     F₂ (U, U) соответственно. Для каждой вершины x_iÎX  ориентированного графа ее образ F₁x_i относительно предиката смежности F₁(X, X) (множество смежных ей вершин X_i⁺) определяется характеристическим множеством предиката-свойства F₁x_i (X). Истинность предиката-свойства F₁x_i (X) задается i-м вектором-строкой матрицы R₁.

Множество вершин X_i^–, которым смежна вершина x_i , т. е. ее прообраз F₁^-1x_i относительно предиката F₁ (X, X), является характеристическим множеством предиката-свойства F₁^-1x_i (X) . Истинность предиката-свойства F₁^-1x_i (X) задается i-м вектором-строкой матрицы R₁^-1 или соответствующим вектором-столбцом матрицы  R₁.

По аналитическому представлению ориентированного графа в виде  G (X, U, Г₁X, Г₂X, Г₁U, Г₂U) для каждой вершины x_i Î X ее образ F₁x_i определяется по выражению (16), а прообраз F₁^-1x_i – по выражению (17).

Если в ориентированном графе нет кратных ребер, то с учетом (33) эти формулы упрощаются и имеют соответственно вид:

                F₁x_i = {Г₂u_j / u_j Î Г₁ x_i }                                           (38)

и             F₁^-1x_i = {Г₁u_j / u_j Î Г₂ x_i }  .                                       (39)

У ориентированного графа, изображенного на рисунке 16, на основании (38) и (39) образ вершины x₁ и прообраз вершины x₃  будут получены так:

Г₁ x₁ = {u₁, u₂},  Г₂ u₁ = {x₂}, Г₂ u₂ = {x₃}, F₁ x₁ = {x₂ , x₃};

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

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

                                 F₁X = {F₁x_i / x_i Î X}

и                              F₁^-1X = {F₁^-1x_i / x_i Î X}.

Для того же ориентированного графа множества образов F₁ X и прообразов  F₁^-1 X его вершин относительно предиката смежности F₁ будут:

F₁ X ={F₁x_i /i = 1,3}: F₁x₁ = {x₂, x₃}, F₁x₂ = {x₃}, F₁x₃ = {x₁};                                               F₁^-1 X = {F₁^-1x_i / i = 1,3}:    F₁^-1x₁ = {x₃},  F₁^-1x₂ = {x₁},   F₁ ^-1x₃ = {x₁, x₂}.

Образ F₂u_j и прообраз F₂^-1u_j ребра u_j Î U  относительно предиката F₂ (U, U), т. е. множества U_j⁺ смежных ему ребер и U_j^– ребер, которому это ребро смежно, являются характеристическими множествами предикатов-свойств  F₂u_j (U) и F₂^-1u_j (U) соответственно. Истинность предиката F₂u_j (U) задается j-м вектором-строкой матрицы R₂, а истинность предиката F₂^-1u_j (U) – j-м вектором-строкой матрицы R₂^‑1 или соответствующим вектором-столбцом матрицы R₂.

По аналитическому представлению ориентированного графа для каждого ребра  u_j Î U его образ F₂u_j и прообраз F₂^-1u_j определяются на основании (34) и (35) : 

                           F₂u_j = Г₁x_i ,   x_i = Г₂u_j ,                                  (40)

              и          F₂^-1u_j = Г₂x_i ,   x_i = Г₁u_j .                                 (41)

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

                                 F₂U = { Г₁x_i , x_i = Г₂u_j  / u_j Î U}

и                              F₂^-1U = { Г₂x_i , x_i = Г₁u_j  / u_j Î U}.

Для ориентированного графа, изображенного на рисунке 16, множества образов F₂U и прообразов F₂^-1U его ребер относительно предиката смежности F₂ будет:

F₂U = {F₂u_j / j = 1,4}:  F₂u₁ = {u₄}, F₂u₂ = {u₃}, F₂u₃ = { u₁, u₂}, F₂u₄ = {u₃},      F₂^-1U = {F₂^-1u_j / j = 1,4}: F₂^-1u₁ = F₂^-1u₂ = {u₃}, F₂^-1u₃ = {u₂, u₄}, F₂^-1u₄ = {u₁}.

Задание ориентированного графа множествами вершин X, ребер U и их  образами и прообразами относительно предикатов смежности F₁(X,X) и F₂(U,U) соответственно будем обозначать G (X, U, F₁X, F₁^-1X,                                 F₂U, F₂^-1U) .                                                                    

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

Характеристики вершин и ребер ориентированного графа. К характеристикам вершин относятся:

·         r⁺ (x_i) – полустепень исхода, т. е. количество ребер, инцидентных вершине x_i Î X;

·           r^- (x_i) – полустепень захода, т. е. количество ребер, которым инцидентна вершина x_i Î X. 

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

Для графа, изображенного на рисунке 16, полустепень исхода вершины x₁ по матрице A₁ будет 

                                                   4

                                             r⁺(x₁) = S a_11,j =2

                                                                                   j=1

и вершины x₂ по аналитическому  представлению  r⁺(x₂) = | Г₁x₂ |=1;                                            

полустепень захода вершин x₃ и x₁ по матрице A₂ и по аналитическому представлению соответственно –                                                                  

                                 4

                           r^-(x₃) = S a_2j,3 = 2 и  r^-(x₁) = | Г₂x₁ | =1;            

                                j=1

·     s⁺ (x_i) – количество вершин, смежных вершине x_i Î X ;

·     s^- (x_i)– количество вершин, которым смежна вершина x_i Î X.

Эти показатели имеют смысл только для мультиграфа, так как для графа без кратных ребер они совпадают с полустепенями исхода и захода соответственно. По матрицам смежности R₁ и R₁^-1 и при известных образах и прообразах вершин относительно предиката смежности F₁(X,X) эти показатели рассчитываются по тем же формулам, что и для ультраграфа.                                 

Для вершины x₁ ориентированного графа, показанного на рисунке 18,  r⁺ (x₁) = 3, а s⁺ (x₁) = 2 и r^- (x₁) = 1, а s^- (x₁) = 1;

·     e(x_i) = |{u_j Î U : Г₁u_j = Г₂u_j = x_i}| – количество петель при вершине x_i.

Рисунок 18 – Ориентированный мультиграф

Характеристики ребер ориентированного графа:

·          s⁺(u_j)– количество ребер, смежных ребру u_jÎU;

·          s^-(u_j)– количество ребер, которым смежно ребро u_jÎU.

 По матрицам смежности R₂ или R₂^-1и при известных  образах и прообразах ребер относительно предиката смежности F₂(U,U) эти показатели рассчитываются по тем же формулам, что и для ультраграфа.

Например, для ребер u₃ и u₁ ориентированного графа, показанного на рисунке 16,

       4                                             4

 s⁺(u₃) = S r_23,j = 2   и  s^-(u₁) = S r_2i,1 = 1  или

              j=1                                             i=1

 s⁺(u₃) = | F₂u₃ |=2   и  s^-( u₁) = | F₂^-1u₁| = 1.

  Если образы и прообразы ребер относительно предиката смежности F₂ (U, U) не заданы, эти показатели при известных образах Г₁X множества вершин X относительно предиката Г₁ (X, U) и прообразах Г₂X  относительно предиката Г₂ (U, X), а также образах и прообразах множества ребер относительно соответствующих предикатов, на основании (38) и (39)  будут определяться по формулам:                                                                                                                                                   

s⁺(u_j) = | Г₁x_i |,  x_i  = Г₂ u_j   и  s^-(u_j) = | Г₂x_i |,  x_i  = Г₁ u_j .

Обыкновенные неориентированные графы. Данный вид графа можно определить как два непересекающихся множества вершин X и ребер U, на элементах которых задана пара двуместных предикатов-отношений  инцидентности Г₁ (X, U) и Г₂ (U, X), удовлетворяющих условиям (1), (20) и выражению:

                         " u_j Î U  (|Г₁u_j| = |Г₂u_j| = 2).

 Таким образом ребра обыкновенного неориентированного графа соединяют вершины попарно, а предикат Г₂ (U, X) на основании (20) является обратным к предикату Г₁ (X, U). Обыкновенный неориентированный граф будет задан, если заданы множества   X, U и один из этих предикатов. Из сказанного выше следует, что он является частным случаем гиперграфа. Изображение неориентированного графа дано на рисунке 19.

Рисунок 19 – Неориентированный граф (а) и мультиграф (б)

 Представление неориентированного графа матрицей инцидентности. Так как матрица предиката Г₂ (U, X) является транспонированной матрицей предиката Г₁ (X, U), для матричного представления неориентированного графа достаточно одной из них. В качестве матрицы инцидентности A будем использовать матрицу истинности предиката Г₁ (X, U), размером n´m, где n = |X|, а m = |U|. Элементы этой матрицы определяются по тому же правилу, что и для гиперграфа.

Матрица инцидентности графа, показанного на рисунке 19,б, имеет вид

Представление неориентированного графа образами вершин и ребер относительно предикатов Г₁ (X, U) и Г₂ (U, X). В неориентированном графе образ Г₁x_i вершины x_iÎX относительно предиката  Г₁ (X, U) является характеристическим множеством предиката-свойства Г₁x_i (U), т. е. вектора-строки матрицы А. Множество подмножеств ребер, инцидентных вершинам x_i Î X, т. е. образ множества X относительно указанного предиката, определяется по выражениям (23). 

Образ множества ребер U относительно предиката Г₂ (U,X), т. е. множество   подмножеств Г₂u_j, будет задаваться множеством характеристических подмножеств предикатов-свойств Г₂u_j (X),  т. е. столбцов матрицы А  и определяется по выражениям (24). На основании (20) и (33) количество вершин, инцидентных каждому ребру неориентированного графа без петель,  | Г₂u_j | = 2.

Неориентированный граф данным способом будет задан, если заданы множества вершин X, ребер U и их образы, т. е. множества подмножеств Г₁X и Г₂U. Граф в данном случае будем обозначать как G (X, U, Г₁X, Г₂U). Неориентированный граф, изображенный на рисунке 19,б, этим способом будет представлен:

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

Г₁X = {Г₁x_i /i = 1,4},

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

Г₂U={ Г₂u_j / j=1,6}, 

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

Рассмотренное представление неориентированного графа, так же как и матричное, является полным. 

Предикаты смежности F₁(X,X) вершин и F₂(U,U) ребер неориентированного графа. Для вершин x_i, x_k ÎX  связь предиката смежности F₁ (X, X) с предикатами Г₁ (X, U) и Г₂(U, X) определяется выражением (25).

Инцидентные вершине x_i ребра задает характеристическое множество U_i = Г₁x_i предиката-свойства  Г₁x_i  (U). Вершины, инцидентные ребру u_j Î U_i , определяет предикат-свойство Г₂u_j (X). Если u_j не является петлей, подмножество Г₂u_j состоит из двух вершин, одна из которых x_i (смотри первые пять столбцов матрицы А).Таким образом,  вершины, смежные вершине x_i, будут задаваться предикатом – свойством, определяемым по выражению (26).                         

У графа, показанного на рисунке 19,б, U₂ = Г₁x₂ = {u₁, u₂, u₃, u₅} и характеристические вектора предикатов Г₂u₁  (X), Г₂u₂ (X), Г₂u₃ (X),            Г₂u₅ (X) равны:

Гu₁ (X) ={1,1,0,0}, Гu₂ (X) = {0,1,0,1}, Гu₃ (X) = {0,1,1,0}, Гu₅ (X) = {0,1,1,0}.

После присваивания Г₂u₁ (x₂), Г₂u₂ (x₂), Г₂u₃(x₂) и Г₂u₅ (x₂) значения «0» получаем

F₁x₂ (X) =  Г₂u₁ (X) Ú Г₂u₂ (X) Ú Г₂u₃ (X) Ú Г₂u₅ (X) ={1,0,1,1},т. е. вершина x₂ смежна вершинам x₁, x₃, x₄.

Предикат-отношение F₁ (X, X) смежности вершин неориентированного графа определяется выражением (27).

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

Матрицы смежности R₁ и R₁¢, вершин  графов, изображенных на рисунках 19,а и б, будут иметь вид:

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

Для ребер u_j, u_r Î U  связь предиката смежности F₂ (U, U) с предикатами Г₂ (U, X) и Г₁ (X, U) определяется выражением (26). Вершины, инцидентные ребру u_jÎU, задает характеристическое множество X_j = Г₂u_j  предиката-свойства  Г₂u_j  (X). Ребра, инцидентные вершине x_iÎX, определяет предикат-свойство Г₁x_i (U). Подставляя в Г₁ (X, U) вершины множества  X_j (| X_j | = 2), получаем пару предикатов-свойств {Г₁x_i (U)},  x_i Î X_j, каждый из которых задает ребра, смежные ребру u_j по вершине x_i. Предикат-свойство F₂u_j (U), задающий ребра, смежные ребру u_jÎU в неориентированном графе, определяется по выражению (29).

У графа, показанного на рисунке 19,б, Г₂u₁ = {x₁, x₂} и характеристические вектора предикатов Г₁x₁(U) и Г₁x₂(U) имеют значения:

Г₁x₁ (U) ={1, 0, 0, 0, 0, 0} и Г₁x₂ (U) = {1, 1, 1, 0, 1, 0}.

Так как |Г₂u₁| = 2, присваиваем Г₁x₁( u₁) и Г₁x₂( u₁) значения «0» и получаем

F₂u₁(U) = {0, 0, 0, 0, 0, 0}Ú {0, 1, 1, 0, 1, 0} = {0, 1, 1, 0, 1, 0}, т. е. ребро u₁ смежно  ребрам u₂, u₃ и u₅.

Предикат-отношение F₂ (U, U) смежности ребер неориентированного графа определяет выражение (30). Элементы матрицы смежности   ребер R₂ по матрице инцидентности А определяются по тому же правилу, что и гиперграфа. Матрица смежности ребер неориентированного мультиграфа, изображенного на рисунке 19,б, имеет вид:

Граф смежности ребер этого же графа представлен на рисунке 20.

Рисунок 20 – Граф смежности ребер графа, изображенного на рисунке 19,б

Здесь ребра неориентированного графа  изображены кружками, а истинность  F₂(u_j, u_r) – линиями.

Образы множеств X и U относительно предикатов смежности вершин F₁ (X, X) и ребер F₂ (U, U) соответственно. Для каждой вершины x_i Î X  неориентированного графа G (X, U) множество смежных ей вершин X_i = F₁x_i определяется характеристическим множеством предиката-свойства F₁x_i (X), истинность которого задается i-м вектором-строкой матрицы R₁.

По аналитическому представлению графа в форме G(X, U, Г₁X, Г₂U) для каждой вершины x_i Î X ее образ Fx_i на основании (26) определяется  по правилу (31). Для неориентированного графа без кратных ребер формула упрощается и имеет вид:

  F₁x_i  = { Г₂u_j \ x_i : | Г₂u_j | = 2 Ú Г₂u_j : | Г₂u_j | = 1 / u_j Î Г₁x_i }.           (42)

Для графа, изображенного на рисунке 19,а, множество ребер, инцидентных вершине x₂, т. е. ее образ относительно   предиката Г₁(X, U), –  Г₁x₂ ={u₁, u₂, u₃} и образы каждого из этих ребер относительно предиката Г₂(U, X) будут: Г₂u₁={x₁, x₂}, Г₂u₂={x₂, x₄}, Г₂u₃={x₂, x₃}. Исключив из  Г₂u_j  вершину x₂, получим   F₁x₂ ={x₁, x₄, x₃}.

Множество образов  F₁X ={ F₁x_i / x_iÎ X } вершин этого графа относительно предиката смежности F₁(X,X) будет:

F₁X = {F₁x_i /i =1,4}: 

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

Для каждого ребра u_j Î U  неориентированного графа G (X, U) множество смежных ему ребер U_j = F₂u_j определяется характеристическим множеством предиката-свойства F₂u_j (U), истинность   которого задается j-м вектором-строкой матрицы R₂.

По аналитическому представлению графа образ ребра F₂u_j на основании (32) определяется  по правилу

 F₂u_j = {Г₁x_i \ u_j : | Г₂u_j | = 2 Ú Г₁x_i : | Г₂u_j | = 1 / x_i Î Г₂u_j}.            (43)

Для графа, изображенного на рисунке 19,а, множество вершин, инцидентных ребру u₂, т. е. его образ относительно предиката  Г₂(U, X) –  Г₂u₂ ={x₂, x₄} и образы каждой из этих вершин относительно предиката Г₁(X, U)  будут: Г₁x₂={u₁, u₂, u₃}, Г₁x₄={u₂, u₄}. Исключив из  Г₁x_i  ребро u₂, получим   F₂u₂ ={u₁, u₃, u₄}.

Множество образов F₂U = { F₂u_j / u_jÎ U } ребер этого графа относительно предиката смежности F₂(U,U)  будет:

F₂U = {F₂u_j /i =1,4}: 

F₂u₁ = {u₂, u₃}, F₂u₂ ={u₁, u₃, u₄}, F₂u₃ ={u₁, u₂, u₄},  F₂u₄ = {u₂, u₃}.

Аналитическое представление неориентированного графа множествами вершин X, ребер U и их образами относительно предикатов смежности F₁(X, X) и F₂(U, U) соответственно будем обозначать G (X, U, F₁X, F₂U).

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

Характеристики вершин и ребер неориентированного графа. К характеристикам вершин относятся:

·          r(x_i) – локальная степень вершины, т. е. количество ребер, инцидентных вершине x_i Î X.

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

Для графа, изображенного на рисунке 19,б, локальная степень вершины x₂ по матрице A будет  

               6

 r(x₂) = Sa_{2, j} =4

              j=1

и вершины x₄ по аналитическому представлению –

 r(x₄) = | Г₁x₄ |=2;

·        s(x_i) – количество вершин, смежных вершине x_iÎX. Этот показатель имеет смысл только для мультиграфа, так как для графа без кратных ребер он совпадает с локальной степенью. По матрице смежности R₁  и при известных образах вершин относительно предиката смежности F₁(X,X) этот показатель определяется по тем же формулам, что и для гиперграфа.  

                                                                                          4

Для вершины x₂ того же графа  s(x₂) = Sr_{12, j} =3 – сравните с s(x₃) =4.

                                                                           j=1

·     e(x_i) – количество петель при вершине x_i. По матрице инцидентности A и при аналитическом представлении характеристика определяется по тем же  выражениям, что и для гиперграфа.

Характеристики ребер неориентированного графа:

· s(u_j)– количество ребер, смежных ребру u_jÎU.

По матрице смежности R₂ и при известных  образах ребер относительно предиката смежности F₂ (U, U) этот показатель рассчитывается по тем же формулам, что и для гиперграфа.

Например, для ребер u₃ и u₁ неориентированного мультиграфа, показанного на рисунке 19,б,

       6                                           

 s(u₃) =S r_23,j =5   и для ребра  u₁ графа, изображенного на рисунке 19,а,

    j=1                                        

 s ( u₁) = | F₂u₁| = 2.

 

  Литература

1. Овчинников В.А. Автоматизация комбинаторно‑оптимизацион-ных задач при проектировании ЭВМ и систем: Учеб. для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.