1. На главную
  2. Электронные версии
  3. Известия РАН. Теория и системы управления
  4. № 4, 2023

Известия РАН. Теория и системы управления, 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

Аннотация

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

Список литературы

  1. Зыков А.А. Гиперграфы // УМН. 1974. Т. XXIX. № 6 (180). С. 89–154.

  2. Попков В.К. О моделировании городских транспортных систем гиперсетями // АиТ. 2011. № 6. С. 179–189.

  3. Миков А.И., Миков А.А. Свойства геометрических гиперграфов беспроводных компьютерных сетей // Информатизация и связь. 2020. № 4. С. 60–66. https://doi.org/10.34219/2078-8320-2020-11-4-60-66

  4. Александров П.С. Комбинаторная топология. М.: Гостехтеориздат, 1947. 660 с.

  5. Бобу А.В., Куприянов А.Э., Райгородский А.М. О числе ребер однородного гиперграфа с диапазоном разрешенных пересечением // Проблемы передачи информации. 2017. Т. 53. № 4. С. 16–42.

  6. Балобанов А.Е., Шабанов Д.А. О числе независимых множеств в простых гиперграфах // Математические заметки. 2018. Т. 103. № 1. С. 38–48. https://doi.org/10.4213/mzm11508

  7. Денисов И.О., Шабанов Д.А. О концентрации значений чисел независимости случайных гиперграфов // Дискретная математика. 2021. Т. 33. № 4. С. 32–46. https://doi.org/10.4213/dm1676

  8. Захаров П.А., Шабанов Д.А. О максимальном разрезе в случайном гиперграфе // Доклады Российской академии наук. Математика, информатика, процессы управления. 2021. Т. 501. № 1. С. 26–30. https://doi.org/10.31857/S2686954321060187

  9. Райгородский А.М., Черкашин Д.Д. Экстремальные задачи в раскрасках гиперграфов // УМН. 2020. Т. 75. № 1 (451). С. 95–154. https://doi.org/10.4213/rm9905

  10. Бондаренко В.А., Николаев А.В. Об одном классе гиперграфов и о вершинах релаксаций разрезного многогранника // ДАН. 2012. Т. 442. № 3. С. 300–302.

  11. Егорова Е.К., Мокряков А.В., Суворова А.А., Цурков В.И. Алгоритм передачи многомерных данных с использованием экстремальных однородных гиперграфов // Изв. РАН. ТиСУ. 2021. № 1. С. 73–78.

  12. Каменев А.Р., Ирбитский И.С., Пашковская Е.А. Методы подбора ключа для алгоритмов шифрования на графах // Сб. тез. работ ММНК XLVIII Гагаринские чтения – 2022. М.: Перо, 2022. С. 252.

  13. Лежинский М.В. Концепция топологически-ориентированных хэш-функций // Сб. тез. работ ММНК XLVIII Гагаринские чтения – 2022. М.: Перо, 2022. С. 252.

  14. Mironov A.A. Minimax under Transportation Constraints. Dordrecht: Kluwer Acad. Publ., 1999. 309 p.

  15. Миронов А.А. Равномерные обобщенные графы // ДАН. 1996. Т. 351. № 4. С. 465–468.

  16. Мокрозуб В.Г., Немтинов В.А., Мордвин А.С., Илясов А.А. Применение $n$-ориентированных гиперграфов и реляционных баз данных для структурного и параметрического синтеза технических систем // Прикл. информатика. 2010. № 4 (28). С. 115–122.

  17. Суворова А.А., Берецкий И.С. Алгоритм потокового шифрования на экстремальных k-однородных гиперграфах // Сб. тез. работ ММНК Гагаринские чтения – 2020. М.: МАИ, 2020. С. 510–511.

  18. Корельяно Л.Н., Разборов А.А. Семантические пределы плотных комбинаторных объектов // УМН. 2020. Т. 75. № 4(454). С. 45–152.https://doi.org/10.4213/rm9956

  19. Prüfer H. Neuer Beweis eines Satzes Гjber Permutationen // Arch. Math. Phys. 1918. V. 27. P. 742–744.

  20. Кузьмин О.В., Чернигова А.Г. Автоматизация комбинаторного кодирования и декодирования корневых деревьев // Современные технологии. Системный анализ. Моделирование. 2015. № 1 (45). С. 84–88.

  21. Мокряков А.В. Представление гиперграфов в качестве алгебраической структуры // Изв. РАН. ТиСУ. 2011. № 5. С. 53–59.

  22. Погребной В.К., Погребной А.В. Исследование полиномиальности метода вычисления интегрального описателя структуры графа // Изв. Томск. политехн. ун-та. 2013. Т. 323. № 5. С. 146–151.

  23. Гольцова Т.Ю., Егорова Е.К., Мокряков А.В., Цурков В.И. Сигнатуры экстремальных 2-однородных гиперграфов // Изв. РАН. ТиСУ. 2021. Т. 6. № 6. С. 52–60.

  24. Мокряков А.В., Цурков В.И. Восстановление 2-комплексов по целочисленному неотрицательному вектору // АиТ. 2011. № 12. С. 130–143.

  25. Миронов А.А. Геометрия точек пространства ${{R}^{n}}$, реализуемых в граф // УМН. 1977. Т. XXXII. № 6 (198). С. 232–233.

  26. Костяной Д.С., Мокряков А.В., Цурков В.И. Алгоритмы восстановления гиперграфов по заданному вектору степеней вершин // Изв. РАН. ТиСУ. 2014. № 4. С. 43–48.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Известия РАН. Теория и системы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал