|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Информатика
О нижней оценке числа ребер минимального реберного 1-расширения сверхстройного дерева
М. Б. Абросимов Саратовский государственный университет, кафедра теоретических основ компьютерной безопасности
Аннотация:
Граф $G^*$ называется реберным 1-расширением графа $G$, если граф $G$ можно вложить в каждый граф, получающийся из графа $G^*$, удалением любого его ребра. Реберное 1-расширение $G^*$ графа $G$ называется минимальным, если графы $G$ и $G^*$ имеют одинаковое число вершин, а среди всех реберных 1-расширений графа $G$ с тем же числом вершин граф $G^*$ имеет минимальное число ребер. Дерево называется сверхстройным, если только одна его вершина имеет степень больше двух. В работе дается нижняя оценка числа дополнительных ребер минимального реберного 1-расширения произвольного сверхстройного дерева и указывается семейство деревьев, на которых эта оценка достигается.
Ключевые слова:
минимальное реберное расширение, сверхстройное дерево, звездоподобное дерево, отказоустойчивая реализация.
Образец цитирования:
М. Б. Абросимов, “О нижней оценке числа ребер минимального реберного 1-расширения сверхстройного дерева”, Изв. Сарат. ун-та. Нов. сер. Сер.: Математика. Механика. Информатика, 11:3(2) (2011), 111–117
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/isu258 https://www.mathnet.ru/rus/isu/v11/i4/p111
|
Статистика просмотров: |
Страница аннотации: | 329 | PDF полного текста: | 82 | Список литературы: | 59 |
|