Редукционные методы восстановления некоторого класса гиперграфов
Опубликовано: 14.10.2014
Авторы: Гурченков А.А., Костяной Д.С., Мокряков А.В.
Опубликовано в выпуске: #6(30)/2014
DOI: 10.18698/2308-6033-2014-6-1294
Раздел: Информационные технологии
Рассмотрены методы получения некоторых классов гиперграфов из заданного вектора. Для каждого из классов представлен алгоритм построения гиперграфа из произвольного вектора. В случае невозможности построения алгоритм устанавливает, насколько следует уменьшить вектор, чтобы гиперграф можно было реализовать. В планарных графах между двумя точками проводится дуга. Если пространство имеет размерность на единицу больше, то уже через три точки проводится плоскость и в качестве гиперребра выступает треугольник.
Литература
[1] Зыков А.А. Гиперграфы. УМН, 1972, вып. 6(180), с. 3-7
[2] Костяной Д.С. Модель сбалансированного распределения ресурсов в условиях ограниченности. Научн. тр. Международной конф. "XXXIX Гагаринские чтения". Москва, 2013, с. 69-70
[3] Хакими С.П. О реализуемости множества целых чисел степенями вершин графа. Кибернетика. Москва, 1966, вып. 2, с. 40-53
[4] Миронов А.А. Геометрия точек пространства Rn, реализуемых в граф. УМН, 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
[13] Mironov A.A., Levkina T.A., Tsurkov V.I. Minimax Estimations of Arc Weights in Integer Networks With Fixed Node Degrees. Applied and Computational Mathematics, 2009, vol. 8, no. 2, pp. 216-226
[14] Mironov A.A., Tsurkov V.I. Transport Problems With a Minimax Oriterion. ДАН, 1996, т. 346, № 2, с. 168-171
[15] Mironov A.A., Tsurkov V.I. Minimax under Nonlinear Transportation Constraints. DokladyMathematics, 2001, vol. 64, no. 3, pp. 351-354
[16] Mironov A.A., Tsurkov V.I. Open Тransportation Models with a Minimax Criterion. Doklady Mathematics, 2001, vol. 64, no. 3, pp. 374-377