RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика. Приложение // Архив

ПДМ. Приложение, 2022, выпуск 15, страницы 112–116 (Mi pdma592)

Прикладная теория кодирования и графов

О верхней и нижней оценках числа дополнительных дуг минимального рёберного $1$-расширения ориентации цикла

О. В. Моденова, М. Б. Абросимов

Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского

Аннотация: Исследуются верхняя и нижняя оценки числа дополнительных дуг $\text{ec}(\overrightarrow{C_n})$ минимального рёберного $1$-расширения ориентации $\overrightarrow{C_n}$ цикла $C_n$. Основной результат работы: $\left\lceil {n}/{2} \right\rceil \leq \text{ec}(\overrightarrow{C_n}) \leq n$. Приводятся примеры ориентаций циклов, на которых оценки достигаются.

Ключевые слова: минимальное рёберное $1$-расширение, ориентация цикла, отказоустойчивость.

УДК: 519.17

DOI: 10.17223/2226308X/15/27



© МИАН, 2024