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

УДК 004.3 :519.6                                                                              

Иванова Г.С.

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

Задание отношений смежности и инцидентности на универсумах вершин и ребер графовых моделей выполняют в матричной или аналитической форме. Обе формы позволяют описывать только двуместные отношения. В табличной форме элемент таблицы фиксирует наличие отношения R Ì A ´ B между элементом a_i, сопоставленным строке i, и элементом b_j, сопоставленным столбцу матрицы j, т. е. (a_i, b_j) Î R, a_iÎ A & b_j Î B.  В аналитической – каждое множество описания по отношению смежности или инцидентности представляет собой совокупность образов элемента исходного множества по задаваемому отношению, т. е. Ra_i = {b_j / a_iÎ A & b_j Î B & (a_i, b_j) Î R}.

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

Отношения смежности вершин гиперграфов и ультраграфов n-местны, однако, каждое из них может быть представлено как множество двуместных отношений. Так неориентированная n-местная связь (ребро гиперграфа), задаваемая множеством или мультимножеством Xⁿ_j = {x_i, x_k, …x_r}Î Fⁿ Ì Xⁿ, |Xⁿ_j| = n, может рассматриваться как совокупность попарных связей вершин ребра X_j = {{x_i, x_k}/ x_i, x_k Î Xⁿ_j}. Каждая пара множества X_j представляет собой фрагмент ребра гиперграфа и является элементом симметричного бинарного отношения  смежности, т. е. {x_i, x_k}ÎX_j & {x_i, x_k}Î F²Ì X²,  а количество таких пар равно |X_j| = n(n-1).

N-местное отношение порядка подмножеств (дуга ультраграфа), определяемое упорядоченной парой подмножеств вершин-источников X_i  и вершин-приемников  X_k, т. е.  Xⁿ_j = (X_i, X_k) Î FⁿÌ Xⁿ, | X_i | +| X_k |  = n, в этом случае будет представлено как множество упорядоченных пар X_j = {(x_r, x_c)/ x_rÎ X_i & x_cÎ X_k}. Количество пар равно – |X_j| = n₁n₂, где n₁= |X_i | £ n, n₂= |X_k | £ n, откуда n₁ n₂ £ n².

Ориентированная n-местная связь (дуга ориентированного гиперграфа), определяемая кортежем Xⁿ_j = (x_i, x_k, x_c, …, x_e, x_r) Î FⁿÌ Xⁿ, | Xⁿ_j | = n, соответственно, может рассматриваться как кортеж упорядоченных пар X_j = ((x_i, x_k), (x_k, x_c), …, (x_e, x_r)). Каждая упорядоченная пара кортежа X_j, представляющая собой фрагмент гипердуги, является элементом бинарного отношения смежности, т. е. (x_i, x_k) Î X_j & (x_i, x_k)Î F²Ì X², а количество таких пар равно |X_j| = n-1.

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

Матричное задание графовых моделей в случае одного универсума предполагает задание матрицы смежности, а в случае двух универсумов – матрицы инцидентности. Элемент матрицы смежности a_i,j соответствует упорядоченной паре (x_i, x_j). Для ориентированных и неориентированных графов этот элемент задается как

.

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

.                                               

В ориентированном графе каждой связи соответствует одна упорядоченная пара, а в неориентированном – две, поскольку {x_i, x_j} = {(x_i, x_j),( x_j, x_i)}. Соответственно неориентированные связи в матрице смежности отображаются два раза, а ориентированные – один, следовательно, матрица смежности неориентированного графа симметрична и может быть представлена в диагональной форме.

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

Таблица 1 – Задание отношений матрицами смежности

* – не позволяет адекватно задать графовую модель.

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

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

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

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

Для неориентированных графов и мультиграфов в матрице инциденций вершины-ребра указывают:

.

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

  .

Для ориентированных графов и мультиграфов матрица инцидентности должна отображать направление дуг: вершина инцидентна началу дуги, вершина инцидентна концу дуги. Соответственно для ориентированных графов множество отношений инцидентности Г₁ разбивается на два  – вершина инцидентна началу дуги, – вершина инцидентна концу дуги. Для смешанных графов и мультиграфов это множество разбивается уже на четыре подмножества:  – вершина инцидентна началу дуги, – вершина инцидентна концу дуги, Г(~)₁ – вершина инцидентна звену, Г(о)₁ – вершина инцидентна петле. Тогда элемент матрицы инцидентности смешанного графа или мультиграфа кодируется как (см. таблицу 2):

.

Таблица 2 – Задание отношений матрицами инцидентности

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

 Ç= Æ                                                                                                        (1)

может быть обозначено коэффициентом кратности k, например, <a, k>. При нарушении условия (1) элемент матрицы инциденций ультраграфа должен быть представлен парой двоек:

,

где a – признак инцидентности вершины началу ультрадуги, b – признак инцидентности вершины концу ультрадуги, а k₁, k ₂ – количество вершин, входящих в ультрадугу в каждом качестве.

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

  ,

где n – номер вхождения вершины x_i в гипердугу u_j, причем |{n}| = |(x_i, u_j)|.

В таблице 3 представлены способы матричного представления основных структурных моделей.

Таблица 3 – Матричное представление основных структурных моделей

* – не позволяет адекватно задавать графовую модель;

** – вместо «1» можно указать вес ребра или дуги;

*** – возможно задание также через смежность ребер

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

Аналитическое представление графовых моделей. Аналитически графовые модели определяются отображениями соответственно образами по отношению смежности вершин XFX, ребер UFU и по отношению инцидентности вершины-ребра XГU  или ребра-вершины UГX. При построении образов отображений по отношению смежности для гиперграфов и ультраграфов необходимо также как при построении матриц смежности перейти от n-местных к двуместным отношениям.

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

Таблица 4 – Аналитическое задание отношений смежности

* – не позволяет адекватно задать графовую модель.

Аналитическое задание гиперграфа и ультраграфа возможно только через отношение инцидентности (см. таблицу 5). При этом каждое ребро может соединять более двух вершин, а, следовательно, |Гu_j| ³ 2 (соответственно, || ³ 1, || ³ 1 – для ультраграфа).  Повторное вхождение вершин в гиперребро или ультрадугу отображается повторным вхождением идентификатора вершины в соответствующие образы Fx_i, Гu_j  (соответственно ,  – для ультраграфа), которые при этом становятся мультимножествами.

Таблица 5 – Аналитическое задание отношений инцидентности

Аналитическое задание ориентированного гиперграфа требует определения порядка пар в кортеже пар гипердуги, что можно сделать, используя в качестве Гu_j кортежи. При использовании отображения ГX этот порядок необходимо показать явно, используя номера: <u_r, k_r>, где k_r – номер вершины в указанном гиперребре.

В таблице 6 рассмотрены способы аналитического представления основных графовых моделей.

Таблица 6 – Способы аналитического описания графовых моделей

 * – не позволяет адекватно задать графовую модель

Представление иерархических моделей. Для реализации стратегий проектирования «снизу-вверх» и «сверху-вниз» представление иерархических моделей помимо отношений смежности и инцидентности должно позволять задавать бинарное отношение вхождения Rⁱ вершин i-1-го уровня в вершину i-го уровня или обратное ему бинарное отношение включения (Rⁱ)^-1 вершин i-1-го уровня в вершину i-го уровня.

Отношение вхождения при этом определяется как

{(,)/Î} Ì  Rⁱ Ì ´ ,

где , – вершины i-го и i-1-го уровня соответственно;

– подмножество вершин i-1-го уровня, соответствующее , т. е. k-ой вершине i-го уровня;

, – множества вершин i-го и i-1-го уровня соответственно.

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

Аналогично при описании иерархии аналитически можно не указывать образы элементов верхнего уровня. Всего при аналитическом описании иерархии i =  необходимо будет построить образов по одному элементу в каждом, поскольку каждая вершина i-1- го уровня входит в единственную вершину i-го уровня.

Кроме того, отношение Rⁱ сюръективно, следовательно, его можно задать таблицей соответствия, в которых каждой вершине i-1-го уровня – аргументу функции сопоставлена вершина i-го уровня – значение функции (см. рисунок 1 и таблицу 7). Количество столбцов такой таблицы равно || = n^i-1, а количество строк равно 2. Соответственно, для иерархии i =  необходимо задать q таблиц соответствия, суммарным объемом V₁ = элементов.

Рисунок 1 – Пример иерархической модели

Таблица 7 – Таблица соответствия отношения R¹

Таблица 8   – Таблица соответствия отношения R²

Отношение включения (Rⁱ)^-1 – многозначно, т. е. не является функциональным, следовательно, его нельзя задать таблицей соответствия. Для его определения целесообразно использовать аналитическое представление. При этом для описания отношения включения на i-м уровне необходимо задать || = nⁱ образов вида:

(Rⁱ)^-1= {/Î& Î& (, ) Î (Rⁱ)^-1} = .

Соответственно, для иерархии i =  необходимо задать q отображений, общим объемом V₂ = элементов. Например, описание отношения включения модели, представленной на рисунке 1, множеством образов имеет вид:

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

(,) Î Ì ´ или  (,) Î ()^-1 Ì´,

где , – ребра i-1 и i-го уровней соответственно,

      , ()^-1 – прямая и обратная функции, причем – частичная, т. е. определена не на всем множестве , а только на множество внешних ребер кусков , в то время как функция ()^-1 – тотальная.

Данные функции также можно задать таблицами соответствия для нахождения ребра i – го уровня по ребру i-1 уровня и для нахождения ребра i-1 уровня по ребру i – го уровня. Отличие между этими таблицами заключается в том, что в таблице множеству внутренних ребер, для которых не определены соответствующие ребра i-го уровня,  будет сопоставлено «Æ».

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

Литература

1. Бершадский А.М. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. – Саратов: Изд-во Саратовского ун-та, 1983.

2. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Гл. ред. ф.-м. лит. изд «Наука», 1971.

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

4. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. – М.: Лаборатория Базовых Знаний, 2002.