|
Совершенные раскраски гиперграфа подматриц
С. О. Бородин, А. А. Тараненко Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Аннотация:
Гиперграфом подматриц $G_{n\times m}$ назовём гиперграф, вершинами которого являются элементы матрицы размера $n\times m,$ а гиперрёбрами — все возможные подматрицы порядка $2$. В настоящей работе рассматриваются совершенные раскраски гиперграфов $G_{n\times m}$ и условия на их параметры инцидентности. Предложено несколько конструкций совершенных раскрасок $G_{n\times m}$ и доказано, что матрицы инцидентности $2$-схем являются совершенными раскрасками гиперграфа подматриц. Кроме того, описаны совершенные $2$-раскраски гиперграфов $G_{2\times m}$ и $G_{3\times m}.$ Ил. 1, библиогр. 12.
Ключевые слова:
гиперграф, симметричная 2-схема, совершенная раскраска.
Статья поступила: 04.09.2023 Переработанный вариант: 07.02.2024 Принята к публикации: 22.03.2024
Образец цитирования:
С. О. Бородин, А. А. Тараненко, “Совершенные раскраски гиперграфа подматриц”, Дискретн. анализ и исслед. опер., 31:3 (2024), 54–78; J. Appl. Industr. Math., 18:3 (2024), 424–440
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da1353 https://www.mathnet.ru/rus/da/v31/i3/p54
|
|