Известия РАН. Теория и системы управления, 2023, № 4, стр. 84-97
СИГНАТУРЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ ЭКСТРЕМАЛЬНЫХ ОДНОРОДНЫХ ГИПЕРГРАФОВ И ИХ СВЯЗЬ С ВЕКТОРАМИ СТЕПЕНЕЙ ВЕРШИН
Т. Ю. Гольцова a, Е. К. Егорова b, c, В. Ю. Леонов c, А. В. Мокряков a, b, *
a РГУ им. А.Н. Косыгина (Технологии. Дизайн. Искусство)
Москва, Россия
b МАИ (национальный исследовательский ун-т)
Москва, Россия
c ФИЦ ИУ РАН
Москва, Россия
* E-mail: MokryakovAlVik@gmail.com
Поступила в редакцию 16.02.2023
После доработки 06.03.2023
Принята к публикации 03.04.2023
- EDN: OCGQCV
- DOI: 10.31857/S0002338823040042
Полные тексты статей выпуска доступны в ознакомительном режиме только авторизованным пользователям.
Аннотация
Матрицы смежности экстремальных 3-однородных гиперграфов занимают существенный объем памяти компьютера. Рассмотрено решение двух задач: предложить эффективный способ представления и хранения таких матриц и найти быстрые алгоритмы, позволяющие оперировать только векторами степеней вершин и сигнатурами (характеристиками матриц смежности), без разворачивания матриц смежности в памяти. В рамках выполнения первой задачи была описана сигнатура второго порядка, задающая однозначно экстремальный 3-однородный гиперграф, без использования его матрицы смежности. Также предложен механизм сжатия сигнатуры второго порядка, что способствует большей эффективности хранения. Для второй задачи был представлен ряд алгоритмов, позволяющих описать взаимоотношения между вектором степеней вершин и сигнатурами как первого, так и второго порядков. Кроме того показано, что произвольная сигнатура второго порядка, построенная с выполнением ряда ограничений, всегда имеет соответствующий ей экстремальный 3-однородный гиперграф.
Полные тексты статей выпуска доступны в ознакомительном режиме только авторизованным пользователям.
Список литературы
Зыков А.А. Гиперграфы // УМН. 1974. Т. XXIX. № 6 (180). С. 89–154.
Попков В.К. О моделировании городских транспортных систем гиперсетями // АиТ. 2011. № 6. С. 179–189.
Миков А.И., Миков А.А. Свойства геометрических гиперграфов беспроводных компьютерных сетей // Информатизация и связь. 2020. № 4. С. 60–66. https://doi.org/10.34219/2078-8320-2020-11-4-60-66
Александров П.С. Комбинаторная топология. М.: Гостехтеориздат, 1947. 660 с.
Бобу А.В., Куприянов А.Э., Райгородский А.М. О числе ребер однородного гиперграфа с диапазоном разрешенных пересечением // Проблемы передачи информации. 2017. Т. 53. № 4. С. 16–42.
Балобанов А.Е., Шабанов Д.А. О числе независимых множеств в простых гиперграфах // Математические заметки. 2018. Т. 103. № 1. С. 38–48. https://doi.org/10.4213/mzm11508
Денисов И.О., Шабанов Д.А. О концентрации значений чисел независимости случайных гиперграфов // Дискретная математика. 2021. Т. 33. № 4. С. 32–46. https://doi.org/10.4213/dm1676
Захаров П.А., Шабанов Д.А. О максимальном разрезе в случайном гиперграфе // Доклады Российской академии наук. Математика, информатика, процессы управления. 2021. Т. 501. № 1. С. 26–30. https://doi.org/10.31857/S2686954321060187
Райгородский А.М., Черкашин Д.Д. Экстремальные задачи в раскрасках гиперграфов // УМН. 2020. Т. 75. № 1 (451). С. 95–154. https://doi.org/10.4213/rm9905
Бондаренко В.А., Николаев А.В. Об одном классе гиперграфов и о вершинах релаксаций разрезного многогранника // ДАН. 2012. Т. 442. № 3. С. 300–302.
Егорова Е.К., Мокряков А.В., Суворова А.А., Цурков В.И. Алгоритм передачи многомерных данных с использованием экстремальных однородных гиперграфов // Изв. РАН. ТиСУ. 2021. № 1. С. 73–78.
Каменев А.Р., Ирбитский И.С., Пашковская Е.А. Методы подбора ключа для алгоритмов шифрования на графах // Сб. тез. работ ММНК XLVIII Гагаринские чтения – 2022. М.: Перо, 2022. С. 252.
Лежинский М.В. Концепция топологически-ориентированных хэш-функций // Сб. тез. работ ММНК XLVIII Гагаринские чтения – 2022. М.: Перо, 2022. С. 252.
Mironov A.A. Minimax under Transportation Constraints. Dordrecht: Kluwer Acad. Publ., 1999. 309 p.
Миронов А.А. Равномерные обобщенные графы // ДАН. 1996. Т. 351. № 4. С. 465–468.
Мокрозуб В.Г., Немтинов В.А., Мордвин А.С., Илясов А.А. Применение $n$-ориентированных гиперграфов и реляционных баз данных для структурного и параметрического синтеза технических систем // Прикл. информатика. 2010. № 4 (28). С. 115–122.
Суворова А.А., Берецкий И.С. Алгоритм потокового шифрования на экстремальных k-однородных гиперграфах // Сб. тез. работ ММНК Гагаринские чтения – 2020. М.: МАИ, 2020. С. 510–511.
Корельяно Л.Н., Разборов А.А. Семантические пределы плотных комбинаторных объектов // УМН. 2020. Т. 75. № 4(454). С. 45–152.https://doi.org/10.4213/rm9956
Prüfer H. Neuer Beweis eines Satzes Гjber Permutationen // Arch. Math. Phys. 1918. V. 27. P. 742–744.
Кузьмин О.В., Чернигова А.Г. Автоматизация комбинаторного кодирования и декодирования корневых деревьев // Современные технологии. Системный анализ. Моделирование. 2015. № 1 (45). С. 84–88.
Мокряков А.В. Представление гиперграфов в качестве алгебраической структуры // Изв. РАН. ТиСУ. 2011. № 5. С. 53–59.
Погребной В.К., Погребной А.В. Исследование полиномиальности метода вычисления интегрального описателя структуры графа // Изв. Томск. политехн. ун-та. 2013. Т. 323. № 5. С. 146–151.
Гольцова Т.Ю., Егорова Е.К., Мокряков А.В., Цурков В.И. Сигнатуры экстремальных 2-однородных гиперграфов // Изв. РАН. ТиСУ. 2021. Т. 6. № 6. С. 52–60.
Мокряков А.В., Цурков В.И. Восстановление 2-комплексов по целочисленному неотрицательному вектору // АиТ. 2011. № 12. С. 130–143.
Миронов А.А. Геометрия точек пространства ${{R}^{n}}$, реализуемых в граф // УМН. 1977. Т. XXXII. № 6 (198). С. 232–233.
Костяной Д.С., Мокряков А.В., Цурков В.И. Алгоритмы восстановления гиперграфов по заданному вектору степеней вершин // Изв. РАН. ТиСУ. 2014. № 4. С. 43–48.
Дополнительные материалы отсутствуют.
Инструменты
Известия РАН. Теория и системы управления