|
Прикладная теория кодирования и графов
О верхней и нижней оценках числа дополнительных дуг минимального рёберного $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$-расширение, ориентация цикла, отказоустойчивость.
Образец цитирования:
О. В. Моденова, М. Б. Абросимов, “О верхней и нижней оценках числа дополнительных дуг минимального рёберного $1$-расширения ориентации цикла”, ПДМ. Приложение, 2022, № 15, 112–116
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma592 https://www.mathnet.ru/rus/pdma/y2022/i15/p112
|
|