Regular vertex 1-extension for 2-di-mension meshes.pdf Безопасность вычислительных систем имеет большое значение. Отказ элементов может привести к её полной неработоспособности. Для обеспечения отказоустойчивости таких систем может применяться графовая модель. Каждому вычислительному узлу системы сопоставляется вершина графа, а связь между двумя узлами представляется ребром между соответствующими вершинами. Далее граф дополняется вершинами и рёбрами до вершинного k-расширения, которое является представлением устойчивой к отказу k узлов вычислительной системы. Будем рассматривать случай с k = 1. Граф G* является вершинным 1-расширением (В-1-Р) графа G, если G вкладывается в каждый граф, полученный из G* удалением одной вершины. Если количество вершин в G* на 1 больше, чем в G, и среди всех В-1-Р графа G с таким числом вершин количество рёбер в G* минимально, то G* называется минимальным вершинным 1-расширением (МВ-1-Р) графа G [1]. Задача построения расширений графа связана с построением отказоустойчивой вычислительной системы [2, 3]. В этих работах для некоторых классов графов, таких, как цепи и циклы, предложены способы построения МВ-1-Р, однако в целом задача нахождения МВ-1-Р заданного графа является вычислительно сложной [4]. Дадим определение рассматриваемым в работе графам. Определение 1. Двухмерной решёткой, или просто решёткой nx m, называется граф, множество вершин которого состоит из пар (i, j), i, j G {0, . . . , n-1}, и множество рёбер состоит из всех возможных пар вершин (u1, v1) и (u2, v2), для которых |u1-u2| = 1 и v1 = v2 или |v1 - v2| = 1 и u1 = u2. Пример такого графа представлен на рис. 1. Двухмерная решётка является интересной топологией с практической точки зрения. Теорема 1. При n,m 2 для каждой решётки n x m существует регулярный граф степени 4, который является её вершинным 1-расширением. Количество дополнительных рёбер в данном расширении равно n + m + 2. Рис. 1. Решётка 3 4 Для построения данного расширения необходимо выполнить следующие шаги: 1) 2) 3) Добавить рёбра между вершинами с метками (0,i) и (n - 1,i - 1), где i Е Е {1,...,m - 1}. Добавить рёбра между вершинами с метками (i, m - 1) и (i - 1, 0), где i Е Е {1, . . . , n - 1}. Добавить вершину и соединить её с (0, m - 1), (n - 1, m - 1), (n - 1, 0), (0, 0). Расширение, построенное по этой схеме, является вершинно-симметричным регулярным графом степени 4. Напомним, что регулярным называется граф, степени вершин которого равны, а вершинно-симметричным - граф, для каждой пары вершин u, v которого существует автоморфизм такой, что

Скачать электронную версию публикации