О количестве минимальных вершинных и реберных 1-расширений циклов с числом вершин до 17

лагается добавить ребро из вершины старшей степени в вершину vi(j-1). Далее авторы статьи утверждают, что построенный граф является минимальным вершинным 1-расширением заданного сверхстройного дерева. Однако в общем случае построенный граф является вершинным 1-расширением, но не обязательно минимальным.

Из 67 сверхстройных деревьев с числом вершин до 10 есть деревья, которые не попадают под действие теоремы 1, но имеют k+1 дополнительное ребро [3]. Оказывается, что все они являются контрпримерами к утверждению 1.

Сверхстройное дерево (5, 1, 1) имеет одну сложную вершину, но имеет единственное минимальное вершинное 1-расширение вида (k2, 32, 2m+k-2) с четырьмя дополнительными рёбрами.

Сверхстройное дерево (3, 2, 2) также имеет одну сложную вершину, но имеет два минимальных вершинных 1-расширения вида (k2, 32,2m+k-2) и одно вида ((k + 1), k, 3, 2m+k-1) с четырьмя дополнительными рёбрами.

Наконец, сверхстройное дерево (4, 3, 2) имеет одну сложную вершину, но имеет 4 минимальных вершинных 1-расширения вида (k2, 32, 2m+k-2) с четырьмя дополнительными рёбрами.

Ещё один интересный пример представляет собой сверхстройное дерево (5, 2, 2). Можно заметить, что оно имеет две сложные вершины, но его 37 минимальных вершинных 1-расширений имеют 5, а не 6 дополнительных ребер. Аналогичная ситуация с деревьями (6, 1, 1) и (3, 3, 2), у которых также по две сложные вершины, но минимальные вершинные 1-расширения имеют 5 дополнительных рёбер.

Самое большое отклонение среди всех сверхстройных деревьев с числом вершин до 10 наблюдается на сверхстройном дереве (7, 1, 1). Непосредственной проверкой можно убедиться, что оно имеет три сложные вершины, но его 8 минимальных вершинных 1-расширений имеют 5, а не 7 дополнительных рёбер. Можно предположить, что на сверхстройных деревьях вида (t, 1, 1) (количество сложных вершин в таких деревьях составляет t — 3 при t > 3) при увеличении t отклонение будет возрастать.

Каждый из этих контрпримеров показывает ошибочность утверждения 1 в общем случае.

ЛИТЕРАТУРА

1. Абросимов М. Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур. Томск, 2000. С. 59-64.

2. Harary F and Khurum M. One node fault tolerance for caterpillars and starlike trees // Internet J. Comput. Math. 1995. V. 56. P. 135-143.

3. Абросимов М. Б., Комаров Д. Д. Минимальные вершинные расширения сверхстройных деревьев с малым числом вершин / Саратов, СГУ, 2010. 38 с. Деп. в ВИНИТИ 18.10.2010, № 590-В2010.

УДК 519.17

О КОЛИЧЕСТВЕ МИНИМАЛЬНЫХ ВЕРШИННЫХ И РЁБЕРНЫХ 1-РАСШИРЕНИЙ ЦИКЛОВ С ЧИСЛОМ ВЕРШИН ДО 17

М. Б. Абросимов, Н. А. Кузнецов

Дж. П. Хейз в работе [1], а затем вместе с Ф. Харари в работах [2, 3] предложил графовую модель для исследования отказоустойчивости дискретных систем. Особое внимание было уделено системам, представимым циклами. В работах [1-3] предложены

схемы построения одной оптимальной отказоустойчивой реализации (минимального расширения) цикла; другие схемы предложены в [4-7].

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

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

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

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

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

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

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

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

Если говорить о минимальных вершинных и рёберных к-расширениях циклов, то можно встретить эквивалентные определения.

Граф называется к-вершинно-гамильтоновым, если после удаления любых его к вершин и инцидентных им рёбер получившийся граф является гамильтоновым. Граф называется к-рёберно-гамильтоновым, если после удаления любых к рёбер получившийся граф является гамильтоновым. Вершинно-(рёберно-)к-гамильтонов граф называется оптимальным, если он имеет минимально возможное число рёбер среди всех вершинно-(рёберно-)к-гамильтоновых графов с тем же числом вершин.

Известно, что задачи проверки вершинных (рёберных) к-расширений произвольных графов, так же как и задачи проверки к-вершинно-(рёберно-)гамильтоновых графов являются УР-полными [8]. Интерес представляет количество неизоморфных расширений для различных графов. В 2000 г. проведён вычислительный эксперимент [6-9], в рамках которого удалось построить все минимальные вершинные и рёберные 1-расширения циклов с числом вершин до 13. В рамках представляемой работы проведён новый вычислительный эксперимент с использованием распределённых вычислений. Удалось построить все минимальные вершинные и рёберные 1-расширения циклов с числом вершин до 17. Основные результаты представлены в таблице.

Минимальные вершинные (МВ-1Р) и рёберные (МР-1Р) 1-расширения циклов

Число вершин Число МВ-1Р Число МР-1Р

3 1 1

4 1 1

5 1 1

6 2 2

7 2 2

8 10 4

9 7 13

10 63 13

11 27 87

12 602 53

13 158 885

14 7203 320

15 1396 10933

16 104212 2641

17 16069 160145

ЛИТЕРАТУРА

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. Harary F. and Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. V. 23. P. 135-142.

3. Harary F. and Hayes J. P. Node fault tolerance in graphs // Networks. 1996. V. 27. P. 19-23.

4. Mukhopadhyaya K. and Sinha B. P. Hamiltonian graphs with minimum number of edges for fault-tolerant topologies // Inform. Process. Lett. 1992. V. 44. P. 95-99.

5. Hsu L. H. and Lin C. K. Graph Theory and Interconnection Networks. CRC Press, 2009.

6. Абросимов М. Б. О неизоморфных оптимальных 1-отказоустойчивых реализациях некоторых графов // Теоретические проблемы информатики и её приложений. Саратов: СГУ, 2000. Вып. 3. С. 3-10.

7. Абросимов М. Б. О неизоморфных минимальных реберных 1-расширениях графов // Теоретические проблемы информатики и её приложений. Саратов: СГУ, 2004. Вып. 6. С. 3-9.

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

9. Абросимов М. Б. Минимальные вершинные расширения циклов с числом вершин не более одиннадцати / Саратов: СГУ, 2001. 17 с. Деп. в ВИНИТИ 14.08.2001, №1869-В2001.

УДК 519.17

ОБ ОРГРАФАХ, ИМЕЮЩИХ МИНИМАЛЬНЫЕ ВЕРШИННЫЕ 1-РАСШИРЕНИЯ С МАЛЫМ КОЛИЧЕСТВОМ ДОПОЛНИТЕЛЬНЫХ ДУГ

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

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

Лемма 1 [3]. Пусть G* есть минимальное вершинное k-расширение орграфа G. Тогда симметризация G* является вершинным k-расширением симметризации G.

Следствие 1. Число дополнительных дуг минимального вершинного k-расширения орграфа G не менее числа дополнительных рёбер минимального вершинного k-расширения симметризации орграфа G.

В работе [2] получены следующие результаты (теоремы 1-3).

Теорема 1. Графы со степенным множеством {1, 0}, и только они, имеют минимальные вершинные 1-расширения с одним дополнительным ребром; для каждого графа со степенным множеством {1, 0} такое расширение единственно с точностью до изоморфизма.

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