О минимальном рёберном 1-расширении гиперкуба | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/34

О минимальном рёберном 1-расширении гиперкуба

Граф G* с n вершинами называется минимальным рёберным k-расширением n-вершинного графа G, если G вкладывается в каждый граф, получающийся из G* удалением любых его k рёбер, и G* имеет при этом минимально возможное число рёбер. Гиперкуб Qn - это регулярный 2n-вершинный граф порядка n, представляющий собой декартово произведение n полных 2-вершинных графов K2. Предлагается семейство графов Qn, представители которого при n > 1 являются минимальными рёберными 1-расширениями соответствующих гиперкубов. Вычислительный эксперимент показывает, что при n ^ 4 эти расширения являются единственными с точностью до изоморфизма.

About minimal 1-edge extension of hy-percube.pdf Введение Определение 1. Декартовым произведением G1 х G2 двух графов G1 = (V1,a1) и G2 = (V2,a2) называется граф G = (V, a), такой, что V = V х V2, вершины (u1,u2) и (v1,v2) смежны в G тогда и только тогда, когда либо u1 = v1 и u2,v2 смежны в G2, либо u2 = v2 и u1, v1 смежны в G1. Определение 2. Гиперкубом Qn (n-кубом) называется граф, являющийся декартовым произведением n полных 2-вершинных графов K2. Можно дать рекурсивное определение: одномерным гиперкубом Q1 назовём граф K2; n-мерным гиперкубом при n > 1 будем называть граф Qn = K2 х Qn-1, n > 1. Гиперкуб Qn - это регулярный 2n-вершинный граф порядка n. Семейство гиперкубов достаточно хорошо изучено [1]. Вершины гиперкуба можно пометить двоичными векторами таким образом, чтобы расстояние между каждыми двумя вершинами равнялось дистанции Хэмминга между их метками. Это свойство непосредственно следует из построения гиперкуба. Топология гиперкуба является популярной схемой соединения параллельных процессоров [2], в том числе и в отказоустойчивых системах типа IBM Blue Gene/Q [3]. Особый интерес с точки зрения отказоустойчивости представляет 4-куб Q4, или тессе-ракт. Для исследования полной отказоустойчивости элементов Дж. Хейз предложил модель, основанную на графах [4], которую позднее расширил на случай отказов связей [5]. Оптимальные k-отказоустойчивые реализации гиперкубов Qn при n > 3 неизвестны. На практике используются тривиальные отказоустойчивые реализации с одним избыточным элементом, соединённым со всеми остальными. Далее предложена оптимальная рёберная 1-отказоустойчивая реализация гиперкуба Qn при n > 1. 1. Рёберные расширения Определение 3. Граф G* = (V*, а*) называется минимальным рёберным k-рас-ширением n-вершинного графа G = (V, а), если выполняются следующие условия: 1) граф G* является рёберным k-расширением графа G, то есть граф G вкладывается в каждый граф, получающийся из G* удалением любых его k рёбер; 2) граф G* содержит n вершин, то есть |V*| = |V|; 3) а* имеет минимальную мощность при выполнении условий 1 и 2. Если рассматривать простые графы, то минимальное рёберное k-расширение существует не у всех графов. Например, полные графы Kn не имеют минимальных ребёр-ных k-расширений ни при каких натуральных k. Гиперкуб Q1 соответственно тоже не имеет минимального рёберного k-расширения ни при каких натуральных k. У графа может быть несколько неизоморфных минимальных рёберных k-расширений. Задача поиска минимальных рёберных k-расширений является вычислительно сложной [6]. В [3] доказывается лемма, которая позволяет охарактеризовать вид минимального рёберного k-расширения и оценить минимально возможное количество дополнительных рёбер в нём. Лемма 1 [3]. Если минимальная степень вершины графа G есть d > 0, то его минимальное рёберное k-расширение не содержит вершин степени ниже d + k. 2. Минимальное рёберное 1-расширение гиперкуба Удалось найти схему построения минимального рёберного 1-расширения для любого гиперкуба Qn при n > 1 . Определим семейство графов Qn. Граф Qn при n > 1 получается путём соединения каждой вершины гиперкуба Qn с наиболее удалённой от неё вершиной. Если вершина имеет код k, то она соединяется с вершиной, код которой получается из k поразрядной инверсией. Теорема 1. Для n-мерного гиперкуба Qn при n > 1 граф Qn является минимальным рёберным 1-расширением. Легко убедиться, что минимальное рёберное 1-расширение для гиперкуба Q2 единственно с точностью до изоморфизма: граф Q* изоморфен графу K4. Аналитически доказано, что граф Q* является единственным с точностью до изоморфизма минимальным рёберным 1-расширением для гиперкуба Q3. В общем случае единственность минимального рёберного 1-расширения дли гиперкуба Qn при n > 3 пока доказать не удалось. Для гиперкуба Q4 проведён вычислительный эксперимент по поиску всех неизоморфных минимальных рёберных 1-расширений. Из теоремы 1 и леммы 1 следует, что любое минимальное рёберное 1-расширение гиперкуба Qn при n > 1 есть регулярный граф порядка n + 1. С помощью программы genreg [7] были построены все 16-вершинные регулярные графы порядка 5 и проверено, являются ли они 1-рас-ширениями гиперкуба Q4. Найдено единственное расширение - граф Q4. Вычисления проводились с использованием кластера высокопроизводительных вычислений ПРЦ НИТ СГУ. Единственные с точностью до изоморфизма минимальные рёберные 1-расширения гиперкубов Q2, Q3 и Q4 изображены на рис. 1. Рис. 1. Минимальные рёберные 1-расширения для Q2, Q3 и Q4

Ключевые слова

minimal 1-edge extension, edge fault tolerance, hypercube, graph, минимальное рёберное 1-расширение, рёберная отказоустойчивость, гиперкуб, граф

Авторы

ФИООрганизацияДополнительноE-mail
Лобов Александр АндреевичСаратовский национальный исследовательский государственный университет им. Н. Г. Чернышевскогостудентaisanekai@mail.ru
Абросимов Михаил БорисовичСаратовский национальный исследовательский государственный университет им. Н. Г. Чернышевскогодоктор физико-математических наук, профессорmic@rambler.ru
Всего: 2

Ссылки

Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. №5(88). С. 643-650.
Meringer M. Fast generation of regular graphs and construction of cages // J. Graph Theory. 1999. V. 30. P. 137-146.
Harary F., Hayes J. P., and Wu H.-J. A survey of the theory of hypercube graphs // Computers & Math. Appl. 1988. V. 15. P. 277-289.
Padua D. A. Encyclopedia of Parallel Computing. N.Y.: Springer, 2011.
Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012. 192 с.
Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V.C.25. No. 9. P. 875-884.
Harary F. and Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. V. 23. P. 135-142.
 О минимальном рёберном 1-расширении гиперкуба | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/34

О минимальном рёберном 1-расширении гиперкуба | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/34