|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Информатика
Характеризация орграфов с малым числом дополнительных дуг минимального вершинного $1$-расширения
М. Б. Абросимов, О. В. Моденова Кафедра теоретических основ компьютерной безопасности и криптографии, Саратовский государственный университет им. Н. Г. Чернышевского
Аннотация:
Граф $G^*$ называется вершинным $1$-расширением графа $G$, если граф $G$ можно вложить в каждый граф, получающийся из графа $G^*$ удалением любой его вершины вместе с инцидентными ребрами. Вершинное $1$-расширение $G^*$ графа $G$ называется минимальным, если граф $G^*$ имеет на одну вершину больше, чем граф $G$, а среди всех вершинных $1$-расширений графа $G$ с тем же числом вершин граф $G^*$ имеет минимальное число ребер. Рассматривается задача описания ориентированных графов, минимальное вершинное $1$-расширение которых имеет заданное число дополнительных дуг. Дается решение, когда число дополнительных дуг равно одному или двум.
Ключевые слова:
минимальное расширение, точное расширение, отказоустойчивая реализация, граф.
Образец цитирования:
М. Б. Абросимов, О. В. Моденова, “Характеризация орграфов с малым числом дополнительных дуг минимального вершинного $1$-расширения”, Изв. Сарат. ун-та. Нов. сер. Сер.: Математика. Механика. Информатика, 13:2(2) (2013), 3–9
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/isu406 https://www.mathnet.ru/rus/isu/v13/i4/p3
|
|