Редукционные методы восстановления некоторого класса гиперграфов
5
координат вектора
A
по максимально возможному значению
.
p
Каждое такое вычитание означает построение одного гиперребра с
весом
.
p
В конце объединим оставшиеся вершины по принципу
действия второго алгоритма.
Шаг 1.
Используем алгоритм 3.
Шаг 2.
Если полученный вектор не равен нулю, то используем
алгоритм 2.
Заключение.
В работе были определены четыре класса гипергра-
фов на
n
вершинах, которые различаются по типам гиперребер и их
кратности. Для каждого из классов были выбраны наиболее простые,
быстрые и эффективные алгоритмы, позволяющие легко построить
программу, реализующую произвольные векторы в гиперграфы раз-
личных классов. Для первого алгоритма приведен пример реализации
вектора. Не исключено последующее их усовершенствование, так как
не решена проблема однозначности реализации гиперграфа из вектора.
Также не решен вопрос о реализации всех гиперграфов, имеющих один
и тот же вектор степеней вершин.
ЛИТЕРАТУРА
[1]
Зыков А.А. Гиперграфы.
УМН
, 1972, вып. 6(180), с. 3–7.
[2]
Костяной Д.С. Модель сбалансированного распределения ресурсов в
условиях ограниченности.
Научн. тр. Международной конф. «XXXIX
Гагаринские чтения»
. Москва, 2013, с. 69–70.
[3]
Хакими С.П. О реализуемости множества целых чисел степенями вершин
графа.
Кибернетика.
Москва, 1966, вып. 2, с. 40–53.
[4]
Миронов А.А. Геометрия точек пространства
,
n
R
реализуемых в граф.
УМН
, 1977, т. XXII, № 6, с. 231–232.
[5]
Mironov A.A., Tsurkov V.I. Graphical Representation of Multilayered
Hierarchical Structures.
Journal of Computer and Systems Sciences
International
, 1992, vol. 30, no. 5, pp. 114–119.
[6]
Миронов А.А. О реализуемости наборов чисел в граф и свойства графов с
заданным набором степеней вершин. Тр. Гор. ГУ, 1981, с. 76–97.
[7]
Миронов А.А. Равномерные обобщенные графы. ДАН, 1996, т. 351, № 4.
[8]
Мокряков А. В. Представление гиперграфов в виде алгебраической струк-
туры.
Изв. РАН. Теория и системы управления
. Москва, Наука, 2011, т. 5,
с. 53–59.
[9]
Mironov A.A., Mokryakov A.V., Sokolov A.A. About Realization of Integer
Non-Negative Numbers Tuple into 2-Dimensional Complexes.
Applied and
Computational Mathematics
, 2007, vol. 6, no. 1, pp. 58–68.
[10] Миронов А.А., Мокряков А.В. Двумерные комплексы полностью описы-
ваемые степенями вершин. Попкова Ю.С., ред.
Тр. ИСА РАН. Дина-мика
неоднородных систем
, 2006, № 10(1), с. 178–186.
[11] Mokryakov A.V., Tsurkov V. I. Reconstructing 2-Complexes by a Nonnegative
Integer-Valued Vector.
Automation and Remote Control
, 2011, vol. 72. no. 12,
pp. 2541–2552.
[12] Миронов А.А., Цурков В.И. Класс распределительных задач с мини-
максным критерием. ДАН, 1994, вып. 336, № 1, с. 35–38.
