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

ПДМ. Приложение, 2017, выпуск 10, страницы 134–136 (Mi pdma347)

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

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

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

a Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского, г. Саратов
b Научно-образовательного центра "Эрудит", г. Саратов

Аннотация: Исследуются верхняя и нижняя оценки числа дополнительных дуг $ec(P_n)$ минимального рёберного $1$-расширения ориентации цепи. Если $P_n$ имеет концы разного типа и отлична от гамильтоновой и от ориентации, состоящей из чередующихся источников и стоков, то $\lceil n/6\rceil+1\leq ec(P_n)\leq n+1$. Если $P_n$ имеет концы одинакового типа, то $\lceil n/4\rceil+1\leq ec(P_n)\leq n+1$.

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

УДК: 519.17

DOI: 10.17223/2226308X/10/52



© МИАН, 2024