ОБЪЕДИНЕНИЕ БАЗ И ОЦЕНКА МНОЖЕСТВА ЭКСТРЕМАЛЬНЫХ 3-ОДНОРОДНЫХ ГИПЕРГРАФОВ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Основная проблема, связанная с гиперграфами, – это их храненение. Если гиперграф без особенностей, то для его описания часто используются разряженные матрицы. Для работы с k-однородными гиперграфами часто применяют матрицы смежности, однако они занимают большое место в памяти компьютера и в целом храненение k-мерных массивов не очень удобно. Здесь предлагается одно решение для описания и хранения экстремальных k-однородных гиперграфов. Это база – уникальная характеристика экстремального гиперграфа, которая однозначно его описывает. Кроме того, базы можно применять для поиска мощности экстремальных k-однордных гиперграфов. Нами представлены алгоритмы перечисления баз и представлена гипотеза об аналитическом виде формул, описывающих мощность множества экстремальных k-однородных гиперграфов. Для данной задачи используется операция объединения баз, также введенная здесь.

Об авторах

И. С. Берецкий

МАИ (национальный исследовательский ун-т)

Email: MokryakovAlVik@ya.ru
Россия, Москва

Е. К. Егорова

МАИ (национальный исследовательский ун-т); ФИЦ ИУ РАН

Email: MokryakovAlVik@ya.ru
Россия, Москва; Россия, Москва

А. В. Мокряков

МАИ (национальный исследовательский ун-т); РГУ им. А.Н. Косыгина (Технологии. Дизайн. Искусство)

Email: MokryakovAlVik@ya.ru
Россия, Москва; Россия, Москва

В. И. Цурков

ФИЦ ИУ РАН

Автор, ответственный за переписку.
Email: MokryakovAlVik@ya.ru
Россия, Москва

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

  1. Иванов М.В., Калашников И.В., Нуруллаев М.М. Исследование структурных свойств сети интернет на основе метаграфовых моделей // Информатика и автоматизация. 2020. Т. 19. № 4. С. 880–905.
  2. Миков А.И., Миков А.А. Свойства геометрических гиперграфов беспроводных компьютерных сетей // Информатизация и связь. 2020. № 4. С. 60–66. https://doi.org/10.34219/2078-8320-2020-11-4-60-66
  3. Герасименко Е.М., Дышаев Н.Н. Персонализация в фолксономиях в виде гиперграфов на основе кластеризации тегов // Информатика, вычислительная техника и инженерное образование. 2019. № 2 (35). С. 11–15.
  4. Зыков А.А. Гиперграфы // УМН. 1974. Т. XXIX. № 6 (180). С. 89–154.
  5. Александров П.С. Комбинаторная топология. М.: Гостехтеориздат, 1947. 660 с.
  6. Бобу А.В., Куприянов А.Э., Райгородский А.М. О числе ребер однородного гиперграфа с диапазоном разрешенных пересечением // Проблемы передачи информации. 2017. Т. 53. № 4. С. 16–42.
  7. Балобанов А.Е., Шабанов Д.А. О числе независимых множеств в простых гиперграфах // Мат. заметки. 2018. Т. 103. № 1. С. 38–48. https://doi.org/10.4213/mzm11508
  8. Денисов И.О., Шабанов Д.А. О концентрации значений чисел независимости случайных гиперграфов // Дискретная математика. 2021. Т. 33. № 4. С. 32–46. https://doi.org/10.4213/dm1676
  9. Захаров П.А., Шабанов Д.А. О максимальном разрезе в случайном гиперграфе // Доклады Российской академии наук. Математика, информатика, процессы управления. 2021. Т. 501. № 1. С. 26–30. https://doi.org/10.31857/S2686954321060187
  10. Райгородский А.М., Черкашин Д.Д. Экстремальные задачи в раскрасках гиперграфов // УМН. 2020. Т. 75. № 1(451). С. 95–154. https://doi.org/10.4213/rm9905
  11. Ванг Л., Егорова Е.К., Мокряков А.В. Развитие теории гиперграфов // Изв. РАН. ТиСУ. 2018. № 1. С. 111–116.
  12. Миронов А.А. Геометрия точек пространства Rn, реализуемых в граф // УМН. 1977. Т. XXXII. № 6 (198). С. 232–233.
  13. Костяной Д.С., Мокряков А.В., Цурков В.И. Алгоритмы восстановления гиперграфов по заданному вектору степеней вершин // Изв. РАН. ТиСУ. 2014. № 4. С. 43–48.
  14. Бондаренко В.А., Николаев А.В. Об одном классе гиперграфов и о вершинах релаксаций разрезного многогранника // ДАН. 2012. Т. 442. № 3. С. 300–302.
  15. Егорова Е.К., Мокряков А.В., Суворова А.А., Цурков В.И. Алгоритм передачи многомерных данных с использованием экстремальных однородных гиперграфов // Изв. РАН. ТиСУ. 2021. № 1. С. 73–78.
  16. Каменев А.Р., Ирбитский И.С., Пашковская Е.А. Методы подбора ключа для алгоритмов шифрования на графах // Сб. тез. работ ММНК XLVIII Гагаринские чтения – 2022. М.: Перо, 2022. С. 252.
  17. Лежинский М.В. Концепция топологически-ориентированных хэш-функций // Сб. тез. работ ММНК XLVIII Гагаринские чтения – 2022. М.: Перо, 2022. С. 252.
  18. Mironov A.A. Minimax under Transportation Constraints. Dordrecht: Kluwer Acad. Publ., 1999. 309 p.
  19. Миронов А.А. Равномерные обобщенные графы // ДАН. 1996. Т. 351. 4. С. 465–468.
  20. Мокрозуб В.Г., Немтинов В.А., Мордвин А.С., Илясов А.А. Применение n-ориентированных гиперграфов и реляционных баз данных для структурного и параметрического синтеза технических систем // Прикладная информатика. 2010. № 4 (28). С. 115–122.
  21. Суворова А.А., Берецкий И.С. Алгоритм потокового шифрования на экстремальных k-однородных гиперграфах // Сб. тез. работ ММНК Гагаринские чтения – 2020. М.: МАИ, 2020. С. 510–511.
  22. PrГjfer H. Neuer Beweis eines Satzes Гjber Permutationen // Arch. Math. Phys. 1918. V. 27. P. 742–744.
  23. Gilbert E.N. Enumeration of Labelled Graphs // Canad. J. Math. 1956. V. 8. P. 405–411.
  24. Кузьмин О.В., Чернигова А.Г. Автоматизация комбинаторного кодирования и декодирования корневых деревьев // Современные технологии. Системный анализ. Моделирование. 2015. № 1(45). С. 84–88.
  25. Мокряков А.В. Представление гиперграфов в качестве алгебраической структуры // Изв. РАН. ТиСУ. 2011. № 5. С. 53–59.
  26. Погребной В.К., Погребной А.В. Исследование полиномиальности метода вычисления интегрального описателя структуры графа // Изв. Томск. политехн. ун-та. 2013. Т. 323. № 5. С. 146–151.
  27. Гольцова Т.Ю., Егорова Е.К., Мокряков А.В., Цурков В.И. Сигнатуры экстремальных 2-однородных гиперграфов // Изв. РАН. ТиСУ. 2021. Т. 6. № 6. С. 52–60.
  28. Мокряков А.В., Цурков В.И. Восстановление 2-комплексов по целочисленному неотрицательному вектору // АиТ. 2011. № 12. С. 130–143.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© И.С. Берецкий, Е.К. Егорова, А.В. Мокряков, В.И. Цурков, 2023