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

№6 ПРИЛОЖЕНИЕ Сентябрь 2013

Секция 4 ПРИКЛАДНАЯ ТЕОРИЯ ГРАФОВ

УДК 519.17

О НИЖНЕЙ ОЦЕНКЕ ЧИСЛА ДОПОЛНИТЕЛЬНЫХ ДУГ МИНИМАЛЬНОГО ВЕРШИННОГО 1-РАСШИРЕНИЯ ОРИЕНТАЦИИ ЦЕПИ

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

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

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

Граф С* = (V*,а*) называется минимальным вершинным к-расширением п-вер-шинного графа С = (V, а), если выполняются следующие условия:

1) граф С* является вершинным к-расширением графа С, то есть граф С вложим в каждый подграф графа С*, получающийся удалением любых его к вершин;

2) граф С* содержит п + к вершин, то есть IV*| = IV| + к;

3) а* имеет минимальную мощность при выполнении условий 1 и 2.

Понятие минимального вершинного к-расширения появилось в работе Дж. Хейза [1] как модель для исследования отказоустойчивости дискретных систем. Там же доказывается, что минимальным вершинным 1-расширением п-вершинной цепи является (п + 1)-вершинный цикл, а в работе [2] доказывается, что это минимальное вершинное 1-расширение является единственным с точностью до изоморфизма. Задача поиска минимального вершинного к-расширения для произвольного графа является вычислительно сложной [3], и в общем виде решение удалось получить лишь для некоторых классов графов.

Рассмотрим ориентации цепи. Очевидно, что ориентация цепи, являющаяся гамильтоновым графом, имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение — контур с одной дополнительной вершиной.

В работе [4] доказывается результат, позволяющий связать минимальные вершинные 1-расширения неориентированных графов и их ориентаций: число дополнительных дуг минимального вершинного 1-расширения орграфа не меньше числа дополнительных рёбер минимального вершинного 1-расширения его симметризации.

Удалось установить следующие результаты.

Теорема 1. Среди ориентаций цепи только гамильтонова цепь имеет минимальное вершинное 1-расширение, содержащее две дополнительные дуги.

Теорема 2. Не существует ориентаций цепей с числом вершин п > 4, таких, что их минимальное вершинное 1-расширение содержит три дополнительные дуги.

Полученные теоремы позволяют получить следующее утверждение.

Следствие 1. Любая ориентация цепи с числом вершин n > 4, отличная от гамильтоновой цепи, имеет минимальное вершинное 1-расширение с не менее чем четырьмя дополнительными дугами.

ЛИТЕРАТУРА

1. Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V.C-25. No. 9. P. 875-884.

2. Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012. 192 с.

3. Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. Т. 88. Вып. 5. С. 643-650.

4. Абросимов М. Б. Минимальные вершинные расширения направленных звезд // Дискретная математика. 2011. №23:2. С. 93-102.

УДК 519.172.3, 519.68

СВОЙСТВА ГЕННЫХ СЕТЕЙ ЦИРКУЛЯНТНОГО ТИПА С ПОРОГОВЫМИ ФУНКЦИЯМИ

Ц. Ч.-Д. Батуева

Описан алгоритм нахождения всех неподвижных точек графа состояний генной сети циркулянтного типа с произвольной булевой функцией. Описаны все истоки графа состояний генной сети с пороговой функцией от к переменных, такой, что существует единственный набор V, для которого /(у) = 1. Для таких функций от трёх переменных описаны все циклы графа состояний и вычислены длины максимальных цепочек до цикла.

Ключевые слова: генная сеть, ориентированный граф, пороговая функция, граф состояний отображения, цикл, неподвижная точка, исток графа состояний.

Пусть п ^ к — натуральные числа. Циклическим словом называется периодическое бесконечное в две стороны слово с периодом п; обозначается а1а2 ... ап. Множество всех циклических слов длины п будем обозначать через Пп.

Рассмотрим ориентированный граф Сп,к+1 = (V, Е), где множество вершин V равно {^і,... , уп} (последовательность вершин соответствует циклическому слову), а множество рёбер Е такое, что каждая вершина V имеет входящие рёбра из к предыдущих вершин и выходящие в к следующих вершин.

Пороговой функцией называется булева функция, которая представима в виде к

Е аі Хі > Т

і= 1

f

где ai — вес аргумента Xi, a T — порог функции f;

аг, Т е К.

Рассмотрим пороговую функцию f, зависящую от к переменных. Построим отображение Af : Пп ^ Пп, которое каждому слову а\а2 ... ап ставит в соответствие слово Ь1Ь2 . . . Ьп, если

Ьг — f

для всех г е {1,...,п}. Неподвижной точкой отображения Af называется слово а, такое, что а = Af(а).

Циклическое слово а называется истоком для отображения Af : Пп ^ Пп, если не существует слова в, такого, что Af (в) = а.