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

ПДМ, 2011, номер 2(12), страницы 77–89 (Mi pdm270)

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

Минимальные реберные расширения направленных и ориентированных звезд

М. Б. Абросимов

Саратовский государственный университет им. Н. Г. Чернышевского, г. Саратов, Россия

Аннотация: Рассматриваются минимальные реберные $k$-расширения графов, которые получаются из звездного графа произвольной ориентацией ребер. Ранее было получено полное решение, описывающее минимальные вершинные и реберные $k$-расширения неориентированных звезд, а также минимальные вершинные $k$-расширения ориентированных звезд. В этой работе дается полное описание всех минимальных реберных $k$-расширений для ориентированных и направленных звезд.

Ключевые слова: минимальное расширение, оптимальная отказоустойчивая реализация, отказоустойчивость, звездные графы.

УДК: 519.17



© МИАН, 2024