Известия РАН. Теория и системы управления, 2023, № 4, стр. 84-97

Введение. Графы и гиперграфы широко применяются как в современных фундаментальных исследованиях, так и при решении практических задач. Причем достаточно часто возникает потребность в выделении определенных классов гиперграфов [1], предназначенных для использования в виде моделей или проверки работы ряда алгоритмов. К таким классам, например, относятся гиперсети [2], динамические геометрические гиперграфы [3]. Отдельно стоит сказать о топологии, где одно из основных понятий – комплекс [4], также относится к одному из классов гиперграфов – однородным гиперграфам. Данный класс гиперграфов используется в двух крупных направлениях фундаментальных исследований: раскраска однородного гиперграфа и различные экстремальные задачи, в том числе для случайных гиперграфов. Таких работ достаточно много, так что отметим наиболее современные и актуальные из них [5–9]. Однако есть направления практического применения однородных гиперграфов в различных областях науки и техники [10–17] от комбинаторики и шифрования до математического представления баз данных.

В теориях графов и гиперграфов является важным дать эффективное представление различных крупных структур [18], такие, как деревья [19, 20], матрицы смежности [21, 22], однородные гиперграфы. К поиску подобных способов определения крупных структур подталкивают реальные задачи. Например, практическая задача хранения гиперграфов и работы с ними является достаточно важной для анализа социальных сетей, которые имеют сотни миллионов сложных связей.

При этом хранение гиперграфов в общем случае не особенно эффективно, так как основной способ хранения – матрица инцидентности или список гиперребер. Если объем такого хранения не слишком велик, то работа с ними не удобна. Для k-однородных гиперграфов [21] есть возможность задания матрицы смежности, но ее объем равен n^k байт, где $n$ – количество вершин гиперграфа. Для экстремальных однородных гиперграфов появляется возможность использовать базу [21] в виде объекта хранения, она занимает в памяти меньше места, чем список гиперребер, но не всегда удобна с практической точки зрения.

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

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

1. Экстремальные однородные гиперграфы и сигнатура первого порядка. Для дальнейшего обсуждения приведем определения гиперграфов, их однородности и экстремальности.

Определение 1. Гиперграф $H({{V}_{n}},E)$ – совокупность множества V_n из $n$ вершин и множества непустых подмножеств множества вершин E [1], ${{e}_{i}}$ – элементы множества E, где $i = \overline {1,\left| E \right|} $ – гиперребра.

Определение 2. Гиперграф ${{H}^{k}} = {{H}^{k}}({{V}_{n}},E)$ называют k-однородным гиперграфом (uniform hypergraph (UH)), если ${\text{|}}{{e}_{i}}{\text{|}} = k$, $\forall {{e}_{i}} \in E$.

Определенные классы UH известны также под другими именами. При k = 2 можно говорить о ненаправленных графах без петель. При больших k однородные гиперграфы известны как k – 1 комплексы [24]. Этот термин пришел из топологии [4].

Одной из важных особенностей UH является их представление в виде k-индексной матрицы смежности ${{X}^{k}}({{H}^{k}}) = ({{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}})$, где индексы ${{i}_{j}} = \overline {1,n} $ при $j = \overline {1,k} $. Это позволяет эффективнее взаимодействовать с ними. Однако память тратится менее эффективно, чем при использовании матрицы инцидентности.

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

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

Определение 4. Доменом нулей – ${{D}_{0}}(X_{n}^{k})$ (единиц – ${{D}_{1}}(X_{n}^{k})$) называется множество значимых ячеек матрицы смежности, равных нулю (единице), при этом не существует значимой единичной (нулевой) ячейки, отличающейся от пары ячеек из D₀ (D₁) только одним индексом и находящейся между ними.

Определение 5. Однородный гиперграф $H_{n}^{k}$ называется экстремальным, если для соответствующей ему матрицы смежности $X_{n}^{k}(H_{n}^{k})$ выполняется правило разделения доменов нулей и единиц, состоящее из следующих условий:

1) все единичные ячейки образуют домен единиц;

2) все значимые нулевые ячейки образуют домен нулей;

3) ячейка ${{x}_{{1 \ldots k}}} \in {{D}_{1}}(X_{n}^{k})$ или ${{D}_{1}}(X_{n}^{k}) = \emptyset $;

4) ячейка ${{x}_{{n - k + 1 \ldots n}}} \in {{D}_{0}}(X_{n}^{k})$ или ${{D}_{0}}(X_{n}^{k}) = \emptyset $.

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

Пример 1. Рассмотрим экстремальный 2-однородный гиперграф. Для этого изучим матрицу, представленную на рис. 1. Здесь на главной диагонали находятся незначимые ячейки, а остальные явно разделены на D₁ и D₀. Также между ними проведена граница, обозначим ее b. Граница определена только на верхней половине матрицы, так как мы рассматриваем исключительно ненаправленные невзвешенные однородные гиперграфы без петель.

Пример 2. Теперь посмотрим на матрицу смежности 2-однородного, но не экстремального гиперграфа. Она представлена на рис. 2. Здесь мы можем легко найти пары ячеек, которые демонстрирует, что правило разделения доменов тут не действует. Например, это ${{x}_{{13}}} = {{x}_{{15}}} = 1$ с нулевой ячейкой между ними, ${{x}_{{36}}} = {{x}_{{56}}} = 0$ с единичной ячейкой между ними. Наличие хотя бы одной подобной пары однозначно свидетельствует о неэкстремальности рассматриваемого $UH_{8}^{2}$.

Большой интерес представляет вектор степеней вершин однородного гиперграфа, так как он позволяет однозначно восстановить (при наличии соответствующего алгоритма [24–26]) всю матрицу смежности, а соответственно и сам UH, а занимает в памяти меньший объем, чем матрица смежности.

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

Ранее в работе [23] было дано определение сигнатуры $EUH_{n}^{2}$. Сформулируем его в упрощенном виде.

Определение 6. Сигнатурой первого порядка σ¹ (или просто сигнатурой σ) экстремального 2-однородного гиперграфа $H_{n}^{2}$ называется характеристика в виде целого числа, отождествленная с границей разделения доменов нулей и единиц b. Она задается следующим образом: проходим по границе от правой верхней точки до нижней левой точки окончания границы. Граница b состоит из $n$ сегментов, которые расположены либо вертикально, либо горизонтально. Каждому вертикальному сегменту b устанавливается 1, а каждому горизонтальному – 0. Проходя по границе получаем разряды двоичного целого числа от старшего к младшему. Соответственно сигнатура представляется целым (двоичным или десятичным) числом.

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

Определение 7. Обозначим операцию получения длины сигнатуры $\sigma $ как lenσ, равную длине отождествленной границы и соответственно количеству двоичных разрядов сигнатуры.

Замечание 1. Заметим, что при представлении сигнатуры в десятичном виде есть неоднозначность при определении ее длины, а именно ${\text{len}}{\kern 1pt} \sigma > \left\lfloor {{{{\log }}_{2}}\sigma } \right\rfloor $ (где $\left\lfloor {x} \right\rfloor $ – взятие целой части от x). Таким образом длина сигнатуры в десятичном виде имеет нижнюю грань, но верхняя не определена и может зависеть от задачи.

Определение 8. Запишем значение k-го разряда сигнатуры $\sigma $ как ${{\sigma }_{{(k)}}} = \sigma {{\& 2}^{k}}$, где операция $\& $ – операция побитового “и”. Стоит отметить, что разряды нумеруются с нуля справа налево.

2. Сигнатуры второго порядка и их свойства. Сигнатура первого порядка задает $EU{{H}^{2}}$ . Для получения характеристики, позволяющей определить $EU{{H}^{3}}$, нужно рассмотреть его кубическую матрицу смежности.

Пусть $X_{n}^{3} = X_{n}^{3}(H_{n}^{3})$ – кубическая матрица смежности экстремального 3-однородного гиперграфа $H_{n}^{3}$, построенного на n вершинах. Представим ее как последовательность срезов (квадратных матриц). Набор срезов получаем перебором одного из индексов с фиксацией его внутри среза. Так как в UH предполагается, что ребро соединяет только различные вершины, то главные диагонали в каждом срезе не рассматриваются (и традиционно обозначаются нулем). Также не рассматриваются строка и столбец с номерами, равными номеру среза, так как иначе совпадают минимум пара координат, что противоречит структуре UH. Таким образом k-срез матрицы X³ имеет вид, представленный на рис. 3. Здесь серым обозначены ячейки, которые не являются значимыми при построении 3-однородного гиперграфа. Остальные ячейки могут иметь значения 0 или 1.

Кроме того, так как исследуются ненаправленные UH, то их матрицы смежности симметричны, а следовательно, симметричны и каждый из срезов относительно главной диагонали. Отсюда также можно сделать вывод, что выбор координаты (i, j или k) для построения срезов не важен. Из-за симметричности матрицы $X_{n}^{3}$ проистекает следующей свойство.

Свойство. Так как ${{x}_{{ijk}}} = {{x}_{{ikj}}} = {{x}_{{jik}}} = {{x}_{{jki}}} = {{x}_{{kij}}} = {{x}_{{kji}}}$, то значения t-среза задают значения с индексом t в других срезах матрицы. Таким образом можно представить декомпозицию кубической матрицы как набор срезов, где каждый t-срез определяет значения ${{x}_{{tij}}}$ только для $i = \overline {t + 1,n - 1} $ и $j = \overline {i + 1,n} $. Остальные значения либо незначимы (при равенстве любой пары индексов), либо заданы на p срезах, где $p = \overline {1,t - 1} $, либо равны симметричным ячейкам в данном срезе.

Проиллюстрируем описанное свойство кубической матрицы смежности на примере.

Пример 3. Пусть дан $H_{6}^{3} = H_{6}^{3}(U,E)$, где U – множество из шести вершин, а множество гиперребер $E = \{ \{ {{u}_{1}},\;{{u}_{2}},\;{{u}_{3}}\} $, $\{ {{u}_{1}},\;{{u}_{2}},\;{{u}_{4}}\} $, $\{ {{u}_{1}},\;{{u}_{2}},\;{{u}_{5}}\} $, $\{ {{u}_{1}},\;{{u}_{2}},\;{{u}_{6}}\} $, $\{ {{u}_{1}},\;{{u}_{3}},\;{{u}_{4}}\} $, $\{ {{u}_{1}},\;{{u}_{3}},\;{{u}_{5}}\} $, $\{ {{u}_{1}},\;{{u}_{4}},\;{{u}_{5}}\} $, $\{ {{u}_{2}},\;{{u}_{3}},\;{{u}_{4}}\} $, $\{ {{u}_{2}},\;{{u}_{3}},\;{{u}_{5}}\} $, $\{ {{u}_{2}},\;{{u}_{4}},\;{{u}_{5}}\} $, $\{ {{u}_{3}},\;{{u}_{4}},\;{{u}_{5}}\} \} $. Его матрицу смежности $X_{6}^{3} = X_{6}^{3}(H_{6}^{3})$ можно представить в виде срезов (рис. 4), где темно-серым фоном без чисел показаны незначимые области матрицы, светло-серым фоном с числами обозначаются определенные ранее ячейки, курсивом – значения заданные симметрией текущего среза, а полужирным шрифтом – значения, которые определены на текущем срезе.

Определение 9. Областью определения t-среза кубической матрицы смежности однородного гиперграфа будем называть набор значений ${{x}_{{ijk}}}$, где $i = t$, $j = \overline {t + 1,n - 1} $ и $k = \overline {j + 1,n} $.

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

Определение 10. Областью определения кубической матрицы смежности однородного гиперграфа будем называть набор значений совокупности областей определения t-срезов, где $t = \overline {1,n - 2} $.

Если представить кубическую матрицу смежности в виде куба, состоящего из n × n × n единичных кубов, то область определения матрицы представляет собой усеченную ступенчатую призму (рис. 5).

Теперь перейдем к экстремальным 3-однородным гиперграфам ($EU{{H}^{3}}$). Здесь, как и в $EU{{H}^{2}}$, домены нулей и единиц отделены друг от друга. Под этим мы понимаем, что в области определения матрицы смежности $EU{{H}^{3}}$ $\forall {{x}_{{ijk}}} = 1$ не существует ${{x}_{{pqt}}} = 0$ при $i \geqslant p$, $j \geqslant q$, $k \geqslant t$ и $\forall {{x}_{{ijk}}} = 0$ не существует ${{x}_{{pqt}}} = 1$ при $i \leqslant p$, $j \leqslant q$, $k \leqslant t$. Следовательно, каждый из срезов матрицы смежности можно представить в виде сигнатуры. Однако так как область определения каждого из срезов сужается, то и сигнатуры для каждого из них состоят из меньшего количества бит.

Определение 11. Сигнатурой второго порядка (или вектором сигнатур) экстремального 3‑однородного гиперграфа на $n$ вершинах ($H_{n}^{3}$) будем называть ${{\sigma }^{2}}(H_{n}^{3}) = ({{\sigma }_{1}}, \ldots ,{{\sigma }_{{n - 2}}})$, где σ_i – сигнатура области определения i-среза кубической матрицы смежности $X_{n}^{3} = X_{n}^{3}(H_{n}^{3})$.

Пример 4. Воспользуемся гиперграфом из примера 3. Его матрица смежности представлена на рис. 4. Нетрудно убедиться, что данный гиперграф является экстремальным, так как его множество гиперребер $E$ имеет две максимальные тройки вершин $\{ {{u}_{1}},\;{{u}_{2}},\;{{u}_{6}}\} $ и $\{ {{u}_{3}},\;{{u}_{4}},\;{{u}_{5}}\} $, которые в свою очередь образуют базу $\mathcal{B} = \{ \{ 1,\;2,\;6\} ,\{ 3,\;4,\;5\} \} $ [21].

Для наглядности отобразим только области определения срезов и границы их доменов нулей и единиц. Последняя будет отображена сплошной линией. Стоит напомнить, что сигнатура определяется как двоичное число, кодирующее границу между доменами по следующему принципу: если граница идет вниз, то ей соответствует 1, а если влево, то – 0. Границу проходим справа налево и сверху вниз. Разряды в сигнатуре заполняем от старшего к младшему. На рис. 6 представлены области определения, границы и их сигнатуры в двоичном виде. Конечный вид сигнатуры второго порядка для рассматриваемого $H_{6}^{3}$: ${{\sigma }^{2}}{{ = (1011}_{2}}{{,011}_{2}}{{,01}_{2}}{{,0}_{2}}) = (11,3,1,0)$.

Для такого объекта как сигнатура второго порядка можно оценить объем памяти, необходимый для ее хранения. Так как сигнатура второго порядка представляет собой вектор сигнатур, первая из которых имеет размер, равный n – 2 бита, а каждая следующая на 1 бит меньше, то общий объем памяти, занимаемый сигнатурой второго порядка $EUH_{n}^{3}$, равен $\frac{1}{2}(n - 1)(n - 2) = C_{{n - 1}}^{2}$ – числу сочетаний из n – 1 по 2 бита. Так как для хранения единого значения чаще используется целое число байт, то объем памяти вектора сигнатур можно оценить как $\left\lceil {\frac{1}{8}C_{{n - 2}}^{2}} \right\rceil $ байт (здесь $\left\lceil x \right\rceil $ – ближайшее целое большее x).

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

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

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

Рассмотрим соседние срезы в кубической матрице смежности. Не теряя общности, можем рассмотреть первый и второй срезы и их сигнатуры. Пусть сигнатура σ₁ отождествляет некоторою междоменную границу ${{b}_{1}}$ 1-среза, а сигнатура σ₂ – границу ${{b}_{2}}$ 2-среза. Сигнатура σ₂ на один разряд меньше, чем σ₁, а длина границы ${{b}_{2}}$ на один сегмент короче, чем граница ${{b}_{1}}$.

Для дальнейшей работы нам необходимо сравнять сигнатуры по длине. Для этого введем операцию усечения сигнатуры.

Определение 12. Усеченной сигнатурой $\hat {\sigma }$ называется сигнатура, полученная из σ путем последовательного выполнения двух операций. Пусть $n$ – количество разрядов в σ, а p – номер старшего разряда сигнатуры, равного единице, тогда

Отметим, что усеченная сигнатура имеет на один разряд меньше, чем в $\sigma $.

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

Замечание 2. Если сигнатура $\sigma = 0$ и имеет больше одного разряда, то $\hat {\sigma } = 0$.

Замечание 3. Если сигнатура $\sigma $ имеет один разряд, то $\hat {\sigma }$ не существует.

Вернемся к нашим сигнатурам 1-среза и 2-среза. Пусть мы нашли ${{\hat {\sigma }}_{1}}$, тогда ей соответвует граница ${{\hat {b}}_{1}}$. Если представить обе границы наложенными на одну плоскость, согласно их координатам, то для выполнения ограничения по доменам единиц и нулей необходимо, чтобы граница b₂ проходила на всех своих участках не дальше от начала координат, чем ${{\hat {b}}_{1}}$. Аналитически это можно описать следующим образом: количество спусков в границе b₂ не должно превосходить количество спусков границы ${{\hat {b}}_{2}}$ на протяжении всей длины ${{b}_{2}}$.

Перейдем к определению данного ограничения в терминах сигнатур. Для этого необходимо найти отношение сравнения для сигнатур.

Определение 13. При условии равенства длин сигнатур будем говорить, что ${{\sigma }_{1}} \leqslant {{\sigma }_{2}}$, если

где $i = \overline {1,n} $. При этом ${{\sigma }_{1}} = {{\sigma }_{2}}$, только если их значения равны.

Теперь введем отношение включения сигнатуры.

Определение 14. Пусть даны сигнатуры ${{\sigma }_{1}}$ и ${{\sigma }_{2}}$. Будем говорить, что сигнатура ${{\sigma }_{2}}$ включена в ${{\sigma }_{1}}$ (${{\sigma }_{2}} \subset {{\sigma }_{1}}$), если ${{\sigma }_{2}} \leqslant {{\hat {\sigma }}_{1}}$.

Пример 5. Проиллюстрируем отношения включения, которые представлены в табл. 1.

Из отношения включения можно вывести следующую теорему.

Теорема. Пусть дан произвольный набор сигнатур ${{\tilde {\sigma }}^{2}} = ({{\sigma }_{1}}, \ldots ,{{\sigma }_{n}})$. Данный набор образует сигнатуру второго порядка экстремального 3-однородного гиперграфа построенного на $n - 2$ вершинах тогда и только тогда, когда ${{\sigma }_{{i + 1}}} \subset {{\sigma }_{i}}$, где $i = \overline {1,n - 1} $.

Доказательство. Предположим, что существует такая пара сигнатур, что , но при этом ${{\tilde {\sigma }}^{2}}$ является сигнатурой второго порядка, т.е. существует такой $EUH_{{n - 2}}^{3}$, что его матрица смежности может быть представлена в виде срезов соответствующих набору сигнатур. Из предположения следует: нельзя сказать, что ${{\sigma }_{{k + 1}}}\; \leqslant {{\hat {\sigma }}_{k}}$. Это возможно в следующих случаях:

1) ${\text{len}}{\kern 1pt} {{\sigma }_{k}} - {\text{len}}{\kern 1pt} {{\sigma }_{{k + 1}}} \ne 1$ ( см. определение 7) – области определения k-среза и k + 1-среза также различаются болee чем на одну строку, что невозможно по определению среза матрицы смежности;

2) ${{\sigma }_{k}} \ne {{\sigma }_{{k + 1}}}$ и ${{\sigma }_{k}} \leqslant {{\sigma }_{{k + 1}}}$ – это приведет к противоречию с экстремальностью однородного гиперграфа, так как найдется такое значение ${{x}_{{k + 1\;pq}}} = 1$, что ${{x}_{{kpq}}} = 0$, что нарушает правило разделения доменов единиц и нулей;

3) отношение сравнения между ${{\sigma }_{k}}$ и ${{\sigma }_{{k + 1}}}$ определить нельзя – мы получим две границы, которые пересекают друг друга, т.е. не находятся в упорядоченном состоянии, что, как и в предыдущем случае, приводит к нарушению правила разделения доменов нулей и единиц.

Мы пришли к противоречию, таким образом данное предположение неверно.

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

Однако, несмотря на однозначность соответствия между ${{\sigma }^{2}}$ и $EU{{H}^{3}}$, вопрос экономии памяти при хранении собственно сигнатуры второго порядка в памяти еще открыт. Одним из решений представляется введение сокращения каждой сигнатуры в наборе до размера своих значащих разрядов.

Замечание 4. усть даны сигнатуры ${{\sigma }_{1}}$ и ${{\sigma }_{2}}$. Если ${{\sigma }_{2}} \subset {{\sigma }_{1}}$, то количество значащих разрядов в ${{\sigma }_{2}}$ не может быть больше, чем p + 1, где p – номер старшего ненулевого разряда в ${{\hat {\sigma }}_{1}}$.

Действительно, так как ${{\sigma }_{2}} \leqslant {{\hat {\sigma }}_{1}}$, то старший ненулевой разряд второй сигнатуры не может иметь номер больший, чем старший ненулевой разряд усеченной сигнатуры предыдущего среза.

Отсюда можно вывести определение сжатой сигнатуры второго порядка.

Определение 15. Пусть ${{\sigma }_{1}}$ – первая сигнатура из ${{\sigma }^{2}}$ и ${\text{len}}{\kern 1pt} {{\sigma }_{1}} = n - 2$. Тогда без потери однозначности можно для ${{\sigma }_{2}}$ зарезервировать $p + 1$ бит, где p – номер старшего ненулевого разряда ${{\hat {\sigma }}_{1}}$. Обозначим такую сжатую сигнатуру как ${{\bar {\sigma }}_{2}}$. Если ${{\hat {\sigma }}_{k}} = 0$ или не существует, но ${{\hat {\sigma }}_{{k - 1}}} \ne 0$, то сжатая сигнатура второго порядка ${{\bar {\sigma }}^{2}} = ({{\sigma }_{1}},{{\bar {\sigma }}_{2}}, \ldots ,{{\bar {\sigma }}_{k}})$.

Так как объем памяти, зарезервированный для ${{\bar {\sigma }}^{2}}$, зависит от σ², то точная оценка не возможна. Минимальный объем, занимаемый ${{\bar {\sigma }}^{2}}$, равен $n - 2$ бита, если $EU{{H}^{3}}$ является вполне несвязным. Максимальный объем ${{\bar {\sigma }}^{2}}$ равен объему σ², если $EU{{H}^{3}}$ – полный или почти полный – без одного ребра, соединяющего три максимальных по номеру вершины. В этом случае ${{\sigma }_{i}}$ представляют собой двоичные числа вида $\underbrace {1 \ldots 1}_{n - 1 - i}$, где $i = \overline {1,n - 3} $.

4. Связь векторов степеней вершин и сигнатур. Сначала объясним алгоритм нахождения вектора степеней вершин по сигнатуре, а после дадим его формальное определение.

Пример 6. Пусть дана сигнатура $\sigma {{ = 37}_{{10}}}{{ = 100101}_{2}}$. Здесь для наглядности сигнатура представлена в десятичной и двоичной системах счисления. Так как нам не дано количество вершин соответствующего $EU{{H}^{2}}$ ${{H}^{2}}$, то считаем ${\text{len}}{\kern 1pt} \sigma = 6$, что определяет наличие в H² связной компоненты из семи вершин и некоторого количества изолированных вершин. Не теряя смысла, допускаем, что изолированных вершин в H² нет, хотя на алгоритм это предположение не оказывает серьезного влияния.

Построим матрицу смежности ${{X}^{2}} = {{X}^{2}}(\sigma ) = {{X}^{2}}({{H}^{2}})$. Так как сигнатура есть двоичное описание границы разделения доменов единиц и нулей, то сделать это достаточно просто [23]. Ставим начало границы в правом верхнем углу матрицы. Идем по двоичному представлению сигнатуры справа налево. Если встречаем 1, то ведем границу вниз, иначе – влево. После последнего действия граница коснется одной из ячеек главной диагонали. Слева и сверху от границы находятся единицы, а справа и снизу – нули. Результат можно видеть на рис. 6.

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

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

Для простоты подсчета установим две переменные $t = 6$ и $b = 0$, отвечающие за подсчет степени вершины по строке и по столбцу соответственно. При встрече 1 в сигнатуре увеличиваем b, а при встрече 0 – уменьшаем t. Также нам понадобится два номера вершин $s = 1$ и $e = 7$, для которых сохраняем текущие степени вершины. При встрече 1 в сигнатуре устанавливаем ${{a}_{s}} = t$ и увеличиваем s, а при 0 – устанавливаем ${{a}_{e}} = b$ и уменьшаем e.

Итак, ${{\sigma }_{{(5)}}} = 1$, следовательно, ${{a}_{1}} = 6$, $s = 2$, $b = 1$. Далее ${{\sigma }_{{(4)}}} = 0 \Rightarrow {{a}_{7}} = 1$, $e = 6$, $t = 5$. Следующий разряд также равен 0, т.е. ${{a}_{6}} = 1$, $e = 5$, $t = 4$. Второй разряд равен 1, что приводит к нахождению второй координаты: ${{a}_{2}} = 4$, $s = 3$, $b = 2$. Далее ${{\sigma }_{{(1)}}} = 0 \Rightarrow {{a}_{5}} = 2$, $e = 4$, $t = 3$. И, наконец, самый правый разряд равен 1: ${{a}_{3}} = 3$, $s = 4$, $b = 3$.

Анализ сигнатуры завершился, но мы не нашли координаты с номером 4. Однако этот номер хранит и e, и s. А значение хранится в переменных b или t, поэтому не важно какое значение мы возьмем. В результате получим вектор ${\mathbf{A}}({{H}^{2}}) = (6,4,3,3,2,1,1)$.

Теперь формально опишем процесс построения вектора степеней вершин по сигнатуре.

Алгоритм 1. Построение вектора степеней вершин по сигнатуре экстремального 2-однородного гиперграфа H².

Входные данные: $\sigma $ – сигнатура (целое неотрицательное число), $n$ – количество вершин в H².

Локальные переменные: $s = 1$, $e = n$ – индексы координат вектора A; $b = 0$ и $t = n - 1$ – временные значения; $i = n - 2$ – счетчик, указывающий на текущий разряд сигнатуры.

Выходные данные: $A = ({{a}_{i}})$ – $n$-координатный вектор степеней вершин H².

Шаг 1. Если ${\text{len}}{\kern 1pt} \sigma \geqslant n$, то построить вектор степеней вершин по данной сигнатуре невозможно.

Шаг 2. Если ${\text{len}}{\kern 1pt} \sigma < n - 1$, то устанавливаем ${\text{len}}{\kern 1pt} \sigma = n - 1$ с требуемым количеством нулевых старших разрядов.

Шаг 3. Если ${{\sigma }_{{(i)}}} = 1$, то переходим к шагу 4, иначе переходим к шагу 5.

Шаг 4. Устанавливаем ${{a}_{s}} = t$, $s = s + 1$, $b = b + 1$. Переходим к шагу 6.

Шаг 5. Устанавливаем ${{a}_{e}} = b$, $e = e - 1$, $t = t - 1$. Переходим к шагу 6.

Шаг 6. Устанавливаем $i = i - 1$.

Шаг 7. Если $i \geqslant 0$, то переходим к шагу 3.

Шаг 8. Устанавливаем ${{a}_{s}} = b$.

Шаг 9. Вектор степеней вершин готов.

Замечание 5. Легко видеть что алгоритм 1 имеет логарифмическую сложность относительно размера сигнатуры или линейную – относительно количества координат в искомом векторе.

Проиллюстрируем работу алгоритма 1 таблицей значений сигнатур и соответствующих им векторов степеней (табл. 2).

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

Алгоритм 2. Построение сигнатуры первого порядка из вектора степеней вершин $n$-вершинного $EUH_{n}^{2}$.

Входные данные: $A = ({{a}_{i}})$ – вектор степеней вершин $EUH_{n}^{2}$ ${{H}^{2}}$, $n$ – количество координат вектора A.

Локальные переменные: $p = n - 1$ – номер индекса сигнатуры; $t = n - 1$ – временное значение; i = 1 – индекс координаты вектора A.

Выходные данные: $\sigma $ – сигнатура (целое неотрицательное число).

Шаг 1. Если ${{a}_{i}} < t$, то переходим к шагу 2, иначе переходим к шагу 3.

Шаг 2. Установим $t = t - 1$. Переходим к шагу 4.

Шаг 3. Установим ${{\sigma }_{{(p)}}} = 1$ и $i = i + 1$. Переходим к шагу 4.

Шаг 4. Установим $p = p - 1$.

Шаг 5. Если p > 0, то переходим к шагу 1.

Шаг 6. Сигнатура построена.

Замечание 6. Аналогично замечанию 5 сложность алгоритма линейная или логарифмическая в зависимости от отношения к начальным данным.

5. Взаимосвязь вектора степеней вершин с сигнатурой второго порядка. Принцип построения вектора с сигнатурой второго порядка сложнее, чем с сигнатурой первого порядка. Так как каждый срез определяет не только свои значения, но и значения следующих срезов. Следовательно, строить вектор будем, согласно накопительной схеме: строим вектор, соответствующий первой координате вектора сигнатур, его координаты суммируются и делятся пополам для сохранения первой координаты вектора. Остальные координаты сохраняются как промежуточные. На следующем шаге подобным образом находим вторую координату и добавляем ее к уже имеющейся временной. Остальные координаты добавляем к накопленным. Повторяем, пока не переберем все координаты вектора сигнатур. Таким образом вектор степеней вершин будет построен.

Теперь рассмотрим данный алгоритм с точки зрения формального описания.

Алгоритм 3. Построения вектора степеней вершин ${\mathbf{A}}$ $EUH_{n}^{3}$ из сигнатуры второго порядка.

Входные данные: ${{\sigma }^{2}} = ({{\sigma }_{1}}, \ldots ,{{\sigma }_{{n - 1}}})$ – сигнатура второго порядка (вектор сигнатур), $n$ – количество вершин в H³.

Локальные переменные: B – временный вектор для отдельной координаты сигнатуры второго порядка;  j – индекс для переноса координат временного вектора в накопительный; i = 1 – счетчик, указывающий на текущую координату вектора сигнатуры.

Выходные данные: ${\mathbf{A}} = ({{a}_{i}})$ – $n$-координатный вектор степеней вершин H².

Шаг 1. Установим ${\mathbf{A}} = (0,...,0)$.

Шаг 2. Если ${{\sigma }_{i}} = 0$, то переходим к шагу 11.

Шаг 3. С помощью алгоритма 1 получаем вектор ${\mathbf{B}}({{\sigma }_{i}})$.

Шаг 4. Установим ${{a}_{i}} = {{a}_{i}} + \frac{1}{2}\sum\nolimits_j {{b}_{j}}$.

Шаг 5. Установим $j = 1$.

Шаг 6. Установим ${{a}_{{j + i}}} = {{a}_{{j + i}}} + {{b}_{j}}$.

Шаг 7. Увеличим $j = j + 1$.

Шаг 8. Если $j + i \leqslant n$, то переходим на шаг 6.

Шаг 9. Увеличим $i = i + 1$.

Шаг 10. Если $i < n - 1$, то переходим на шаг 2.

Шаг 11. Вектор степеней вершин A получен.

Также проиллюстрируем разработанный алгоритм табл. 3. Здесь в первом столбце приведены все сигнатуры второго порядка в векторном виде, а во втором – соответствующие векторы степеней вершин $EUH_{6}^{3}$ .

Теперь представим обратный алгоритм преобразования из вектора степеней вершин в сигнатуру второго порядка. Данный алгоритм базируется на свойстве разделения доменов нулей и единиц. Основная идея состоит в том, что первая координата должна быть задействована со второй координатой и с остальными. После этого проводится усечение в векторе первой и второй координаты на n – 2, а других – на 1, при этом ${{\sigma }_{1}}_{{(n - 2)}} = 1$. Если от первой координаты вектора что-то осталось, то повторяем операцию, только выбираем третью координату к первой в пару. Если получится связать первую, третью и последнюю координаты снова, то следующий разряд первой координаты вектора сигнатуры также устанавливается в единицу, иначе устанавливаем разряд в ноль и пытаемся связать первую, третью и предпоследнюю координаты и т.д., пока ${{a}_{1}}$ не станет равной нулю. В этом случае остальные разряды ${{\sigma }_{1}}$ будут нулями, и найдем полностью определенную первую компоненту сигнатуры второго порядка.

Получив в процессе усеченный вектор A₁ без первой координаты, передаем его для нахождения ${{\sigma }_{2}}$ тем же образом, что и ${{\sigma }_{1}}$. Если на k-м этапе вектор ${{{\mathbf{A}}}_{k}} = (0, \ldots ,0)$, то ${{\sigma }_{p}}$ = 0, $\forall p = \overline {k + 1,n - 2} $.

Перейдем к формальному описанию алгоритма.

Алгоритм 4. Построение сигнатуры второго порядка из вектора степеней вершин A $EUH_{n}^{3}$ .

Входные данные: ${{A}_{0}} = ({{a}_{i}})$ – вектор степеней вершин $EUH_{n}^{3}$ ${{H}^{3}}$; $n$ – размерность вектора A.

Локальные переменные: p – номер старшего разряда сигнатуры; $t = n - 2$ – временное значение; i = 0 – индекс координаты вектора A; $j$ – вспомогательный счетчик.

Выходные данные: ${{\sigma }^{2}} = ({{\sigma }_{1}}, \ldots ,{{\sigma }_{{n - 2}}})$ – сигнатура (целое неотрицательное число).

Шаг 1. Увеличим $i = i + 1$.

Шаг 2. Присвоим ${{{\mathbf{A}}}_{i}} = {{{\mathbf{A}}}_{{i - 1}}}$.

Шаг 3. Если ${{{\mathbf{A}}}_{i}} = (0, \ldots ,0)$, то переходим к шагу 11.

Шаг 4. Присвоим $p = n - 2 - i$.

Шаг 5. Установим $j = i + 1$ и $t = n - j$.

Шаг 6. Если ${{a}_{i}} \geqslant t$ и ${{a}_{j}} \geqslant t$ и ${{a}_{{j + t}}} > 0$, то переходим к шагу 7, иначе переходим к шагу 10.

Шаг 7. Уменьшим ${{{\mathbf{A}}}_{i}}$: ${{a}_{i}} = {{a}_{i}} - t$, ${{a}_{j}} = {{a}_{j}} - t$, ${{a}_{k}} = {{a}_{k}} - 1$ для $k = \overline {j + 1,j + t} $.

Шаг 8. Установим ${{\sigma }_{i}}_{{(p)}} = 1$. Уменьшим $p = p - 1$.

Шаг 9. Если ${{a}_{i}} = 0$, то переходим к шагу 1, иначе перейдем к шагу 5.

Шаг 10. Уменьшим $t = t - 1$ и $p = p - 1$. Перейдем к шагу 6.

Шаг 11. Сигнатура второго порядка σ² получена.

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

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

Также крайне полезной представляется возможность перечисления векторов степеней своих вершин экстремальных 2-однородных гиперграфов, так как позволит рассмотреть механизмы образования таких векторов. Кроме того, быстрый алгоритм преобразования между сигнатурой и вектором степеней вершин завершает цикл алгоритмов преобразования между всеми характеристиками $EUH_{n}^{2}$: сигнатурой, базой, матрицей смежности и вектором степеней вершин.

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