Аннотация:
Минимальные рёберные расширения графов можно рассматривать как модель оптимальной рёберной отказоустойчивой реализации некоторой системы. Работа посвящена верхней оценке количества дополнительных рёбер минимальных рёберных $1$-расширений для графов специального вида – сверхстройных деревьев. Приводятся две схемы построения рёберного $1$-расширения для сверхстройного дерева произвольного вида и соответствующий алгоритм на основе этих схем.
Ключевые слова:графы, минимальные расширения графов, сверхстройное дерево, отказоустойчивость.
Полный текст:
PDF файл (807 kB)