О минимальных реберных k-расширениях направленных звезд

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

Секция 5

МАТЕМАТИЧЕСКИЕ ОСНОВЫ НАДЁЖНОСТИ ВЫЧИСЛИТЕЛЬНЫХ И УПРАВЛЯЮЩИХ СИСТЕМ

УДК 519.17

О МИНИМАЛЬНЫХ РЕБЕРНЫХ к-РАСШИРЕНИЯХ НАПРАВЛЕННЫХ ЗВЕЗД

М. Б. Абросимов

Звездой называется полный двудольный граф К1п, в котором одна вершина смежна с п попарно несмежными вершинами. Направленной звездой назовём диграф, симметризация которого является звездой, то есть направленный граф, получающийся из неориентированной звезды заменой каждого ребра дугой. Направленную звезду будем обозначать Zm,n, где т и п — число вершин с одной исходящей и одной входящей дугой соответственно. Вершину, являющуюся концом или началом каждой дуги звезды, будем называть центральной.

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

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

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

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

Понятие минимального к-расширения введено на основе конструкции оптимальной к-отказоустойчивой реализации. Понятие реберной отказоустойчивости было предложено Хейзом совместно с Харари в работе [1]. Было доказано, что задача проверки к-расширения для произвольного графа является КР-полной (см. [2]).

В работе [3] дается полное описание минимальных вершинных и реберных к-рас-ширений неориентированных звезд. Удалось получить полное описание минимальных вершинных к-расширений направленных звезд (см. [4]). Основной результат данной работы устанавливает для направленных звезд вид их минимальных реберных к-рас-ширений.

Обозначим через ^Кт,га,р семейство графов, получающихся из звезды Zm,n добавлением р — 1 центральной вершины, соединением их между собой и центральной вершиной звезды Zm,n парами встречных дуг. Каждая из добавленных центральных вершин соединяется т входящими и п исходящими дугами с произвольными источниками и стоками звезды Zmn. По описанной схеме для заданной звезды в общем случае может быть построено много графов.

Теорема 1. Относительно минимальных реберных 1-расширений направленных звезд Zm,n справедливо следующее:

1) при т = п =1 звезда Zl,l имеет единственное с точностью до изоморфизма минимальное реберное 1-расширение, которым является циклическая тройка;

2) при тп > 1 звезда Zm,n имеет минимальные реберные 1-расширения вида к и графы, построенные по схемам ZKm_1n,2 и ZKmn_1,2;

3) при m > 0, n = 0 звезда Zm,n имеет минимальные реберные 1-расширения вида

ZKm— 1,n,2;

4) при m = 0, n > 0 звезда Zm,n имеет минимальные реберные 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 > 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 звезда Zm,n при 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 > 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 цепей