First and Second Order Signatures of Extreme Uniform Hypergraphs and Their Relationship with Vectors of the Vertex Degrees

T. Yu. Goltsova; Гольцова Т. Ю.; E. K. Egorova; Егорова Е. К.; V. Yu. Leonov; Леонов В. Ю.; A. V.  Mokryakov; Мокряков А. В.

doi:10.31857/S0002338823040042

СИГНАТУРЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ ЭКСТРЕМАЛЬНЫХ ОДНОРОДНЫХ ГИПЕРГРАФОВ И ИХ СВЯЗЬ С ВЕКТОРАМИ СТЕПЕНЕЙ ВЕРШИН

Авторы: Гольцова Т.Ю.¹, Егорова Е.К.²^,3, Леонов В.Ю.³, Мокряков А.В.¹^,2
Учреждения:
1. РГУ им. А.Н. Косыгина (Технологии. Дизайн. Искусство)
2. МАИ (национальный исследовательский ун-т)
3. ФИЦ ИУ РАН
Выпуск: № 4 (2023)
Страницы: 84-97
Раздел: ДИСКРЕТНЫЕ СИСТЕМЫ
URL: https://journals.rcsi.science/0002-3388/article/view/136875
DOI: https://doi.org/10.31857/S0002338823040042
EDN: https://elibrary.ru/OCGQCV
ID: 136875

Цитировать

Полный текст

Открытый доступ
Доступ закрыт

Доступ предоставлен
Доступ закрыт

Только для подписчиков

Аннотация
Об авторах
Список литературы
Дополнительные файлы
Статистика

Аннотация

Матрицы смежности экстремальных 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.
Мокрозуб В.Г., Немтинов В.А., Мордвин А.С., Илясов А.А. Применение -ориентированных гиперграфов и реляционных баз данных для структурного и параметрического синтеза технических систем // Прикл. информатика. 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.
Миронов А.А. Геометрия точек пространства , реализуемых в граф // УМН. 1977. Т. XXXII. № 6 (198). С. 232–233.
Костяной Д.С., Мокряков А.В., Цурков В.И. Алгоритмы восстановления гиперграфов по заданному вектору степеней вершин // Изв. РАН. ТиСУ. 2014. № 4. С. 43–48.