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

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


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

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

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

3) при m & gt- 0, n = 0 звезда Zm, n имеет минимальные реберные 1-расширения вида
ZKm-1,n, 2-
4) при m = 0, n & gt- 0 звезда Zmn имеет минимальные реберные 1-расширения вида
ZKm, n-1,2-
5) при m = 2, n =1 звезда Z2,1 имеет еще одно минимальное реберное 1-расширение — турнир, получающийся из циклической тройки добавлением одной вершины и дуг от нее во все остальные вершины-
6) при m = 2, n =1 звезда Z21 имеет еще одно минимальное реберное 1-расширение — турнир, получающийся из циклической тройки добавлением одной вершины и дуг в нее из всех остальных вершин.
Для общего случая результат формулируется следующим образом.
Теорема 2. Относительно минимальных реберных k-расширений направленных звезд Zm, n при k & gt- 1 справедливо следующее:
1) при m = n = k звезда Zm, n имеет минимальным реберным k-расширением любой регулярный (2k + 1)-вершинный турнир и только их-
2) при m = n + 1 = k звезда Zm+1,m имеет минимальным реберным k-расширением любой (2k + 2)-вершинный турнир, который получается из регулярного (2k + 1)-вершинного турнира добавлением дополнительной вершины-источника-
3) при m + 1 = n = k звезда Zm, m+1 имеет минимальным реберным k-расширением любой (2k + 2)-вершинный турнир, который получается из регулярного (2k + 1)-вершинного турнира добавлением дополнительной вершины-стока-
4) кроме случая m = n = k звезда Zmn при k ^ m + n имеет минимальным реберным k-расширением графы вида ZKmi, ni, k+1, где
m1 + n1 = m + n — k- max{0, m — k} ^ m1 ^ m- max{0, n — k} ^ n1 ^ m.
При k & gt- m + n звезда Zm, n не имеет минимальных реберных k-расширений.
ЛИТЕРАТУРА
1. Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. V. 23. P. 135−142.
2. Абросимов М. Б. О вычислительной сложности расширений графов // Прикладная дискретная математика. Приложение. 2009. № 1. С. 94−95.
3. Абросимов М. Б. Минимальные расширения неориентированных звезд // Теоретические проблемы информатики и ее приложений. Саратов: СГУ, 2006. Вып 7. С. 3−5.
4. Абросимов М. Б. Минимальные расширения направленных звезд // Проблемы теоретической кибернетики: тез. докл. XV Междунар. конф. (Казань, 2−7 июня 2008 г.). Казань: Отечество. 2008. С. 2.
УДК 519. 17
О МИНИМАЛЬНЫХ ВЕРШИННЫХ 1-РАСШИРЕНИЯХ СВЕРХСТРОЙНЫХ ДЕРЕВЬЕВ СПЕЦИАЛЬНОГО ВИДА
М. Б. Абросимов, Д. Д. Комаров
Дерево называется сверхстройным, если все его вершины, кроме корня и листьев, имеют степень 2. Сверхстройное дерево можно рассматривать как объединение k цепей
P?1,…, P? fc с общей концевой вершиной. Для однозначного задания сверхстройного дерева достаточно указать длины этих цепей: (/1 — І,… ,/& amp- - І).
Граф G* = (V*, а*) называется минимальным вершинным k-расширением (k — натуральное) n-вершинного графа G = (V, а), если выполняются следующие условия:
1) G* является вершинным k-расширением G, то есть граф G вкладывается в каждый подграф графа G*, получающийся удалением любых его k вершин-
2) G* содержит n + k вершин, то есть |V*| = |V| + k-
3) а* имеет минимальную мощность при выполнении условий l и 2.
Понятие минимального k-расширения введено на основе понятия оптимальной k-отказоустойчивой реализации, которое предложено Хейзом в работе [l], где описана модель для исследования отказоустойчивости, основанная на графах.
Вектор степеней сверхстройного дерева имеет вид (k, 2,…, 2, І,…, І), причем количество листьев, то есть вершин степени l, в точности равно k. Кратко вектор степеней сверхстройного дерева может быть записан в виде (k, 2m, Ік). Среди сверхстройных деревьев есть представители других хорошо известных семейств графов.
Если k = І или k = 2, то сверхстройное дерево является цепью Pn. Единственное минимальное вершинное l-расширение цепи Pn есть цикл Cn+1 (см. [l]). Далее исключим цепи из рассмотрения и будем говорить о сверхстройных деревьях, у которых k & gt- 2.
Если m = О, то сверхстройное дерево является звездой K1,^. Минимальное вершинное l-расширение звезды K1,^ единственно с точностью до изоморфизма и получается добавлением вершины и соединением ее со всеми вершинами звезды.
Пусть граф G* суть минимальное вершинное l-расширение некоторого сверхстройного дерева T. Очевидно, что G* не может содержать вершин степени меньше двух.
В самом деле, если бы некоторая вершина имела степень l, то удаление смежной с ней вершины привело бы к графу с изолированной вершиной. В такой граф дерево T вкладываться не может. Граф G* должен иметь, по крайней мере, две вершины степени не ниже k, причем если эти вершины имеют в точности степень k, то они не могут быть смежны. Если бы такая вершина была одна, то ее удаление из графа G* привело бы к графу, в который дерево T вкладываться не может. Аналогично, если вершин степени k две и они смежны. Таким образом, граф G* отличается от дерева T не менее чем на k дополнительных ребер. Эту оценку уточняет следующая
Теорема 1. Число дополнительных ребер минимального вершинного l-расширения любого сверхстройного дерева не меньше k + І.
На основании проведенного вычислительного эксперимента были проанализированы все сверхстройные деревья с количеством вершин до lO общим числом 67. Большинство из них имеют минимальные вершинные l-расширения с числом дополнительных ребер k + І. Только у 9 из них минимальные вершинные l-расширения имеют k + 2 дополнительных ребра и у одного дерева — k + З (это дерево имеет вид (З, З, З)).
Легко заметить, что если минимальное вершинное l-расширение сверхстройного дерева имеет k + І дополнительных ребер, то его вектор степеней может иметь вид ((k + І)2, 2m+k), (k + І, k, З, 2m+k-1) или (k2, З2, 2m+k-2). В работе [2] удалось полностью описать минимальные вершинные l-расширения сверхстройных деревьев, которые имеют вектор степеней первого вида.
Теорема 2. Пусть сверхстройное дерево является объединением k & gt- 2 цепей длины /1,… ,/&-, где хотя бы одна цепь имеет длину больше единицы. Минимальное вершинное l-расширение этого дерева будет отличаться на k + І дополнительных ребер
и иметь вектор степеней ((k + 1)2, 2m+k) тогда и только тогда, когда
Vi Є {1,…, k} (li & gt- 1 ^ Vj Є {2, … ,/i} 3p (1 ^ p ^ k & amp- (Ip = j — 1 V Ip = li — j))).
Минимальное вершинное 1-расширение из теоремы 2 строится следующим образом: к дереву T добавляется вершина, соединяется ребрами со всеми листьями и с корневой вершиной.
Среди 67 сверхстройных деревьев с числом вершин до 10 и имеющих минимально возможное число дополнительных ребер k + 1 только 3 не подпадают под теорему 2. В частности, все сверхстройные деревья с числом вершин до 7 имеют минимальное вершинное 1-расширение вида, указанного в теореме 2. Самые малые по числу вершин сверхстройные деревья, которые имеют минимальные вершинные 1-расширения, отличные от вида из теоремы 2, — это 8-вершинные сверхстройные деревья (1,1, 5) и (2, 2, 3). Всего 13 сверхстройных деревьев с числом вершин до 10 не подпадают под действие теоремы 2.
Удалось описать одно семейство сверхстройных деревьев, у которых есть минимальное вершинное 1-расширение вида (k + 1, k, 3, 2m+k-1).
Теорема 3. Пусть сверхстройное дерево T является объединением k (k & gt- 2) цепей с длинами не более 2, среди которых есть хотя бы одна цепь длины 1 и хотя бы одна цепь длины 2. Тогда граф G*, полученный из дерева T добавлением вершины и соединением ее со всеми листьями и любой вершиной степени 2, является минимальным вершинным 1-расширением дерева T.
Непосредственной проверкой можно убедиться, что графы из теоремы 3 подпадают под действие теоремы 2 и, таким образом, имеют по крайней мере два минимальных вершинных 1-расширения. Оказывается, что имеет место более сильное утверждение.
Теорема 4. Пусть сверхстройное дерево T является объединением k (k & gt- 3) цепей с длинами не более 2, среди которых есть хотя бы одна цепь длины 1 и хотя бы одна цепь длины 2. Тогда дерево T имеет в точности два неизоморфных минимальных вершинных 1-расширения, которые строятся по схемам из теорем 2 и 3.
ЛИТЕРАТУРА
1. Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976.
V. C25. No. 9. P. 875−884.
2. Абросимов М. Б. Минимальные вершинные расширения графов // Новые информационные технологии в исследовании дискретных структур. Томск, 2000. С. 59−64.
УДК 681.3. 012+681. 3−192
ПРИМЕНЕНИЕ НЕНАДЁЖНЫХ ТЕСТОВ ДЛЯ САМОДИАГНОСТИКИ МОДУЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ ПРИ КРАТНЫХ ОТКАЗАХ
Димитриев Ю. К., Задорожный А. Ф.
Исследуется возможность децентрализованной диагностики модульных вычислительных систем в условиях кратных отказов. Модули с точки зрения диагностики являются неделимыми единицами системы. Их функциональные характеристики позволяют им в одиночку осуществить полную проверку других (соседних) модулей и

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