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

Изв. Сарат. ун-та. Нов. сер. Сер.: Математика. Механика. Информатика, 2013, том 13, выпуск 2(2), страницы 3–9 (Mi isu406)

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

Информатика

Характеризация орграфов с малым числом дополнительных дуг минимального вершинного $1$-расширения

М. Б. Абросимов, О. В. Моденова

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

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

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

УДК: 519.17

DOI: 10.18500/1816-9791-2013-13-2-2-3-9



Реферативные базы данных:


© МИАН, 2024