Известия РАН. Теория и системы управления, 2021, № 6, стр. 52-60

Введение. В теории графов важное место занимают вопросы оценки мощности множества графов, обладающих определенными характеристиками. В разное время эти вопросы исследовались в работах [1–5]. Оценка мощности множества графов определенных классов важна не только в рамках теоретической, но и в практической области. Например, дерево легко хранить с помощью алгоритма Прюфера [6] в виде определенной последовательности. Данный механизм подходит, например, для генерации случайных деревьев, а также случайных графов общего вида путем объединения набора случайных деревьев.

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

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

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

Определение 1. Гиперграф $H = H(V,E) = H({{V}_{n}},E)$ – совокупность множества из $n$ вершин ${{V}_{n}}$ и множества непустых подмножеств множества вершин E [7], 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 комплексы [13]. Этот термин пришел из топологии [10].

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

Особый интерес для исследования представляют экстремальные UH. Пусть ${{\mathbb{Z}}_{ + }}$ – множество неотрицательных целых чисел и n – количество координат вектора A. Введем следующие обозначения: $\mathbb{Z}_{ + }^{n}$ = {A = (a₁, …, a_n) : a_i ∈ ${{\mathbb{Z}}_{ + }}\,\,\forall i$} – множество неотрицательных n-координатных векторов и $\bar {\mathbb{Z}}_{ + }^{n}$ = {A ∈ $\mathbb{Z}_{ + }^{n}$ : a_i ≥ a_{i + 1}, $\forall i$, i = $\overline {1,n - 1} $} – множество неотрицательных n-координатных векторов с упорядоченными по невозрастанию координатами.

Определение 3. Реализацией вектора A ∈ $\mathbb{Z}_{ + }^{n}$ в k-однородный гиперграф H = $H = H({\mathbf{A}}) = H(V,E)$ называется такой гиперграф, что вектор степеней его вершин есть вектор A.

Пусть вектор A из $\mathbb{Z}_{ + }^{n}$ есть реализуемый в k-однородный гиперграф вектор и ${{\Gamma }^{k}} = \{ H({\mathbf{A}})\} $ – множество всех реализаций (с множеством вершин V_n).

Определение 4. Вектор A из $\mathbb{Z}_{ + }^{n}$, где n ≥ 2, называется k-совершенным, если ${\text{|}}{{\Gamma }^{k}}{\text{|}} = 1$. При этом единственная реализация H(A) обозначается k-совершенным однородным гиперграфом.

Для определения экстремальности вектора (и гиперграфа) удобно перейти к вектору, координаты которого упорядочены по невозрастанию.

Определение 5. Вектор A из $\bar {\mathbb{Z}}_{ + }^{n}$, где n ≥ 2, называется k-экстремальным, если A – k-совершенный вектор. Единственная реализация H(A) будет экстремальным k-однородным гиперграфом ($EUH_{n}^{k}$).

Определение 6. Множество всех $EUH_{n}^{k}$ обозначим как $\mathfrak{A}_{n}^{k}$.

Основное преимущество использования экстремальных гиперграфов состоит в том, что между множеством k-экстремальных векторов и множеством экстремальных k-однородных гиперграфов установлено взаимно-однозначное соответствие. Кроме того, существуют быстрые редукционные алгоритмы восстановления k-экстремальных векторов в k-однородный гиперграф при k = 2 [14], k = 3 [13] и частично для произвольного k [15]. При этом $EUH_{n}^{k}$ – база [8] экстремального k-однородного гиперграфа.

Пусть n, $k \in \mathbb{Z}$, k ≥ 2. Для множества индексов ${{I}_{n}} = \{ i \in \mathbb{Z}:i = \overline {1,n} \} $ (номеров) введем обозначение k-индексных упорядоченных подмножеств множества I_n: $I_{n}^{k} = {\text{\{ }}({{i}_{1}}, \ldots {{i}_{k}}):{{i}_{j}} = \overline {1,n} ,{{i}_{j}} < {{i}_{{j + 1}}}\forall j{\text{\} }}$. Определим на $I_{n}^{k}$ частичный порядок: положим $({{i}_{j}}:j = \overline {1,k} )$ ≥ $({{m}_{j}}:j = \overline {1,k} )$, если ${{i}_{j}} \geqslant {{m}_{j}}$ $\forall j$, и $({{i}_{j}}:j = \overline {1,k} ) > ({{m}_{j}}:j = \overline {1,k} )$ при $({{i}_{j}}:j = \overline {1,k} )$ ≥ $({{m}_{j}}:j = \overline {1,k} )$ и $({{i}_{j}}:j = \overline {1,k} ) \ne ({{m}_{j}}:j = \overline {1,k} )$.

Построим конструкцию, позволяющую алгебраическим способом описать $EU{{H}^{k}}$. Для $UH_{n}^{k} = {{H}^{k}}\left( {{{V}_{n}},E} \right)$ и ${{X}^{k}}({{H}^{k}}) = ({{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}})$ зададим $\hat {I}_{n}^{k}({{H}^{k}})$ = $\{ ({{i}_{1}}, \ldots ,{{i}_{k}}) \in I_{n}^{k}:{{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}} = 1\} $ = {(i₁, ..., i_k) ∈ ∈ $I_{n}^{k}:{\text{\{ }}{{{v}}_{{{{i}_{j}}}}}:j = \overline {1,k} {\text{\} }} \in E{\text{\} }}$.

Определение 7. Пусть ${{H}^{k}}\left( {{{V}_{n}},E} \right)$ – непустой экстремальный k-однородный гиперграф $(E \ne \emptyset )$, а ${{X}^{k}}({{H}^{k}}) = ({{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}})$ – его матрица смежности. Подмножество индексов $\bar {I}_{n}^{k}({{H}^{k}})$ = {(i₁, ..., i_k)} из $I_{n}^{k}$ называется базой для комплекса H^k, если выполняются следующие условия:

– для разных элементов $({{i}_{1}}, \ldots ,{{i}_{k}})$ и $({{m}_{1}}, \ldots ,{{m}_{k}})$ из $\bar {I}_{n}^{k}({{H}^{k}})$ отношение порядка в $I_{n}^{k}({{H}^{k}})$ не определено;

– для $\forall ({{i}_{1}}, \ldots ,{{i}_{k}}) \in I_{n}^{k}({{H}^{k}}){{\backslash }}\bar {I}_{n}^{k}({{H}^{k}})$ имеется такой $({{m}_{1}}, \ldots ,{{m}_{k}}) \in \bar {I}_{n}^{k}({{H}^{k}})$, что существует отношение частичного порядка: $({{i}_{1}}, \ldots ,{{i}_{k}}) < ({{m}_{1}}, \ldots ,{{m}_{k}})$.

Определение 8. Подмножество индексов $({{m}_{1}}, \ldots ,{{m}_{k}})$ из $\hat {I}_{n}^{k}({{H}^{k}})$ (т.е. ${{x}_{{{{m}_{1}} \ldots {{m}_{k}}}}} = 1$) называется максимальным, если ${{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}} = 0$, $\forall ({{i}_{1}}, \ldots ,{{i}_{k}}) > ({{m}_{1}}, \ldots ,{{m}_{k}})$.

Теорема 1. Теорема состоит из четырех частей.

1. База содержит все максимальные подмножества индексов.

2. Любой экстремальный $UH_{n}^{k} = {{H}^{k}}\left( {{{V}_{n}},E} \right)$ имеет единственную базу.

3. Пусть $\tilde {I}_{n}^{k} = \{ ({{i}_{1}}, \ldots ,{{i}_{k}}) \in I_{n}^{k}\} $ и между элементами $\tilde {I}_{n}^{k}$ отсутствует отношение частичного порядка. Тогда $\tilde {I}_{n}^{k}$ – база некоторого экстремального k-однородного гиперграфа.

4. $UH_{n}^{k}$ является экстремальным тогда и только тогда, когда имеет базу.

Доказательство данной теоремы представлено в [8].

Рассмотрим на примере то, как база соответствует вектору степеней вершин $EUH_{n}^{k}$.

Пример 1. Возьмем 4-экстремальный вектор ${\mathbf{A}} = (5,5,4,2,2,1,1)$. Построим его единственную реализацию ${{H}^{4}} = {{H}^{4}}\left( {{{V}_{7}},E} \right) = {{H}^{4}}({\mathbf{A}})$, где множество гиперребер E = {$\{ {{{v}}_{1}},{{{v}}_{2}},{{{v}}_{3}},{{{v}}_{4}}\} ,\{ {{{v}}_{1}},{{{v}}_{2}},{{{v}}_{3}},{{{v}}_{5}}\} $, $\{ {{{v}}_{1}},{{{v}}_{2}},{{{v}}_{3}},{{{v}}_{6}}\} ,\{ {{{v}}_{1}},{{{v}}_{2}},{{{v}}_{3}},{{{v}}_{7}}\} ,\{ {{{v}}_{1}},{{{v}}_{2}},{{{v}}_{4}},{{{v}}_{5}}\} {\text{\} }}$. Следовательно, $\bar {I}_{7}^{4}({{H}^{4}}) = \left\{ {(1,2,3,7),(1,2,4,5)} \right\}$.

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

Пример 2. Пусть дана база $B = \left\{ {(2,9),(4,7)} \right\}$. Матрица смежности для нее представлена в табл. 1. На матрице смежности пунктиром выделены элементы базы.

Отдельно стоит обозначить множество баз k-экстремальных однородных гиперграфов на n вершинах как ${{\mathfrak{B}}^{k}}(n)$.

2. Мощность множества 2-экстремальных однородных гиперграфов. В данном разделе рассматриваются вопросы перечисления экстремальных графов. Экстремальный граф – это частный случай $EUH_{n}^{k}$ для k = 2. В [14] упоминалось, что ${\text{|}}\mathfrak{A}_{n}^{2}{\text{|}} = {{2}^{{n - 1}}}$. Доказательство данного факта опиралось на свойства экстремальных векторов и ограничения на их координаты. Рассмотрим другой способ доказательства данной теоремы – через базы.

Теорема 2. Мощность множества экстремальных графов, построенных на n вершинах, равна ${{2}^{{n - 1}}}$.

Доказательство. Так как множество баз однозначно соответствует множеству ${{\mathfrak{A}}_{n}}$, то найдем ${\text{|}}{{\mathfrak{B}}^{2}}(N){\text{|}}$. Базы могут состоять из нескольких элементов. Так как между элементами базы отсутствует отношение частичного порядка [8], то при $n$ вершинах количество элементов в базе не превосходит n/2. Это легко увидеть, если предположить, что первый элемент базы равен (1, n), второй – $(2,n - 1)$, а $i$ – $(i,n - i)$ при i ≤ n/2. Если количество вершин четно, то последним в данной цепочке будет элемент $(n{\text{/}}2,n{\text{/}}2 + 1)$. В обратном случае последний элемент в цепочке может принимать три варианта: $((n - 1){\text{/}}2,(n - 1){\text{/}}2 + 1)$, $((n - 1){\text{/}}2,(n - 1){\text{/}}2 + 2)$ и $((n - 1){\text{/}}2 + 1,(n - 1){\text{/}}2 + 2)$.

Обозначим через $\mathfrak{B}_{i}^{2}(n) = {{\mathfrak{B}}_{i}}(n)$ множество баз экстремальных графов на $n$ вершинах, при этом каждая базa состоит из i элементов.

Теперь нужно найти $\left| {{{\mathfrak{B}}^{2}}(n)} \right|$. Так как множество баз можно разложить на непересекающиеся множества, то справедливо следующее утверждение:

Легко заметить, что $\left| {{{\mathfrak{B}}_{0}}(n)} \right| = 1$, так как база, в которой нет элементов описывает вполне несвязный граф, т.е. граф без ребер. Для множества ${{\mathfrak{B}}_{1}}(n)$ также легко найти мощность. Так как единственный элемент базы состоит из двух различных чисел, упорядоченных по возрастанию, то их количество равно числу сочетаний из n по 2, т.е. $C_{n}^{2}$.

Аналогично можно найти $\left| {{{\mathfrak{B}}_{2}}(n)} \right|$. Пусть база состоит из двух элементов (x, y) и (t, s), то, не нарушая общности, мы можем предположить, что $x < t$ и $y > s$. Это связано с тем, что между элементами базы не может быть установлено отношение частичного порядка. Соответственно, задача формулируется так: сколько комбинаций можно получить из четырех чисел $1 < x < t < s < y \leqslant n$? Ответом является $C_{N}^{4}$. Продолжая рассмотрения частных случаев, придем к следующему выражению:

Используя значения (2.2), преобразуем формулу (2.1):

Выражение (2.3) можно упростить, если воспользоваться правилом суммирования чисел сочетаний: $C_{n}^{k} = C_{{n - 1}}^{k} + C_{{n - 1}}^{{k - 1}}$. Тогда из (2.3) вытекает следующее:

Благодаря замене $2i = p$ и известному свойству бинома Ньютона

представляем (2.4) в следующей форме:

Таким образом доказано, что $\left| {\mathfrak{A}_{n}^{2}} \right| = {{2}^{{n - 1}}}$.

3. Сигнатура экстремального 2-однородного гиперграфа. Обозначим множество целых неотрицательных чисел меньше t как ${{\mathbb{Z}}_{t}}$. Тогда исходя из теоремы 2 мы могли бы установить взаимооднозначное соответствие между множеством ${{\mathbb{Z}}_{{{{2}^{{n - 1}}}}}}$ и множеством $\mathfrak{A}_{n}^{2}$. Это позволяет определить понятие сигнатуры экстремального графа и сигнатурной характеристики множества экстремальных графов.

Определение 9. Назовем n-битное неотрицательное число $x \in {{\mathbb{Z}}_{{{{2}^{{n - 1}}}}}}$, однозначно характеризующее экстремальный граф по описанному далее алгоритму 1, сигнатурой соответствующего ему экстремального графа, а множество ${{\mathbb{Z}}_{{{{2}^{{n - 1}}}}}}$ – сигнатурной характеристикой множества $\mathfrak{A}_{n}^{2}$.

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

Алгоритм 1. Восстановление матрицы смежности $n$-вершинного экстремального графа по сигнатуре.

Входные данные: x – сигнатура (целое неотрицательное число), $n$ – количество вершин в экстремальном графе.

Локальные переменные: индексы $0 \leqslant i,j,k \leqslant n$.

Выходные данные: $M = ({{m}_{{pq}}})$ – матрица смежности результирующего экстремального графа.

Шаг 1. Если $x \geqslant {{2}^{{n - 1}}}$, то построить экстремальный граф на данном множестве вершин по указанному числу невозможно.

Шаг 2. Установим i = 0, $j = n$ и $k = n - 2$, а также ${{m}_{{pq}}} = 0$, $\forall p,q = \overline {1,n} $.

Шаг 3. Если k-й бит числа равен 0, то увеличиваем j на 1 и переходим к шагу 5.

Шаг 4. Увеличиваем i на 1, устанавливаем ${{m}_{{pq}}}$ и ${{m}_{{qp}}} = 1$, где $p = i$, а $q = \overline {i + 1,j} $.

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

Шаг 6. Матрица смежности экстремального графа получена.

Суть алгоритма состоит в анализе сигнатуры, представленной в двоичном виде. Начинаем перебирать разряды числа от большего к меньшему. Если разряд равен 1, то сдвигаемся по узлам матрице вниз, иначе — влево. Построенная граница разделяет домены единиц и нулей в результирующей матрице смежности.

Замечание. Перечисление битов можно проводить в двух направлениях от n – 1 к 1 и наоборот. В первом случае (алгоритм 1) при подаче на вход одной и той же сигнатуры x и разных n (n₁ и n₂) результирующие графы будут отличаться только наличием дополнительных изолированных вершин. Их количество равно $\left| {{{n}_{1}} - {{n}_{2}}} \right|$.

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

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

Рассмотрим действие алгоритма 1 на примере.

Пример 3. Пусть на вход подается $x = 201$ и $n = 10$. Сначала проверим, что при данных значениях граф существует: $x = 201 < {{2}^{{10 - 1}}} = 512$. Теперь можно перейти к непосредственному построению матрицы, но сначала представим x в двоичном виде: $x = {{011001001}_{2}}$. Здесь x начинается с 0, так как количество бит должно быть равно n – 1. Дальнейший процесс построения приведем в виде табл. 2 со строками: k, значение k-го бита (x_k), i и j.

Результирующая матрица M (табл. 3) представлена и содержит траекторию, которую можно построить, если поставить начальную точку в правый верхний угол правой верхней ячейки матрицы, и сдвигать точку, согласно правилам алгоритма 1. Как видно, построенная ломанная отделяет домен единиц от домена нулей, что является одним из критериев экстремальности графа. Также данная ломаная всегда упирается в ячейки главной диагонали, которые в случае экстремального графа всегда имеют нулевые и не значимы.

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

Алгоритм 2. Нахождение сигнатуры по матрице смежности n-вершинного экстремального графа.

Входные данные: $M = ({{m}_{{pq}}})$ – матрица смежности $n$ вершинного экстремального графа.

Локальные переменные: индексы $0 \leqslant i,j,k \leqslant n$.

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

Шаг 1. Установим i = 1, $j = n$, $k = n - 2$ и x = 0.

Шаг 2. Если ${{m}_{{ij}}} = 0$, то уменьшаем j на 1 и переходим к шагу 4.

Шаг 3. Увеличиваем i на 1, устанавливаем k-й бит числа x в 1.

Шаг 4. Уменьшаем k на 1. Если $k > 0$, то перейдем к шагу 2.

Шаг 5. Текущее значение $x$ – искомая сигнатура.

Суть данного алгоритма состоит в поиске границы единичного домена матрицы смежности: идем с конца строки влево пока не найдем единицу, потом вниз пока не найдем ноль. Пока ищем ноль, устанавливаем соответствующие биты в числе. Повторяем, пока не дойдем до главной диагонали. Рассмотрим работу алгоритма 2 на примере.

Пример 4. Пусть дана матрица смежности M размерности 7 × 7 (табл. 4).

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

Так как базы являются эффективным средством представления экстремальных графов, то желательно установить соответствие между множествами ${{\mathfrak{B}}^{2}}(n)$ и ${{\mathbb{Z}}_{{{{2}^{{n - 1}}}}}}$. Таким образом можно упорядочить множество баз и упростить манипулирование ими. Для этого приведем алгоритм построения базы на основе сигнатуры.

Алгоритм 3. Восстановление базы $n$-вершинного экстремального графа по сигнатуре.

Входные данные: x – сигнатура (целое неотрицательное число), $n$ – количество вершин в соответствующем экстремальном графе.

Локальные переменные: индексы $0 \leqslant i,j,k \leqslant n$.

Выходные данные: $B = {\text{\{ }}{{b}_{t}}{\text{\} }}$ – база из t-элементов, соответствующая экстремальному графу.

Шаг 1. Если $x \geqslant {{2}^{{n - 1}}}$, то построить экстремальный граф (и соответственно его базу) на данном множестве вершин по указанной сигнатуре – невозможно.

Шаг 2. Установим i = 0, $j = n$ и $k = n - 3$.

Шаг 3. Если k-й бит числа равен 1, то увеличиваем i на 1 и переходим к шагу 6.

Шаг 4. Если k – 1-й бит равен 1, то добавляем к $B$ элемент (i, j).

Шаг 5. Уменьшаем  j на 1.

Шаг 6. Если $k > 0$, то уменьшаем k на 1 и переходим к шагу 3.

Шаг 7. Если нулевой бит сигнатуры равен 1, то добавляем в $B$ элемент (i, j).

Шаг 8. База экстремального графа получена.

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

Пример 5. Пусть сигнатура $x = 332$ и n = 10. Найдем базу соответствующего сигнатуре графа.

Для нахождения базы сначала переведем сигнатуру в двоичный вид: $x = {{101001100}_{2}}$. Теперь постепенно будем проходить по разрядам и определять координаты базы. Для этого покажем траекторию движения точки из верхнего правого угла по правилам алгоритма 3. Траекторию и элементы базы можно увидеть в табл. 6, а процесс вычислений покажем в виде табл. 7. Здесь траектория завершается достигнув верхнего правого угла ячейки (5, 5), а элементами базы являются пары индексов (1, 10), (2, 9) и (4, 7). Таким образом база по сигнатуре построена.

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

Алгоритм 4. Нахождение сигнатуры по базе n-вершинного экстремального графа.

Входные данные: $B = ({{b}_{t}})$ – база экстремального графа, $n$ – количество вершин в графе, $t$ – количество элементов в базе.

Локальные переменные: индексы $0 \leqslant i,j,k,p \leqslant n$.

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

Шаг 1. Отсортируем элементы базы по возрастанию первого элемента.

Шаг 2. Установим $i = 1$, $j = n$, $k = n - 2$, $p = 0$ и x = 0.

Шаг 3. Если $p = t$, то переходим к шагу 8, иначе увеличиваем p на 1.

Шаг 4. Если ${{b}_{{{{p}_{2}}}}} < j$, то уменьшаем j на 1 и переходим к шагу 8.

Шаг 5. Увеличиваем i на 1, устанавливаем k-й бит числа $x$ в 1.

Шаг 6. Уменьшаем k на 1.

Шаг 7. Если $i > {{b}_{{{{p}_{1}}}}}$, то перейдем к шагу 3, иначе перейдем к шагу 4.

Шаг 8. Полученное значение x – искомая сигнатура.

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

Продемонстрируем работу данного алгоритма на примере.

Пример 6. Пусть дана база $B = {\text{\{ }}(2,8),(3,5){\text{\} }}$ для 10-вершинного графа. Найдем для нее сигнатуру.

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

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

эффективный метод хранения экстремальных графов в виде $n$-битного числа;

применение сигнатуры в качестве ключа при шифровании, основанном на топологической структуре экстремальных графов, на текущий момент в качестве ключа используется n-координатный вектор степеней вершин экстремального графа;

выполнение операций объединения и пересечения над сигнатурами, а не над матрицами смежности графов, что позволит снизить сложность операции с $O({{n}^{2}})$ до $O(n)$, где n – количество вершин графа (сейчас разработаны алгоритмы частичного упрощения булевых операций через векторы степеней вершин);

сигнатура предполагается к использованию в алгоритме нахождения ${\text{|}}\mathfrak{A}_{n}^{3}{\text{|}}$ и общего случая ${\text{|}}\mathfrak{A}_{n}^{k}{\text{|}}$.