Отправить статью по E-mail 
ОБЪЕДИНЕНИЕ БАЗ И ОЦЕНКА МНОЖЕСТВА ЭКСТРЕМАЛЬНЫХ 3-ОДНОРОДНЫХ ГИПЕРГРАФОВ
- Авторы: Берецкий И.С.1, Егорова Е.К.1,2, Мокряков А.В.1,3, Цурков В.И.2
-
Учреждения:
- МАИ (национальный исследовательский ун-т)
- ФИЦ ИУ РАН
- РГУ им. А.Н. Косыгина (Технологии. Дизайн. Искусство)
- Выпуск: № 5 (2023)
- Страницы: 67-77
- Раздел: КОМПЬЮТЕРНЫЕ МЕТОДЫ
- URL: https://journal-vniispk.ru/0002-3388/article/view/140343
- DOI: https://doi.org/10.31857/S0002338823050037
- EDN: https://elibrary.ru/TEEFBU
- ID: 140343
Цитировать
Полный текст
Аннотация
Основная проблема, связанная с гиперграфами, – это их храненение. Если гиперграф без особенностей, то для его описания часто используются разряженные матрицы. Для работы с k-однородными гиперграфами часто применяют матрицы смежности, однако они занимают большое место в памяти компьютера и в целом храненение k-мерных массивов не очень удобно. Здесь предлагается одно решение для описания и хранения экстремальных k-однородных гиперграфов. Это база – уникальная характеристика экстремального гиперграфа, которая однозначно его описывает. Кроме того, базы можно применять для поиска мощности экстремальных k-однордных гиперграфов. Нами представлены алгоритмы перечисления баз и представлена гипотеза об аналитическом виде формул, описывающих мощность множества экстремальных k-однородных гиперграфов. Для данной задачи используется операция объединения баз, также введенная здесь.
Об авторах
И. С. Берецкий
МАИ (национальный исследовательский ун-т)
Email: MokryakovAlVik@ya.ru
Россия, Москва
Е. К. Егорова
МАИ (национальный исследовательский ун-т); ФИЦ ИУ РАН
Email: MokryakovAlVik@ya.ru
Россия, Москва; Россия, Москва
А. В. Мокряков
МАИ (национальный исследовательский ун-т); РГУ им. А.Н. Косыгина (Технологии. Дизайн. Искусство)
Email: MokryakovAlVik@ya.ru
Россия, Москва; Россия, Москва
В. И. Цурков
ФИЦ ИУ РАН
Автор, ответственный за переписку.
Email: MokryakovAlVik@ya.ru
Россия, Москва
Список литературы
- Иванов М.В., Калашников И.В., Нуруллаев М.М. Исследование структурных свойств сети интернет на основе метаграфовых моделей // Информатика и автоматизация. 2020. Т. 19. № 4. С. 880–905.
- Миков А.И., Миков А.А. Свойства геометрических гиперграфов беспроводных компьютерных сетей // Информатизация и связь. 2020. № 4. С. 60–66. https://doi.org/10.34219/2078-8320-2020-11-4-60-66
- Герасименко Е.М., Дышаев Н.Н. Персонализация в фолксономиях в виде гиперграфов на основе кластеризации тегов // Информатика, вычислительная техника и инженерное образование. 2019. № 2 (35). С. 11–15.
- Зыков А.А. Гиперграфы // УМН. 1974. Т. XXIX. № 6 (180). С. 89–154.
- Александров П.С. Комбинаторная топология. М.: Гостехтеориздат, 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
- Ванг Л., Егорова Е.К., Мокряков А.В. Развитие теории гиперграфов // Изв. РАН. ТиСУ. 2018. № 1. С. 111–116.
- Миронов А.А. Геометрия точек пространства Rn, реализуемых в граф // УМН. 1977. Т. XXXII. № 6 (198). С. 232–233.
- Костяной Д.С., Мокряков А.В., Цурков В.И. Алгоритмы восстановления гиперграфов по заданному вектору степеней вершин // Изв. РАН. ТиСУ. 2014. № 4. С. 43–48.
- Бондаренко В.А., Николаев А.В. Об одном классе гиперграфов и о вершинах релаксаций разрезного многогранника // ДАН. 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.
- PrГjfer H. Neuer Beweis eines Satzes Гjber Permutationen // Arch. Math. Phys. 1918. V. 27. P. 742–744.
- Gilbert E.N. Enumeration of Labelled Graphs // Canad. J. Math. 1956. V. 8. P. 405–411.
- Кузьмин О.В., Чернигова А.Г. Автоматизация комбинаторного кодирования и декодирования корневых деревьев // Современные технологии. Системный анализ. Моделирование. 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.
Дополнительные файлы
