1
УДК 519.179.1
Редукционные методы восстановления некоторого
класса гиперграфов
А.А. Гурченков
1
, Д.С. Костяной
2
, А.В. Мокряков
2
1
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
2
МАТИ — РГТУ им. К.Э. Циолковского, Москва, 121552, Россия
Рассмотрены методы получения некоторых классов гиперграфов из заданного
вектора. Для каждого из классов представлен алгоритм построения гиперграфа
из произвольного вектора. В случае невозможности построения алгоритм уста-
навливает, насколько следует уменьшить вектор, чтобы гиперграф можно было
реализовать. В планарных графах между двумя точками проводится дуга. Если
пространство имеет размерность на единицу больше, то уже через три точки
проводится плоскость и в качестве гиперребра выступает треугольник.
Ключевые слова:
гиперграфы, реализуемость вектора, k-комплексы.
Введение.
Идеи восстановления гиперграфов [1] некоторых классов
из произвольных векторов сформулированы при решении задачи о
распределении ресурсов, представленных в виде векторов [2]. Рас-
смотрим следующие четыре класса гиперграфов:
1
1
( , )
k n
— на
n
вершинах существуют гиперребра только с ве-
сом 1, инцидентные
k
различным вершинам;
1
( , )
k n
— на
n
вершинах существуют гиперребра только с ве-
сом 1, инцидентные
k
вершинам, в том числе гиперребра размерно-
стью меньше
;
k
1
( , )
k n
— на
n
вершинах существуют кратные гиперребра, ин-
цидентные
k
различным вершинам;
( , )
k n
— на
n
вершинах гиперребра содержат любой набор из
k
вершин, т. е. гиперребра размерностью меньше
,
k
которые могут
быть кратными.
С.П. Хакими [3] исследовал вопрос реализуемости вектора в
граф. В работах [4–7] алгоритм Хакими видоизменен таким образом,
что появилась возможность получения не одного, а всех возможных
графов, удовлетворяющих исходному вектору. Однако более слож-
ные модели требуют использования понятия гиперграфа [8]. В ряде
работ [9–11] были исследованы вопросы реализации вектора в двух-
комплекс (гиперграф). Упомянутые работы основаны на результатах,
приведенных в [12–16]. При этом общего алгоритма для
k
-
комплексов не получено. Здесь делается попытка привести варианты
реализации вектора в гиперграф с определенными ограничениями на
его структуру.
