О нижней оценке числа дополнительных дуг минимального вершинного 1-расширения ориентации цепи | ПДМ. 2013. № 6 (Приложение).

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

Даётся нижняя оценка для числа дополнительных дуг минимального вершинного 1-расширения произвольной ориентации цепи.

About the lower bounds for the number of additional arcs in a minimal vertex 1-extension of oriented path.pdf Граф G* = (V*,а*) называется минимальным вершинным к-расширением n-вер-шинного графа G = (V, а), если выполняются следующие условия: 1) граф G* является вершинным k-расширением графа G, то есть граф G вложим в каждый подграф графа G*, получающийся удалением любых его к вершин; 2) граф G* содержит n + к вершин, то есть |V*| = |V| + к; 3) а* имеет минимальную мощность при выполнении условий 1 и 2. Понятие минимального вершинного к-расширения появилось в работе Дж. Хейза [1] как модель для исследования отказоустойчивости дискретных систем. Там же доказывается, что минимальным вершинным 1-расширением n-вершинной цепи является (n + 1)-вершинный цикл, а в работе [2] доказывается, что это минимальное вершинное 1-расширение является единственным с точностью до изоморфизма. Задача поиска минимального вершинного к-расширения для произвольного графа является вычислительно сложной [3], и в общем виде решение удалось получить лишь для некоторых классов графов. Рассмотрим ориентации цепи. Очевидно, что ориентация цепи, являющаяся га-мильтоновым графом, имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение — контур с одной дополнительной вершиной. В работе [4] доказывается результат, позволяющий связать минимальные вершинные 1-расширения неориентированных графов и их ориентаций: число дополнительных дуг минимального вершинного 1-расширения орграфа не меньше числа дополнительных рёбер минимального вершинного 1-расширения его симметризации. Удалось установить следующие результаты. Теорема 1. Среди ориентаций цепи только гамильтонова цепь имеет минимальное вершинное 1-расширение, содержащее две дополнительные дуги. Теорема 2. Не существует ориентаций цепей с числом вершин n > 4, таких, что их минимальное вершинное 1-расширение содержит три дополнительные дуги. Полученные теоремы позволяют получить следующее утверждение. Следствие 1. Любая ориентация цепи с числом вершин n > 4, отличная от га-мильтоновой цепи, имеет минимальное вершинное 1-расширение с не менее чем четырьмя дополнительными дугами.

Ключевые слова

граф, минимальное вершинное расширение, отказоустойчивость, graph, minimal vertex extension, fault tolerance

Авторы

ФИООрганизацияДополнительноE-mail
Абросимов Михаил БорисовичСаратовский государственный университетдоцент, кандидат физико-математических наук, доцентmic@rambler.ru
Моденова Ольга ВладимировнаСаратовский государственный университетаспирантка кафедры теоретических основ компьютерной безопасности и криптографииoginiel@rambler.ru
Всего: 2

Ссылки

Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V.C-25. No. 9. P. 875-884.
Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012. 192 с.
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. Т. 88. Вып. 5. С. 643-650.
Абросимов М. Б. Минимальные вершинные расширения направленных звезд // Дискретная математика. 2011. №23:2. С. 93-102.
 О нижней оценке числа дополнительных дуг минимального вершинного 1-расширения ориентации цепи | ПДМ. 2013. № 6 (Приложение).

О нижней оценке числа дополнительных дуг минимального вершинного 1-расширения ориентации цепи | ПДМ. 2013. № 6 (Приложение).

Полнотекстовая версия