Эта публикация цитируется в
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