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

Введение. Гиперграфы начиная с XXI в. активно применяются для анализа сетей [1, 2], признаков и характеристик принадлежности (таких, как теги, свойства, необязательные параметры) [3]. Графы и гиперграфы широко используются как в современных фундаментальных исследованиях, так и при решении практических задач. Однако большинство алгоритмов на гиперграфах оперирует специальными классами гиперграфов [4]. Характер ограничений, накладываемых на данные классы, позволяет точнее описывать модели анализируемых данных.

При этом нужно учитывать, что сами гиперграфы суть аморфные структуры, имеющие слабые общие черты, что привело к построению класса однородных гиперграфов. Это дает возможность применять некий общий аппарат при их исследовании. Данную структуру независимо друг от друга начали разрабатывать как топологи [5], так и исследователи в области обобщения теории графов [6–13]. Большое количество статей по раскраскам гиперграфов показывает актуальность фундаментальных исследований. С другой стороны, имеется широкий спектр работ, связанный с однородными гиперграфами [14–21], где показывается их применимость в разделах управления сетями и базами данных, шифровании и моделировании.

Главными ключевыми задачами в области комбинаторной топологии и теории гиперграфов всегда были вопросы подсчета. Здесь стоит упомянуть как давние основополагающие работы, например [22, 23], так и современные [24–26]. Сложные методы подсчета зачастую опираются на специфические структуры-представления графов и гиперграфов, которые позволяют взглянуть на них с иной стороны [27, 28].

В статье продолжается исследование базы – структуры, описанной в [28], а именно расширяется понятие базы на k-мерный случай с построением операции объединения двух баз и реализации алгоритма подсчета баз.

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

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

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

В различных отраслях математики частные случаи данных объектов встречаются под иными именами: для k = 2 данная конструкция соответсвует ненаправленному графу, не имеющему петель. В топологии данные структуры именуются комплексами с размерностью k – 1 [5, 28].

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

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

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

Теперь воспользуемся данным опеределением в задании особого экстремального класса UH.

Определение 3. Однородный гиперграф $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 $.

В дальнейшем экстремальный ${\text{UH}}_{n}^{k}$ будем обозначать через ${\text{EUH}}_{n}^{k}$.

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

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

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

Теперь построим конструкцию, позволяющую алгебраическим способом описать экстремальный ${\text{EUH}}_{n}^{k}$. Для ${{H}^{k}} = ({{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}}) = {{H}^{k}}({{V}_{n}},E)$ положим $I_{n}^{k}({{H}^{k}}) = \left\{ {({{i}_{1}}, \ldots ,{{i}_{k}}) \in I_{n}^{k}:{{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}} = 1} \right\}$ = = $\{ ({{i}_{1}}, \ldots ,{{i}_{k}}) \in I_{n}^{k}:\{ {{u}_{{{{i}_{j}}}}}:1 \leqslant j \leqslant k\} \in E\} $.

Определение 4. Пусть ${{H}^{k}} = ({{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}}) = {{H}^{k}}({{V}_{n}},E)$ – не пустой ${\text{EUH}}_{n}^{k}$ $\left( {E \ne \emptyset } \right)$. Подмножество индексов $\overline I _{n}^{k}({{H}^{k}}) = \left\{ {({{i}_{1}}, \ldots ,{{i}_{k}})} \right\}$ из $I_{n}^{k}$ называется базой для ${\text{EUH}}_{n}^{k}$, если выполняются следующие условия:

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

б) для $\forall ({{i}_{1}}, \ldots ,{{i}_{k}}) \in I_{n}^{k}({{H}^{k}})$, где , существует такой $({{m}_{1}}, \ldots ,{{m}_{k}}) \in \overline I _{n}^{k}({{H}^{k}})$, что $({{i}_{1}}, \ldots ,{{i}_{k}}) < ({{m}_{1}}, \ldots ,{{m}_{k}})$.

Рассмотрим на следующем примере базу.

Пример 1. Пусть дан $H_{7}^{4} = {{H}^{4}}\left( {{{V}_{7}},E)} \right)$, где множество гиперребер $S = \{ \{ {{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}}\} \} $. Следовательно, $\overline I _{7}^{4}({{H}^{4}}) = \left\{ {(1,2,3,7)} \right\}$.

Теперь зададим понятие максимального подмножества индексов.

Определение 5. Подмножество индексов $({{m}_{1}}, \ldots ,{{m}_{k}})$ из $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}})$.

Это определение означает следующее: для каждой тройки из $I_{n}^{k}({{H}^{k}})$ существует максимальная тройка из этого же множества.

Теорема 1. Любой ${\text{EU}}{{{\text{H}}}_{{}}}$ ${{H}^{k}} = {{H}^{k}}\left( {{{V}_{n}},E} \right) = ({{x}_{{{{i}_{1}} \ldots {{i}_{k}}}}})$ имеет единственную базу и эта база есть $\overline I _{n}^{k}({{H}^{k}})$.

Доказательство данной теоремы для 3-мерного случая приведено в [28]. Оно легко расширяется на k-мерный случай.

Теперь можно ввести принцип построения базы на основе максимального подмножества.

Теорема 2. Пусть $\widetilde I_{n}^{k} = \{ ({{i}_{1}}, \ldots ,{{i}_{k}}) \in I_{n}^{k}:$ любые пары различных подмножеств индексов не связаны отношением порядка из $I_{n}^{k}\} $. Данное множество подмножеств является максимальным. Тогда $\widetilde I_{n}^{k}$ – база некоторого ${\text{EUH}}_{n}^{k}$.

Пример 2. Пусть $\overline I _{8}^{4}({{H}^{4}}) = \left\{ {(1,2,5,7),(2,3,5,6)} \right\}$ – база некоторого экстремального 4-однородного гиперграфа $H_{8}^{4} = {{H}^{4}}\left( {{{V}_{8}},E} \right)$. Тогда $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}}\} $, $\{ {{v}_{1}},{{v}_{2}},{{v}_{4}},{{v}_{6}}\} $, $\{ {{v}_{1}},{{v}_{2}},{{v}_{4}},{{v}_{7}}\} $, $\{ {{v}_{1}},{{v}_{2}},{{v}_{5}},{{v}_{6}}\} $, $\{ {{v}_{1}},{{v}_{2}},{{v}_{5}},{{v}_{7}}\} $, $\{ {{v}_{1}},{{v}_{3}},{{v}_{4}},{{v}_{5}}\} $, $\{ {{v}_{1}},{{v}_{3}},{{v}_{4}},{{v}_{6}}\} $, $\{ {{v}_{1}},{{v}_{3}},{{v}_{5}},{{v}_{6}}\} $, $\{ {{v}_{2}},{{v}_{3}},{{v}_{4}},{{v}_{5}}\} $, $\{ {{v}_{2}},{{v}_{3}},{{v}_{4}},{{v}_{6}}\} $, $\{ {{v}_{2}},{{v}_{3}},{{v}_{5}},{{v}_{6}}\} \} $.

Из теорем 1 и 2 вытекает следующая теорема.

Теорема 3. Однородный гиперграф $H_{n}^{k}$ является экстремальным тогда и только тогда, когда H^k имеет базу.

Доказательство последних теорем очевидно и не вызывает затруднений.

Пример 3. Пусть $n = 5$ и ${{\tilde {I}}_{5}} = \{ (1,2,5),\,\,(2,3,4)\} $. Легко видеть, что 2-комплекс $H_{5}^{3} = {{H}^{3}}({{V}_{5}},E)$, где $E = \{ \{ {{v}_{1}},{{v}_{2}},{{v}_{3}}\} $, $\{ {{v}_{1}},{{v}_{2}},{{v}_{4}}\} $, $\{ {{v}_{1}},{{v}_{2}},{{v}_{5}}\} $, $\{ {{v}_{1}},{{v}_{3}},{{v}_{4}}\} $, $\{ {{v}_{1}},{{v}_{3}},{{v}_{5}}\} $, $\{ {{v}_{1}},{{v}_{4}},{{v}_{5}}\} $, $\{ {{v}_{2}},{{v}_{3}},{{v}_{4}})\} $ задается базой ${{\widetilde I}_{5}}$.

3. Объединение баз. Базу можно задать также через границу, разделяющую домены D₁ и D₀.

Рассмотрим матрицу смежности, которая представляет собой k-мерный куб, касающийся начала координат внешним углом ячейки с минимальнми индексами. Оси координат соответствуют росту индексов, и без потери общности можно считать, что порядок осей такой же, как порядок индексов матрицы. Границу можно представить в виде множества точек, каждая из которых имеет локальные минимум или максимум расстояния до начала координат. При этом нужно понимать, что такая поверхность имеет ряд линий симметрии, каждая из которых делит поверхность пополам. Нас интересует область, в которой ${{i}_{1}} < {{i}_{2}} < \ldots < {{i}_{{k - 1}}} < {{i}_{k}}$.

С учетом вышесказанного граница между доменами является k-мерной поверхностью, которая представляет собой объединение внешней границы (по отношению к началу координат) множества k-мерных параллелепипедов. Главная диагональ каждого параллелепипеда соединяет начало координат и один из локальных максимумов расстояния от границы до начала координат. Точки максимумов в интересующей нас области с упорядоченными значениями координат описываются подмножествами индексов, образующих элементы базы. Если базу представить такой $k$-мерной поверхностью, то легко понять, что будут означать операции объединения и пересечения баз.

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

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

Первым рассмотрим вспомогательный алгоритм поиска места в списке, для добавления нового элемента базы.

Алгоритм 1. Поиск места для вставки элемента.

Входные данные: отсортированный в лексикографическом порядке список $A$ подмножеств индексов, каждое из которых имеет длину k и последний элемент которого не превосходит $n$; $q$ – количество элементов в списке $A$; $b$ – подмножество индексов того же типа, что входят в $A$; $p,j$ – счетчики, равные нулю.

Выходные данные: t – позиция в списке $A{\kern 1pt} '$, куда будет нужно вставить элемент b.

Шаг 1. Увеличиваем $j$ на 1.

Шаг 2. Если $j = q$, то переходим к шагу 4.

Шаг 3. Если ${{A}_{j}} < = b$ в лексикографическом смысле, то переходим к шагу 1, иначе переходим к шагу 4.

Шаг 4. Устанавливаем $t$, равным j.

Шаг 5. Завершаем алгоритм.

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

Алгоритм 2. Объединение базы с одним элементом.

Входные данные: отсортированный в лексикографическом порядке список $A$ подмножеств индексов, каждое из которых имеет длину k и последний элемент которого не превосходит $n$; $b$ – подмножество индексов того же типа, что входят в $A$; $q$ – количество элементов в списке $A$; $p,j$ – счетчики, равные 0; $t$ – позиция в списке $A{\kern 1pt} '$, куда будет нужно вставить элемент b.

Выходные данные: список $A{\kern 1pt} '$ подмножеств индексов, каждое из которых имеет длину k.

Шаг 1. Устанавливаем t как результат работы алгоритма 1 с параметрами A и b.

Шаг 2. Добавляем в список $A{\kern 1pt} '$ элементы ${{A}_{i}}$, где $i = \overline {1,t - 1} $.

Шаг 3. Добавляем в список $A{\kern 1pt} '$ элемент b.

Шаг 4. Добавляем в список $A{\kern 1pt} '$ элементы ${{A}_{i}}$, где $i = \overline {t,q} $.

Шаг 5. Увеличиваем $q$ на 1.

Шаг 6. Увеличиваем $p$ на 1.

Шаг 7. Если $p = t$, то переходим к шагу 12.

Шаг 8. Если ${{A}_{p}}_{i} < = {{b}_{i}}$ $\forall i$, то удаляем p-й элемент из $A{\kern 1pt} '$, иначе переходим к шагу 6.

Шаг 9. Уменьшаем t на 1.

Шаг 10. Уменьшаем q на 1.

Шаг 11. Переходим к шагу 8.

Шаг 12. Увеличиваем p на 1.

Шаг 13. Если $p > q$, то перейти к шагу 15.

Шаг 14. Если ${{A}_{p}}_{i} > = {{b}_{i}}$ $\forall i$, то удаляем $t$-й элемент из $A{\kern 1pt} '$, иначе переходим к шагу 6.

Шаг 15. Возвращаем $A{\kern 1pt} '$.

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

Алгоритм 3. Объединение двух баз, представленных в виде списков подмножеств.

Входные данные: отсортированные в лексикографическом порядке списки A и B подмножеств индексов, каждое из которых имеет длину k и последний элемент которого не превосходит $n$; ${{q}_{1}}$ и ${{q}_{2}}$ – количество элементов в списках A и B соответственно; $j$ – счетчик, равный 0.

Выходные данные: список $A{\kern 1pt} '$ подмножеств индексов, каждое из которых имеет длину k.

Шаг 1. Устанавливаем $A{\kern 1pt} ' = A$.

Шаг 2. Увеличиваем $j$ на 1.

Шаг 3. Если $j > {{q}_{2}}$, то завершаем алгоритм.

Шаг 4. Устанавливаем $A{\kern 1pt} '$, равным результату алгоритма 2 с параметрами A, ${{B}_{j}}$, ${{q}_{1}}$.

Результатом работы алгоритма 3 будет база-объединение баз A и B.

4. Мощность множества ${\text{EUH}}_{n}^{k}$. Отдельный интерес представлет собой оценка мощности множества всех экстремальных k-однородных гиперграфов. Интерес в данной области связан с разработкой новых алгоритмов шифрования данных, построенных на топологических принципах, в частности на связях вершин внутри ключевого экстремального гиперграфа [15–17], так как чем быстрее растет мощность множества, тем более устойчивым является ключ при простом переборе.

Через $\mathfrak{A}_{n}^{k}$ обозначим множество всех экстремальных k-однородных гиперграфов на множестве вершин ${{V}_{n}}$, через $\mathfrak{B}_{n}^{k}(p)$ – множество баз ${\text{EUH}}_{n}^{k}$, состоящих из p элементов, а через $B_{n}^{k}(p)$ – мошность множества $\mathfrak{B}_{n}^{k}(p)$, т.е. $B_{n}^{k}(p) = {\text{|}}\mathfrak{B}_{n}^{k}(p){\text{|}}$. Запишем также сумму всех $B_{n}^{k}(p)$:

Известно, что $\mathcal{B}_{n}^{2}{{ = 2}^{{n - 1}}}$. Для определения мощности множества $\mathfrak{A}_{n}^{k}$ был предложен следующий путь.

Так как каждой базе соответствует свой ${\text{EUH}}_{n}^{k}$, то была написана программа на языке Си, которая при заданном n создавала все возможные тройки индексов ($1 \leqslant i,j,k, \leqslant n$). Таким образом задавались все базы, состоящие из одной тройки. Эти данные являются начальными для следующего рекурсивного алгоритма.

Алгоритм 4. Подсчет $B_{n}^{k}(p)$.

Входные данные: $A$ – список баз; deep – уровень глубины рекурсии (изначально глубина равна 1); p – номер.

Переменные: subsets – массив подмножеств из k индексов; ckn – число сочетаний из $n$ по $k$; $j$ – счетчик (равен p); $new$ – список подмножеств индексов (сначала пустой).

Шаг 1. Увеличиваем  j на 1.

Шаг 2. Для каждой пары $i$ и  j-й элемент из subsets, где $i > j$, с помощью алгоритма 2 получаем список $A{\kern 1pt} '$.

Шаг 3. Если длина списка $A{\kern 1pt} '$ больше $deep$, то прибавляем количество найденых элементов к $B_{n}^{k}(deep)$ и вызываем текущий алгоритм c параметрами A, $deep + 1$,  j.

Шаг 4. Если $j > ckn$, то завершаем алгоритм.

По завершению всей программы получаем значения $B_{n}^{k}(p)$.

Замечание. усть – округление числа a до ближайшего целого большего a. Тогда:

1) для $k = 2$ $p \leqslant \left\lceil {n{\text{/}}2} \right\rceil $,

2) для $k = 3$ $p \leqslant \left\lceil {n(n - 2){\text{/}}8} \right\rceil $.

Часть из полученных $B_{n}^{k}(p)$ для случая $k = 3$ представлена в табл. 1 и 2, а для k = 4 – в табл. 3. Верхняя строчка задает $n$, а левый столбец – p. В последней строке приведены $B_{n}^{k}$ – общее количество баз на $n$ вершинах.

Отметим, что время расчета растет быстрее экспоненты и при $n = 17$ составляет более 100 ч на 4-ядерном процессоре с частотой 3.0 GHz. Вследствие этого особый интерес представляет аналитический вид $B_{n}^{k}(p)$.

Нам известно, что $B_{n}^{3}(1) = C_{n}^{3}$ (исходя из способа задания начальных данных). Отсюда возникло предположение, что $B_{n}^{k}(p)$ – полиномиальная функция. Для подтверждения его был применен метод конечных разностей для сеточной функции. Одним из применений данного метода является нахождение полинома, проходящего через точки сеточной функции (при его существовании). Собственно для этого он и будет использован. Далее кратко опишем его.

Для значений $x:{{x}_{0}},{{x}_{0}} + h,{{x}_{0}} + 2h, \ldots ,{{x}_{0}} + nh$ нам известны значения функции f(x) : ${{y}_{0}},{{y}_{1}},{{y}_{2}}, \ldots ,{{y}_{n}}$.

Тогда ${{y}_{{i + 1}}} - {{y}_{i}} = \Delta {{y}_{i}}$ – конечные разности первого порядка, $\Delta {{y}_{{i + 1}}} - \Delta {{y}_{i}} = {{\Delta }^{2}}{{y}_{i}}$ – конечные разности второго порядка, ${{\Delta }^{i}}$ – конечная разность i-го порядка.

Пусть задана сеточная функция для $B_{n}^{3}(2)$. Ее значения представлены в табл. 4.

Так как ${{\Delta }^{i}} \ne 0$ при $i = \overline {1,6} $ и равны 0 при больших i, то ищем $B_{n}^{3}(2)$ в виде многочлена шестого порядка.

На основе этой сеточной функции была построена система из семи линейных уравнений следующего вида:

Здесь в качесте неизвестных выступают коэффициенты многочлена.

Решив систему (4.1), получаем

На основе уравнения (4.2) можно заметить, что количество баз связано с числом сочетаний. Это можно объяснить тем, что два элемента базы используют шесть индексов, что предполагает связь количества индексов в одном элементе (три) и количество элементов в базе (два). Кроме того, количество элементов в выборке (n + 1) связано с тем, что при n = 5 уже существует база из двух элементов, это требует существования соответствующего числа сочетаний. Однако легко убедиться, что $B_{n}^{3}(3) \ne C_{{n + 3}}^{9}$. Следовательно, предполагаем наличие более сложной конфигурации для данного значения.

В целом на основе вышесказанного можно выдвинуть следующую гипотезу.

Гипотеза 1. Значения $B_{n}^{3}(p)$ имеют вид

где $t$ – целочисленная функция, равная разнице между $3p$ и мощностью наименьшего множества вершин, на котором впервые встречается база из $p$ элементов; $x$ – неизвестное целое число, ограничивающее количество слагаемых в формуле (определяется эмпирически).

Для нахождения ${{a}_{i}}$ был разработан специальный алгоритм 5.

Алгоритм 5. Нахождение коэффициентов ${{a}_{i}}$ из формулы (4.3).

Входные данные: b – массив найденных значений для $B_{n}^{3}(p)$.

Шаг 1. ${{a}_{0}} = {{b}_{0}}$.

Шаг 2. ${{a}_{1}} = {{b}_{1}} - {{a}_{0}}C_{{n + t(n,p) + 1}}^{{3p}}$.

Шаг 3. ${{a}_{2}} = {{b}_{2}} - {{a}_{0}}C_{{n + t(n,p) + 2}}^{{3p}} - {{a}_{1}}C_{{n + t(n,p) + 1}}^{{3p}}$ и т.д., пока ${{a}_{i}} \ne 0$.

С помощью данного алгоритма были найдены следующие формулы для $B_{n}^{3}(p)$:

Эти выражения не противоречат гипотезе и, скорее, подтверждают ее.

Кроме того алгоритм 5 можно завершать, если данные при нужном количестве вершин еще не найдены, что позволяет получить коэффициенты не для всех слагаемых формул, но для нескольких начальных. Здесь представлены обнаруженные значения для случая p > 7:

Полученные результаты позволяют обобщить гипотезу на общий случай.

Гипотеза 2. Значения $B_{n}^{k}(p)$ имеют следующий вид:

где $t$ – целочисленная функция, равная разнице между kp и мощностью наименьшего множества вершин, на котором впервые встречается база из $p$ элементов; x – неизвестное целое число, ограничивающее количество слагаемых в формуле (определяется эмпирически).

Для k = 4 поиск аналитических формул затруднен в связи с недостатком найденных экспериментальных значений. Однако для $p < 4$ коэффициенты были найдены:

Это также подтверждает справедливость предлагаемой гипотезы.

Заключение. Согласно результатам исследования, получено описание общего принципа объединения баз ${\text{EUH}}_{n}^{k}$, а также алгоритм объединения для конкретного представления базы в виде множества подмножеств. Были сделаны оценки, связанные с задачей перечисления ${\text{EUH}}_{n}^{3}$: найден общий вид для $\mathcal{B}_{n}^{3}(p)$, получены конкретные формулы для случаев $1 \leqslant p \leqslant 7$; эмпирически определена верхняя оценка максимальной размерности базы в зависимости от количества вершин ${\text{EUH}}_{n}^{3}$. Важным итогом работы является предлагаемая гипотеза аналитического вида формул для $B_{n}^{k}(p)$, которой не противоречат проведенные расчеты некоторых формул.

При продолжении исследования в данной области предполагается подтвердить гипотезу и найти аналитические формулы для $B_{n}^{k}(p)$ и общую формулу для $\mathcal{B}_{n}^{k}(p)$, в том числе для k > 3.