RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика // Архив

Изв. Сарат. ун-та. Нов. сер. Сер.: Математика. Механика. Информатика, 2011, том 11, выпуск 3(2), страницы 111–117 (Mi isu258)

Эта публикация цитируется в 3 статьях

Информатика

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

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

Саратовский государственный университет, кафедра теоретических основ компьютерной безопасности

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

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

УДК: 519.17

DOI: 10.18500/1816-9791-2011-11-3-2-111-117



© МИАН, 2024