К вопросу о верхней оценке числа дополнительных рёбер минимальных вершинных расширений цветных циклов

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Графом состояний отображения Af: Qn ^ Qn называется ориентированный граф, в котором Qn — множество вершин, а дуги соединяют слова, а и в, если в = Af (а).
Данная работа посвящена описанию свойств графа состояний отображения Af, а именно описанию истоков, неподвижных точек и циклических состояний, нахождению длин максимальных цепочек.
Пусть f — булева функция от k переменных. Построим ориентированный граф Pf, вершинами которого являются все возможные слова длины k, а рёбра соединяют слова x1… xk и x2 … xkb, если f (x,…, xk) = b. Следующая теорема содержит способ нахождения всех неподвижных точек графов состояния отображения Af для произвольной булевой функции от k переменных.
Теорема 1. Пусть f — булева функция от k переменных и n кратно l. Граф Pf содержит простой цикл (v,…, vi), где Vi = Xj.. Xfc+j-i для i G {1,…, l}, тогда и только тогда, когда (х1… xi) n/l является неподвижной точкой графа состояний отображения Af.
В следующей теореме описаны все истоки графа состояний отображения.
Теорема 2. Пусть f — булева функция от k переменных и существует единственный набор значений переменных v, такой, что f (v) = 1. Тогда циклическое слово, а длины n является истоком графа состояний отображения Af тогда и только тогда, когда оно удовлетворяет одному из условий:
1) а содержит подслово 10s-11, где 1 ^ s ^ k — 1 и s = s'--
2) а содержит подслово 10k-11, где k = ts'- и t ^ 2.
Здесь s'- - минимальный период слова v.
Получено описание всех циклов и длин максимальных цепочек для графа состояний отображения Af, где f — булева функция от трёх переменных, удовлетворяющая условию предыдущей теоремы. Если f (0, 0, 0) = 1, то циклы этого графа представляют циклический сдвиг на 1, 2 или 3 позиции состояния, избегающего определённые слова.
ЛИТЕРАТУРА
1. Евдокимов А. А., Лиховидова Е. О. Дискретная модель генной сети циркулянтного типа с
пороговыми функциями // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2008. № 2(3). С. 18−21.
УДК 519. 17
К ВОПРОСУ О ВЕРХНЕЙ ОЦЕНКЕ ЧИСЛА ДОПОЛНИТЕЛЬНЫХ РЁБЕР МИНИМАЛЬНЫХ ВЕРШИННЫХ РАСШИРЕНИЙ ЦВЕТНЫХ ЦИКЛОВ
П. П. Бондаренко
Приводится верхняя оценка количества дополнительных рёбер в минимальных вершинных 1-расширениях циклов с вершинами двух типов, а также общий вид одного из расширений.
Ключевые слова: граф, цикл, минимальное расширение, отказоустойчивость.
Будем рассматривать неориентированные графы с вершинами двух типов или цветов. Для исследования отказоустойчивости дискретных систем J. P. Hayes [1] предло-
жил графовую модель и рассмотрел отказоустойчивые реализации некоторых классов графов. Основные понятия используются в соответствии с работой [2].
Определение 1. Граф С* = (V*, а*) называется минимальным вершинным к-расширением п-вершинного графа С = (V, а) с вершинами р типов, если выполняются следующие условия:
1) граф С* является вершинным к-расширением графа С, то есть граф С вложим в каждый подграф графа С*, получающийся удалением любых его к вершин-
2) граф С* содержит п + к ¦ р вершин, то есть IV* | = IV| + к ¦ р-
3) а* имеет минимальную мощность при выполнении условий 1 и 2.
Рассмотрим цепь Рп с п + 2 вершинами двух типов: двумя вершинами первого типа степени 1 и п вершинами второго типа. Найдём минимальный по количеству рёбер граф РП, состоящий из п + 3 вершин (две вершины первого типа, а остальные — второго), такой, что при удалении любой вершины второго типа существует путь между вершинами первого типа, проходящий по п вершинам второго типа.
Лемма 1. Минимальное количество дополнительных рёбер в Р* равно [п/2] +3. Если вершины цепи Рп пронумерованы от 0 до п + 1, добавленная вершина в цепи Р* имеет номер п + 2, то для получения Р * к Р нужно добавить следующие рёбра:
а) п — нечётное, п & gt- 1:
{0, 2}- {п + 2, п — 2}- {п + 2, п}- {п + 2, п +1}- {к, к + 3}, 1 ^ к ^ п — 4-
б) п — чётное, п & gt- 2:
{0, 2}- {п + 2, п — 3}- {п + 2, п — 1}- {п + 2, п}- {п + 2, п +1}- {к, к + 3}, 1 ^ к ^ п — 5-
в) п =1: {п + 2, 0}, {п + 2, 2}-
г) п = 2: {п + 2, 0}, {п + 2, 1}, {п + 2, 2}, {п + 2, 3}.
На рис. 1 приведены иллюстрирующие лемму примеры.
Будем рассматривать циклы Сп с вершинами двух типов. Поставим каждому циклу в соответствие последовательность чисел е0, е1,…, е& amp-_1, такую, что
1) к — количество рёбер в цикле Сп, соединяющих две вершины разного типа, т. е. количество групп последовательных вершин одного типа, причём вершины, соседние с крайними из каждой группы, имеют другой тип-
2) г-я группа содержит е^ последовательно соединённых вершин одного типа. Пусть тип вершин в г-й группе отличается от типа вершин в (г — 1)-й группе для любого г & gt- 0. Типы вершин в нулевой и (к — 1)-й группе тоже не совпадают-
3) ео + е1 + ¦ ¦ ¦ + е& amp-_1 = п.
Такой цикл будем обозначать Cn (e0, ei,…, ek-1).
Пусть C*n — минимальное вершинное 1-расширение цикла Cn (e0, e1,…, е^_1). Тогда минимальное количество рёбер, которые нужно добавить к Cn, чтобы получить C*n, можно оценить следующим образом.
Теорема 1. Количество дополнительных рёбер m в минимальном вершинном 1-расширении цикла Cn (e0, e1,…, ek-1) СП удовлетворяет условию
k1
m & lt- Lej/2j +3 ^ Ln/2j + 3k.
i=0
Одно из вершинных 1-расширений строится по лемме 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.
УДК 519. 7
ИССЛЕДОВАНИЕ ДИНАМИЧЕСКИХ СВОЙСТВ НЕКОТОРЫХ ДИСКРЕТНО-АВТОМАТНЫХ ОТОБРАЖЕНИЙ, ЗАДАННЫХ СЛУЧАЙНЫМИ ГРАФАМИ1
А. А. Евдокимов, С. Е. Кочемазов, И. В. Отпущенников, А. А. Семенов
Приведены результаты вычислительного анализа задач поиска неподвижных точек и циклических режимов (циклов) для ряда дискретных отображений, используемых при моделировании поведения систем со множеством взаимодействующих агентов. Рассматривались отображения, задаваемые случайными графами, сгенерированными в соответствии с известными моделями (Сгар-графы, модель Уоттса — Строгатца).
Ключевые слова: случайные графы, генные сети, дискретно-автоматные отображения, SAT.
В последние несколько лет набирают популярность задачи исследования различных свойств мультиагентных систем, взаимодействие компонентов которых определяется сетями [1,2]. Такие системы используются в биоинформатике [3], в исследовании информационных и социальных сетей [2], а также в экономическом моделировании [4]. Авторами в течение ряда лет рассматривались задачи исследования динамических свойств дискретных отображений, естественным образом связанных с сетями. Так, в [5] введены и исследованы дискретные модели, описывающие процессы в генных сетях, получены теоретические результаты (в форме теорем), дающие условия возникновения неподвижных точек и циклов для отображений, заданных сетью регулярной структуры (использовались циркулянтные графы). В работе [6] весовые функции из [5] использовались в сетях случайной структуры. Рассматривались задачи поиска неподвижных
1 Работа выполнена при поддержке Междисциплинарного интеграционного проекта СО РАН № 80 «Дифференциально-разностные и интегродифференциальные уравнения. Приложения к задачам естествознания" — гранта Президента Р Ф СП-3667. 2013. 5- грантов РФФИ № 11−07−377а, 11−01−997.

ПоказатьСвернуть
Заполнить форму текущей работой