Вершинные и реберные расширения гиперкубов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Лобов Александр Андреевич

• Лобов Александр Андреевич
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Лобов Александр Андреевич

Введение

Глава 1. Вершинные расширения гиперкубов

1.1 Многослойные графы

1.2 Вершинные расширения 4-слойных графов

1.3 Вершинные расширения гиперкуба как 4-слойного графа

Глава 2. Рёберные расширения гиперкубов

2.1 Единственность минимального рёберного 1-расширения гиперкуба

2.2 МР-&-Р гиперкуба

Глава 3. Алгоритмы построения расширений

3.1 Задача построения суперграфов

3.2 Метод канонического представителя и матричные коды графов

3.3 Метод Рида-Фараджева

3.3.1 Дерево максимальных матричных кодов

3.3.2 Дерево минимальных матричных кодов

3.3.3 Построение частей графа и его суперграфов

3.4 Перебор сочетаний с ограничениями

3.5 Построение МВ-&-Р методом объединения изоморфных графов

3.6 Результаты вычислительных экспериментов

Заключение

Приложение А. Свидетельство о государственной регистрации программы

для ЭВМ Supgeng

Приложение Б. Свидетельство о государственной регистрации программы для ЭВМ FTConstructor

Введение диссертации (часть автореферата) на тему «Вершинные и реберные расширения гиперкубов»

Введение

Актуальность работы. В данной работе рассматриваются вершинные и рёберные ^-расширения гиперкубов. Основные определения теории графов приводятся согласно работе [9], а связанные с расширениями - по работе [8].

Граф G* называется вершинным ^-расширением (сокращённо В-^Р) и-вершинного графа О, если О вкладывается в каждый граф, получающийся из О* удалением k вершин.

Граф О* называется рёберным ^расширением (сокращённо Р-^Р) и-вершинного графа О, если О вкладывается в каждый граф, получающийся из О* удалением k рёбер.

Напомним, что граф О=( V, а) вкладывается в граф Н=( и, в), если существует такое инъективное отображение ф: V^и, которое удовлетворяет условию (V v1 ,у2eV)((Vх ,у2)^а^(ф( Vх) ,ф( у2))^в). При этом ф

называется вложением графа О в граф Н.

Задачи, связанные с исследованием вершинных и рёберных расширений берут своё начало с задачи построения вычислительной сети, устойчивой к отказу заданного количества элементов или связей.

В 1975 году Авиженис (А. Avizienis) в [59] описал два способа повышения надёжности вычислительной системы:

1. Предотвращение ошибок. Заключается в уменьшении вероятности ошибки за счёт увеличения надёжности каждого элемента системы в отдельности, что оказывает влияние на всю систему.

2. Введение избыточных структур в систему так, чтобы придать ей отказоустойчивость. Под отказоустойчивостью автор подразумевал способность противостоять ошибке и возможность продолжать работу

в присутствии этой ошибки. Отказоустойчивость подразделялась на два

уровня:

2.а. Полная отказоустойчивость - система продолжает работать в присутствии ошибок без существенной потери функциональных свойств.

2.б. Амортизация отказов - система продолжает работать в присутствии ошибок с частичной деградацией функциональных возможностей.

Для задачи полной отказоустойчивости в 1976 году в [71] Хейзом (J. P. Hayes) была предложена математическая модель отказа элементов системы, основанная на графах. Её назвали ^-отказоустойчивостью (k-fault tolerance), и, впоследствии, k-узловой или k-вершинной отказоустойчивостью [68] (k-node fault tolerance). В самой работе рассматривались и цветные графы - графы, где каждая вершина окрашена в какой-либо цвет (под цветом обычно подразумевается целое число - номер этого цвета). Вершины одинакового цвета соответствуют элементам одного типа. Например, первым цветом могут быть обозначены вычислительные устройства, а вторым -коммутаторы.

Также было введено понятие оптимальной k-вершинной отказоустойчивой реализации (optimal k-fault tolerant) - той, которая имеет наименьшее количество избыточных узлов и при этом среди всех таких реализаций имеет наименьшее количество рёбер. Связано это с минимизацией стоимости итоговой системы: обычно узел намного дороже связи между узлами.

В системе выйти из строя может не только узел, но и связь между узлами, поэтому позднее в [67] появилась задача k-рёберной отказоустойчивости (k-edge fault tolerance).

В такой модели элементы системы представляются вершинами, а связи между ними - рёбрами. Под отказом элемента подразумевается удаление соответствующей ему вершины из графа. Следует определить, что

подразумевается под термином граф в данной работе. Также приведём некоторые необходимые определения из теории графов.

Орграфом О называют упорядоченную пару множеств О=( V, а), где V - конечное непустое множество вершин, а а ^ V X V - отношение на множестве вершин, называемое отношением смежности. Элемент (и^)еа называется дугой из вершины и в вершину V.

Если отношение смежности графа О=( V, а) является антирефлексивным ((Vие V)((и, и)^а]) и симметричным

((Vи, Vе V)((и, V)еа ^ (V, и)еа)), то граф О называют неориентированным. Для каждой дуги в таком графе (и^ )еа её обратная дуга (V ,и) также принадлежит отношению смежности, поэтому можно отождествить их в одно ребро {и^ } = {V ,и}. Запись {и^ }е а означает, что граф О=(¥, а) содержит ребро {и^}, то есть (и ^)еал^ ,и)еа. При этом вершины и и V называются смежными. Степенью вершины и называется количество смежных вершин. Упорядоченная по невозрастанию последовательность степеней вершин графа называется его вектором степеней.

Далее под термином граф будет пониматься именно неориентированный граф.

Определим граф Н =( V, а и {{и ^}}) результатом операции добавления ребра {и^} (где и еV Лv еV) к графу О=( V,а). Аналогично можно определить операцию удаления ребра О — {и^ }=( V, а\ {{ и^}}).

Результатом удаления вершины V из графа О=(V, а) будет граф О — V = (и, 0), где и = V\{ V}, 0= аП V XV (то есть при удалении вершины из графа также удаляются все инцидентные ей рёбра).

В дальнейшем М. Б. Абросимовым было введено понятие рёберных и вершинных ^расширений, определения которых были даны ранее. Задача построения расширений, которую после В. Н. Салий обобщил до задачи

построения оптимальной реконструкции [48]. Приведём несколько связанных

с расширениями определений.

*

В-&-Р G п-вершинного графа G называется минимальным вершинным ^расширением (МВ-^Р), если количество вершин в нём равно п + k и количество рёбер минимально среди всех В-^Р графа G с тем же числом вершин.

*

Р-^Р G п-вершинного графа G называется минимальным рёберным ^расширением (МР-^Р), если количество вершин в нём равно п и количество рёбер минимально среди всех Р-^Р графа G с тем же числом вершин.

Частью графа G=(¥, а) называется граф Н =(и, в) такой, что и^ VЛ а^в. Если НФG, то такая часть называется собственной.

Если никакая собственная часть В-^Р G графа G=( V, а) не является

*

В-^Р, то G называется неприводимым вершинными ^расширением

соответственно (сокращённо НВ-^Р). Другими словами, каждый граф,

*

полученный удалением ребра из НВ-^Р G , не является В-^Р (Р-^Р) графа G.

Аналогично определяется неприводимое рёберное расширение (сокращённо НР-^Р).

Минимальное расширение всегда является неприводимым (обратное -неверно), так как в противном случае существовало бы другое расширение с меньшим числом рёбер.

Минимальное рёберное ^расширение графа существует не всегда, если рассматриваются только неориентированные графы. Примером графа, у которого не может быть рёберного расширения, является любой полный граф Кп=(у, V XV) ,И=п (где АХ В = {(а,Ь) | а е А,Ь е В} - декартово произведение множеств А и В) - в него невозможно добавить ребро. Минимальное расширение такого графа из-за фиксированного количества вершин будет находиться среди множества мультиграфов - графов, в

которых допускается существование кратных рёбер (нескольких рёбер между двумя вершинами).

В-к-Р графа всегда существует, так как у каждого графа есть тривиальное вершинное ^расширение.

Граф О+Кк называется тривиальным вершинным к-расширением

(ТВ-к-Р) графа О, где + - это операция соединения графов.

Соединением графов О=(V,а) и Н =(и ,0) называется граф О + Н = ( V ии ,аи0и( V xV )и(и X V)). Считается, что множества V и V не пересекаются, то есть и П V=ф .

Приведём пример описанных ранее типов расширений для 8-вершинного цикла С 8.

Под п-вершинным циклом понимается граф

Сп=( V = { 1,...,п}, а={{ 1, 2}, {2, 3},...,{и —1 ,п},{1 ,п}|), Сп = Рп+ {1 ,и}.

На рисунке 1 под пунктом а изображён сам 8-вершинный цикл, его ТВ-1-Р изображено под пунктом б, МВ-1-Р под пунктом в и НВ-1-Р, отличное от минимального, под пунктом г.

(а) (б) (в) (г)

Рисунок 1 - Цикл С8 (а), его ТВ-1-Р (б), МВ-1-Р (в) и НВ-1-Р (г) На рисунке 1 одинаковыми числами помечены подобные вершины. Вершины и и V графа О, а) называются подобными, если ф(и ) = V для какого-либо автоморфизма ф: V^V графа О - биективного отображения такого, что и^ }еV X V){и^ }еа<^ { ф( и) ,ф( V )}еа.

Множество автоморфизмов графа О обозначается Аи(О).

Покажем, что графы, изображённые на рисунке 1 под буквами б, в и г, являются расширениями 8-вершинного цикла. Для этого нужно для каждого класса подобных вершин удалить из графа одного представителя, и найти вложение цикла С8 в полученный граф. Такие вложения изображены на

рисунке 2. Под пунктом а показан пример удаления дополнительной вершины. В таком случае не удаляется ни одно исходное ребро графа, поэтому вложение всегда будет существовать (тождественное отображение является вложением). Под пунктами а и б показано вложение С4 в графы,

полученные из ТВ-^Р удалением по одной из подобных вершин, под в и г -для МВ-1-Р, изображённого на предыдущем рисунке под пунктом в, и под оставшимися пунктами д, е, ж и з - для НВ-1-Р, изображённого на рисунке 1 под пунктом г.

Рисунок 2 - Вложение 8-вершинного цикла в графы, полученные из его ТВ-1-Р (а, б), МВ-1-Р (в, г) и НВ-1-Р (д, е, ж, з) путём удаления одной

вершины

Достаточно простыми с аналитической точки зрения являются результаты о МВ-^Р и МР-^Р и-вершинной цепи Рп,п>3, для которых

результат был представлен в первых же работах: в [71] описаны МВ-^Р,

затем в [67] аналогичным образом описываются МР-&-Р цепи. Для случая k =1 единственными МР-1-Р и МВ-1-Р цепи являются циклы Сп и Сп+1

соответственно. Для случая k > 1 МР-^Р и МВ-^Р цепей являются МР-(k — 1)-Р или МВ-(k — 1)-Р циклов Сп и Сп+1 соответственно.

п-вершинной цепью Р называется граф Р =(V , а ), где V ={ 1,...,п}

п п 1 п ~п I п

и а={{ 1, 2}, {2, 3},..., {п— 1 ,п}}.

Аналитические результаты достаточно сложно получить без экспериментальных данных. Гораздо проще пытаться проанализировать уже имеющиеся частичные результаты. Например, знание некоторых МВ-^Р или МР-^Р для представителей какого-либо класса графов может дать возможность обобщить результат на весь класс графов. Развиваются способы решения задачи поиска МВ-^Р и МР-^Р графа с помощью вычислительных инструментов. Для этого используются различные подходы, но все они заключаются в построении множества графов, которое будет содержать все искомые объекты, и выбору из этого множества необходимых В-^Р и Р-^Р графа.

Графы G=(У,а) и Н =(и ,0) называются изоморфными, если существует такое биективное отображение ф: У^Ц, для которого выполняется и,у }еУ XV){и,у {ф(и) ,ф( V )}^Д При этом ф

называется изоморфизмом. Отношение изоморфизма разбивает множества всех графов на непересекающиеся подмножества, каждые два элемента которых изоморфны. Данные подмножества называются классами изоморфизма.

Также следует учесть то, что если граф G является В-^Р или Р-^Р графа Н, то любой изоморфный G граф тажке является В-^Р или Р-^Р графа, изоморфного Н (то же самое распространяется на МВ-ЫР, МР-^Р, НВ-^Р и НР-^Р), поэтому не имеет смысла рассматривать изоморфные графы, достаточно рассмотреть только одного представителя класса

изоморфизма. Для решения этой задачи при построении графов обычно используются результаты работ И. А. Фараджева [65], Рида (R. C. Read) [80], [63], [64], Маккея (B. McKay) [72], [73], [74] и других, описывающих подходы, применённые в уже реализованных эффективных генераторах (например для программы genreg [75]).

Рассмотрим примеры.

В работе [53] данные по МВ-1-Р и МР-1-Р были получены с помощью генератора [52], который строит все попарно неизоморфные графы с заданным вектором степеней. В самой работе рассматриваются циклы, для которых все МВ-1-Р и МР-1-Р будут иметь одинаковый вектор степеней, что и было использовано в работе. В общем случае необходимо определить вектора степеней, которые могут иметь минимальные расширения, найти все возможные графы с заданными векторами степеней и проверить их на соответствие расширению по определению (кратко - проверить на расширение).

В работах [51] и [13] использовались алгоритмы, берущие своё начало с алгоритма из [8], основанного на переборе суперграфов с 1, 2, 3 и т. д. дополнительными рёбрами до тех пор, пока не найдётся нужное расширение графа.

Граф G называется суперграфом графа H, если граф H является частью графа G.

Для решения данной задачи был применён метод исключения изоморфных копий, который получилось применить при особом способе кодирования графа, который будет рассмотрен в данной работе.

С помощью программного комплекса [24] были построены все МВ-1-Р для графов с числом вершин до 9 включительно [12], все МР-1-Р для графов с количеством вершин до 10 включительно [50], а также МР-2-Р, МР-3-Р и МР-4-Р для графов с количеством вершин, не превышающим 9.

Существуют работы, направленные на изучение расширений цветных графов и способов их программного построения.

Вершинной (рёберной) раскраской графа О=(V, а) в к цветов С называется сюръективное отображение с: V ^С (с :а^С), а граф, для которого задана раскраска, называется цветным.

Под цветами С обычно понимают какое-либо множество с к элементами, например, С = {0,...,к — 1}.

Цветные графы рассматривались в первой работе [71], в которой была введена графовая модель отказоустойчивости: было рассмотрено В-1-Р 3-х уровневых деревьев специального вида (те вершины, что располагаются на одинаковом уровне, окрашены в один цвет, а те, которые находятся на разных уровнях, - в разные).

В работах [79], [45], [46], [44] и [47] рассматриваются расширения для цветных звёздных графов и цветных полных графов. Для получения экспериментальных данных использовалась программа построения расширений цветных графов [42], которая использует метод построения цветных графов без проверки на изоморфизм [43].

Графы, для которых можно построить расширение программным способом с помощью рассмотренных ранее алгоритмов и программ, имеют небольшое число вершин, поэтому важны и теоретические исследования. Опишем некоторые из них.

Есть ряд работ, в которых изучались графы особого вида: в [17] изучались функциональные графы, в [6], [7], [18], [19], [20] и [22] - деревья особого вида, в [21] - объединения полных графов, [11] - гусениц (класс деревьев особого вида).

Предполным и-вершинным графом называется граф, у которого есть вершина степени и — 1.

Для предполных графов найдена процедура построения их МВ-k-P, которая представлена в [1]. Также были результаты и о МР-k-P некоторых предполных графов в [2] и [4].

Для полного графа K его ТВ-k-P K + K, = K . является

^ г т п n k n +k

единственным МВ-k-P. Кроме этого были получены точные оценки количества дополнительных рёбер в турнирах - ориентациях полного графа [40], ориентациях циклов и цепей [41]. Расширения ориентированных графов специального вида изучались и в других работах [10].

Орграф G=(V, а) называется ориентацией графа H=(V ,0), если

(V u,v gV )[{u,v u,v )^af\(v ,u )£a\/(v,u )еал( u,v )£а)). То есть

орграф G получается из графа H путём замены каждого его ребра {u,v} на одну из дуг (u ,v) или (v, u).

Так как сама задача связана с построением отказоустойчивой вычислительной системы, то объектом исследования обычно являются графы, которые описывают её топологии. Например, циклы, многомерные решётки, торы и гиперкубы.

В [71] описано МВ-k-P цикла и процедуры для их построения, а также в [67] описаны МР-k-P цикла. В [83] также изучались расширения цикла, так как цикл является основой для сети Token Ring. В целом, вопрос количества попарно неизоморфных МВ-k-P и МР-k-P цикла не решён, так как количество таких расширений достаточно велико и быстро растёт с увеличением количества вершин в цикле [53].

Декартовым произведением графов G=(V, а) и H =(U, в) называется граф G X H = ( W, у), где

• w = VxU=(u,v) | ugUлvgV).

Графы T =C X...XC и M = P X...XP называются

n V'nd n1 nd nV'nd n1 nd

d-мерным тором и d-мерной решёткой соответственно.

Топологии d-мерных решёток и торов широко используются в проектировании коммуникационных сетей суперкомпьютеров: 3-мерный тор в Cray Gemini [58] и Extoll [77], сеть Ангара с топологией 4-мерного тора [49], сети суперкомпьютеров IBM BlueGene/Q с топологией 5-мерного тора [69], сети Tofu [54], Tofu2 [55], TofuD [56] суперкомпьютеров компании Fujitsu с топологией 6-мерного тора. В случае каких-либо отказов некоторые сети (например, Fugaku [57]) продолжают работу в виде решётки той же размерности.

В [67] было сделано предположение, что МР-1-Р d-мерной решётки

M - это d-мерный тор T , однако в [78] показано, что для

n1 > ■■■ > nd n 1 > ■■■ ,nd

решёток существует Р-1-Р с меньшим числом дополнительных рёбер и дана схема его построения.

Циркулянтным графом называется граф

CN(S) = ({0, 1,...,N-1},({u,v} | (3/eS)|u-v|=i(modN)}).

Построение В-&-Р для произвольного циркулянтного графа описано в [81]. Циркулянтный граф интересен тем, что он является регулярным и симметричным.

Граф называется регулярным, если все его вершины имеют одинаковую степень.

В [62] Для d-мерных решёток была представлена схема построения В-&-Р, которое является циркулянтным графом C ^ d + (S), где

S = U (i ,i +1,... ,i+[ 2 J}. Также в данной работе рассматривались

i e{1, 2, 22,..., 2d-1} 2

расширения В-1-Р 2-мерных торов.

В работах [14] и [15] применяется похожий способ построения В-1-Р, который для произвольного «-вершинного графа G = ({ V1,..., ^}

заключается в объединении графов G =G °и... UGИ. В работе считается, что

^), гДе ф ) = ■

v ., если j > i

j J

v . л, иначе

j-1'

В данном случае очень легко найти вложение. Это отображения ф.

Под действием или применением инъективного отображения p: V—> U к графу G=( V, а) будем подразумевать операцию получения другого графа p(G) = H = ( Imp,0), где Imp - это множество образов, в определяется следующим образом: в ={(ф(v 1), p(v2)) | (v 1 ,v2)Ga}. При

этом, очевидно, полученный граф H будет изоморфен графу G.

Данный метод был применён к различным классам графов, в том числе к решёткам и торам. Расширения, которые получаются, не всегда являются минимальными и очень сильно зависят от порядка вершин графа, однако при подобном построении очень легко найти вложение после удаления вершин.

N-мерным гиперкубом или, кратко, N-кубом является граф Qn = { V ={0,1 }N,a={{ u,v} | h (u,v ) = 1}, где h - расстояние Хемминга

(количество различных позиций, в которых отличаются два вектора одной длины). То есть V - это множество всех возможных векторов длины N, элементами которого являются 0 и 1, а ребро между двумя вершинами ставится только в том случае, если метки вершин отличаются ровно в одной позиции.

Топология гиперкуба широко использовалась в построении суперкомпьютеров. С начала 1997 года до середины 2003 года по крайней мере 10 суперкомпьютеров из рейтинга 500 самых мощных суперкомпьютеров имели топологию гиперкуба [76]. Данную топологию использовали в своих решениях компании nCUBE [70] и Intel [84] (iPSC/860).

В настоящий момент в связи с ростом числа узлов в суперкомпьютерах применяются его производные: обобщённый гиперкуб и расширенный обобщённый гиперкуб [16], основанный на использовании квазиполных графов.

Несмотря на это, по состоянию на ноябрь 2022 года в списке 500 мощнейших суперкомпьютеров присутствует суперкомпьютер EAGLE с топологией 8-куба, запущенный в 2018 году.

N-куб состоит из двух (N — 1 )-кубов, у которых соответствующие вершины соединены, поэтому N-куб также можно задать следующим

способом: qn=qn — 1X P2.

Следует отметить, что N-куб является N-мерным тором Qn = T2 2 2 и N-мерной решёткой Qn = M2 2 поэтому к нему можно применить

имеющиеся результаты для данных классов графов.

В работе [81] была представлена схема построения В-k-F для циркулянтного графа, которую применили для N-куба. Далее в [62] данная схема была улучшена, но при этом в полученных по схеме расширениях для гиперкуба дополнительных рёбер больше, чем в ТВ-k-R

В [67] была описана схема построения МР-1-Р N-куба для произвольного N, которая совпала с появившейся позднее схемой построения Р-1-Р многомерных решёток [78].

Целью данной работы является исследование вершинных и рёберных расширений гиперкубов. Особый интерес представляют следующие задачи:

1. Поиск В-^Р гиперкубов с числом рёбер меньше, чем у ТВ-k-R

2. Определение единственности МР-1 -Р гиперкубов.

3. Поиск МР-к-Р и Р-^Р гиперкубов для k > 1.

Результаты, выносимые на защиту:

1. Найдена схема построения В-1-Р и В-2-Р с количеством рёбер на 1 и 2 меньше, чем у ТВ-1-Р и ТВ-2-Р соответственно, которая применима ко всем двудольным графам, за исключением полных двудольных графов.

2. Описаны все возможные попарно неизоморфные В-1-Р и В-2-Р для гиперкубов, которые могут быть построены по данным схемам, доказано, что построенные по предложенной схеме В-1-Р являются неприв одимыми.

3. Доказана единственность МР-1 -Р гиперкубов.

4. Предложены способы кодирования графа, которые позволяют использовать метод канонического представителя для исключения изоморфных копий при построении суперграфов и частей графа, а как же и производный от него метод Рида-Фараджева.

5. Предложен алгоритм построения МВ-&-Р на основе объединения графов.

Научная новизна. Все выносимые на защиту результаты являются новыми.

Теоретическая и практическая значимость. Результаты имеют в основном теоретический характер. Реализованные программы для ЭВМ, основанные на описанных в данной работе алгоритмах, можно использовать для построения отказоустойчивых вычислительных систем и суперграфов и частей заданного графа.

Степень достоверности и апробация работы. Было принято участие в следующих конференциях:

1. VIII Международная научная конференция «Компьютерные науки и информационные технологии» памяти А. М. Богомолова, СГУ, Саратов, 2018.

2. Международная конференция «Ломоносов-2018», МГУ, Москва, 2018.

3. 17-я международная конференция «Сибирская научная школа-семинар «Компьютерная безопасность и криптография»» Sibecrypt'18, Томск, 2018.

4. XIII Международный семинар «Дискретная математика и её приложения» имени академика О.Б. Лупанова, МГУ, Москва, 2019.

5. 18-я международная конференция «Сибирская научная школа-семинар «Компьютерная безопасность и криптография»» Sibecrypt'19, Томск, 2019.

6. Международная конференция «Ломоносов-2021», МГУ, Москва, 2021.

7. IX Международная научная конференция «Компьютерные науки и информационные технологии» памяти А. М. Богомолова, СГУ, Саратов, 2021.

8. 21-я международная конференция «Сибирская научная школа-семинар «Компьютерная безопасность и криптография»» имени Г. П. Агибалова Sibecrypt'22, Красноярск, 2022.

Публикации. По теме диссертации было опубликовано 17 работ, из которых 7 выпущены в изданиях из списка ВАК (все статьи опубликованы в изданиях, относящихся к категории К1):

• В ВАК, Scopus и WebOfScience входят 5 работ: [29], [30], [31], [35], [36].

• 2 только в ВАК и РИНЦ: [32] и [38].

• Только в РИНЦ входят 5 работ: [25], [26], [28], [33], [37].

• Не индексируются 3 работы: [27], [34], [39].

• 2 свидетельства о регистрации программы для ЭВМ: [23] и [24]. Зарегистрированные программы для ЭВМ использовались для

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

Программа для построения всех попарно неизоморфных суперграфов Supgeng [23] (свидетельство приведено в приложении А) и программный комплекс БТСош^иСш [24] (свидетельство приведено в приложении Б) для построения всех МВ-&-Р и МР-&-Р заданного графа с использованием техник исключения изоморфных копий.

Личный вклад. Все выносимые на защиту результаты получены соискателем лично.

Научному руководителю Абросимову М. Б. принадлежит постановка темы диссертации и участие в проверке и корректировке статей.

Следует конкретизировать вклад автора в 4-х статьях с соавторами, отличными от научного руководителя:

В статье [29] «Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей» автору принадлежат результаты, касающиеся способа кодирования графа, при котором возможно построение суперграфов с применением техник построения графов без проверки на изоморфизм.

В статье [30] «Построение минимальных рёберных расширений графа без проверки на изоморфизм» результатом автора является способ построения суперграфов без проверки на изоморфизм. В данной статье указывается на возможность использования данных наработок для решения задачи построения минимальных рёберных расширений графа.

В статье [31] «Построение всех неизоморфных суперграфов без проверки на изоморфизм» результатом автора является описание способа построения суперграфов. Фактически, статья объединяет все предыдущие наработки, касающиеся данной темы.

В статье [32] «Построение минимальных вершинных расширений графа методом Рида-Фараджева» автору принадлежат результаты, связанные со способом кодирования графа и деревом кодов, позволяющем применять

технику исключения изоморфных копий Рида-Фараджева при построении суперграфов.

То есть основные результаты автора были связаны со способом кодирования графов, позволяющий строить суперграфы и вопросы, непосредственно связанные с их построением.

В программе БТСош^иСш автор занимался разработкой кода, связанного с проверкой графа на каноничность, и вспомогательными утилитами.

Код программы Supgeng был написан автором полностью. Объем и структура работы. Работа состоит из введения, трёх глав, заключения, списка литературы и двух приложений.

В первой главе «Вершинные расширения гиперкубов» указываются теоретические результаты, полученные при поиске схем построения вершинных расширений гиперкубов:

1. Определены и описаны классы ^-слойных графов.

2. Приведены схемы построения В-1-Р и В-2-Р 4-слойных графов.

3. Посчитано количество попарно неизоморфных В-1-Р и В-2-Р гиперкубов, полученных по схемам построения расширений 4-слойных графов.

4. Доказана неприводимость построенного по предложенной схеме В-1-Р гиперкуба.

Во второй главе «Рёберные расширения гиперкубов» представлены результаты по рёберным расширениям гиперкубов:

1. Приведена схема построения МР-1-Р гиперкуба и доказано, что данное МР-1-Р для гиперкуба единственно с точностью до изоморфизма.

2. Выдвинуто предположение о существовании некоторых МР-&-Р, которые являются регулярными графами.

В третьей главе «Алгоритмы построения расширений» приведены и обоснованы алгоритмы, используемые для решения задач, касаемых В-&-Р:

1. Приведены способы кодирования графа, позволяющие использовать техники исключения изоморфных копий для построения суперграфов и частей заданного графа.

2. Описаны и обоснованы алгоритмы построения всех МР-&-Р и МВ-&-Р заданного графа с использованием построения суперграфов и частей без проверки на изоморфизм.

Список литературы диссертационного исследования кандидат наук Лобов Александр Андреевич, 2024 год

Список литературы

[1] Абросимов, М. Б. Минимальные к-расширения предполных графов / М. Б. Абросимов // Известия высших учебных заведений. Математика. - 2003. - № 6. - С. 3-11.

[2] Абросимов, М. Б. К вопросу о реберных расширениях предполных графов / М. Б. Абросимов // Компьютерные науки и информационные технологии : Материалы Международной научной конференции, Саратов, 01-04 июля 2009 года. - 2009. - С. 3-5.

[3] Абросимов, М. Б. О вычислительной сложности расширений графов / М. Б. Абросимов // Прикладная дискретная математика. Приложение. -

2009. - № 1. - С. 94-95.

[4] Абросимов, М. Б. Минимальные реберные расширения некоторых предполных графов / М. Б. Абросимов // Прикладная дискретная математика. - 2010. - № 1(7). - С. 105-117.

[5] Абросимов, М. Б. О сложности некоторых задач, связанных с расширениями графов / М. Б. Абросимов // Математические заметки. -

2010. - Т. 88, № 5. - С. 643-650.

[6] Абросимов, М. Б. О нижней оценке числа рёбер минимального рёберного 1-расширения сверхстройного дерева / М. Б. Абросимов // Изв. Сарат. Ун-та. Нов. Сер. Сер.: Математика. Механика. Информатика. - 2011. - Т. 11, вып. 3, ч. 2. - С. 111-117.

[7] Абросимов, М. Б. О числе дополнительных рёбер минимального вершинного 1-расширения сверхстройного дерева / М. Б. Абросимов // Изв. Сарат. Ун-та. Нов. Сер. Сер.: Математика. Механика. Информатика. - 2012. - Т. 12, вып. 2. - С. 103-113.

[8] Абросимов, М. Б. Графовые модели отказоустойчивости / М. Б. Абросимов // Саратов: Издательство Саратовского университета.

- 2012. - 192 с.

[9] Богомолов, А. М. Алгебраические основы теории дискретных систем / А. М. Богомолов, В. Н. Салий // М.: Наука. - 1997. - 368 с.

[10] Гавриков, А. В. Т-неприводимые расширения объединений некоторых типов орграфов / А. В. Гавриков // Прикладная дискретная математика.

- 2013. - № 4 (22). - С. 47-56.

[11] Кабанов, М. А. Об отказоустойчивых реализациях графов / М. А. Кабанов // Теоретические задачи информатики и ее приложений.

- Саратов: Изд-во Сарат. ун-та, 1997. - вып. 1. - С. 50-58.

[12] Камил, И. А. К. Вычислительный эксперимент по построению отказоустойчивых реализаций графов с числом вершин до 9 / И. А. К. Камил // International Journal of Open Information Technologies. -2020. - Т. 8, № 9. - С. 43-47.

[13] Камил, И. А. К. Методы и алгоритмы разработки вычислительных систем, устойчивых к отказам элементов, без проверки на изоморфизм : дис. ... канд. техн. наук : 05.13.18 / Камил Ихаб Абдулджаббар Камил. -Томск: 2021. - 121 с.

[14] Каравай, М. Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. I. Одно-отказоустойчивые структуры / М. Ф. Каравай // Автоматика и телемеханика. - 2004. - № 12. - С. 159-177.

[15] Каравай, М. Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. II. Решетки и k-отказоустойчивость / М. Ф. Каравай // Автоматика и телемеханика. - 2005. - № 2. - С. 175-189.

[16] Каравай, М. Ф. Расширенный обобщенный гиперкуб как отказоустойчивая системная сеть для многопроцессорных систем /

М. Ф. Каравай, В. С. Подлазов // Управление большими системами: сборник трудов. - 2013. - № 45. - С. 344-371.

[17] Киреева, А. В. Отказоустойчивость в функциональных графах / А. В. Киреева // Упорядоченные множества и решетки. - 1995. -Саратов: Изд-во Сарат. ун-та. - вып. 11. - С. 32-38.

[18] Комаров, Д. Д. Минимальные рёберные расширения пальм / М. Б. Абросимов, Д. Д. Комаров // Изв. Сарат. Ун-та. Нов. Сер. Сер.: Математика. Механика. Информатика. - 2013. - Т. 13, вып. 3. -С. 99-104.

[19] Комаров, Д. Д. Минимальные вершинные 1-расширения пальм / М. Б. Абросимов, Д. Д. Комаров // Изв. Сарат. Ун-та. Нов. Сер. Сер.: Математика. Механика. Информатика. - 2014. - Т. 14, вып. 2. -С. 233 241.

[20] Комаров, Д. Д. Верхняя оценка количества дополнительных рёбер минимальных рёберных 1-расширений сверхстройных деревьев / Д. Д. Комаров // Прикладная дискретная математика. - 2015. - 4(30). -С. 91-99.

[21] Курносова, С. Г. Т-неприводимые расширения объединений полных графов / С. Г. Курносова // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. - 2005. - Т. 5, вып. 1. - С. 107-115.

[22] Курносова, С. Г. Т-неприводимые расширения полных бинарных деревьев / С. Г. Курносова // Вестн. Томск. гос. ун-та. Приложение. -2005. - № 14. - С. 158-160.

[23] Лобов А. А., Абросимов М. Б. Свидетельство о государственной регистрации программы для ЭВМ № 2020610497 Российская Федерация. GenSupg : № 2019666671. - заявл. 19.12.2019 : опубл. 15.01.2020

[24] Лобов А. А., Камил И. А. К., Судани Х. Х. К., Абросимов М. Б. Свидетельство о государственной регистрации программы для ЭВМ

№ 2020614773 Российская Федерация. Построение оптимальных отказоустойчивых реализаций графов FTConstructor : № 2020612581. -заявл. 10.03.2020 : опубл. 24.04.2020

[25] Лобов, А. А О вершинном 1-расширении гиперкуба / А. А. Лобов, М. Б. Абросимов // Компьютерные науки и информационные технологии : Материалы Международной научной конференции, Саратов, 02-03 июля 2018 года. - Саратов: ИЦ "Наука". - 2018. -С. 249-251.

[26] Лобов, А. А. О минимальном рёберном 1-расширении гиперкуба / А. А. Лобов, М. Б. Абросимов // Прикладная дискретная математика. Приложение. - 2018. - № 11. - С. 109-111.

[27] Лобов, А. А. Оценка количества дополнительных рёбер в минимальном вершинном 1-расширении подкласса двудольных графов [Электронный ресурс] / Материалы Международного молодежного научного форума 1 «Л0М0Н0С0В-2018». - Отв. ред. И. А. Алешковский, А. В. Андриянов, Е. А. Антипов // М.: МАКС Пресс. - 2018. - 1 электрон. опт. диск (DVD-ROM); 12 см - Систем. требования: ПК с процессором 486+; Windows 95; дисковод DVD-ROM; Adobe Acrobat Reader. — 1450 Мб. — 11000 экз. ISBN 978-5-317-05800-5.

[28] Лобов, А. А. Построение минимальных расширений графа методом канонических представителей / А. А. Лобов, И. А. К. Камил, Х. Х. К. Судани, М. Б. Абросимов // Прикладная дискретная математика. Приложение. - 2019. - № 12. - С. 179-182.

[29] Лобов, А. А. Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей / А. А. Лобов, М. Б. Абросимов, И. А. К. Камил // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. - 2019. - Т. 19, № 4. - С. 479-486.

[30] Лобов, А. А. Построение минимальных рёберных расширений графа без проверки на изоморфизм / A. A. Лобов, Х. Х. К. Судани, М. Б. Абросимов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. - 2020. - Т. 20, вып. 1. - С. 105-115.

[31] Лобов, А. А. Построение всех неизоморфных суперграфов без проверки на изоморфизм / А. А. Лобов, И. А. К. Камил, Х. Х. К. Судани, М. Б. Абросимов // Прикладная дискретная математика. - 2020. - № 48.

- С. 82-92.

[32] Лобов, А. А. Построение минимальных вершинных расширений графа методом Рида-Фараджева / А. А. Лобов, И. А. К. Камил, М. Б. Абросимов // International Journal of Open Information Technologies. - 2020. - Vol. 8, № 4. - P. 54-58.

[33] Лобов, А. А. О вершинных 2-расширениях 4-слойных графов / М. Б. Абросимов, Лобов А. А. // Саратов : Издат. центр «Наука». - 2021.

- С. 97-99.

[34] Лобов, А. А. О вершинном 1-расширении некоторых торов [Электронный ресурс] / Материалы Международного молодежного научного форума 2 «Л0М0Н0С0В-2021». - Отв. ред. И. А. Алешковский, А. В. Андриянов, Е. А. Антипов, Е. И. Зимакова // М.: МАКС Пресс. - 2021. - 1 электрон. опт. диск (DVD-ROM); 12 см. -2000 экз. ISBN 978-5-317-06593-5.

[35] Лобов, А. А. О единственности минимального рёберного 1-расширения гиперкуба Q4 / А. А. Лобов, М. Б. Абросимов // Прикладная дискретная математика. - 2022. - № 58. - С. 84-93.

[36] Лобов, А. А. Вершинные расширения 4-слойных графов и гиперкубов / А. А. Лобов, М. Б. Абросимов // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. - 2022. -Т. 22, № 4. - С. 536-548.

[37] Лобов, А. А. О единственности минимального рёберного 1-расширения гиперкуба / А. А. Лобов, М. Б. Абросимов // Прикладная дискретная математика. Приложение. - 2022. - № 15. - С. 110-112.

[38] Лобов, А. А. Единственность минимального рёберного 1-расширения гиперкубов / А. А. Лобов // International Journal of Open Information Technologies. - 2023. - Vol. 11, № 9. - P. 28-32.

[39] Лобов, А. А. О генерации графов, содержащих заданный подграф / А. А. Лобов, М. Б. Абросимов // Материалы XIII Международного семинара «Дискретная математика и её приложения», имени академика О. Б. Лупанова (Москва, МГУ, 17-22 июня 2019 г.) / Под редакцией О. М. Касим-Заде. - М.: Изд-во МГУ, 2019. - С. 223-226.

[40] Моденова, О. В. О точных оценках числа дополнительных дуг минимального вершинного 1-расширения турнира / О. В. Моденова, М. Б. Абросимов // Прикладная дискретная математика. Приложение. -2015. - № 8. - С. 111-113.

[41] Моденова, О. В. О минимальных 1-расширениях ориентаций цепей / О. В. Моденова, М. Б. Абросимов // Прикладная дискретная математика. - 2017. - № 38. - С. 89-94.

[42] Разумовский П. В., Абросимов М. Б. Свидетельство о государственной регистрации программы для ЭВМ № 2021662022 Российская Федерация. ColorGraphExtensions : № 2021661289 : заявл. - 20.07.2021 : опубл. 20.07.2021

[43] Разумовский, П. В. Построение цветных графов без проверки на изоморфизм / П. В. Разумовский, М. Б. Абросимов // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. - 2021. - Т. 21, № 2. - С. 267-277.

[44] Разумовский, П. В. О поиске минимальных вершинных расширений цветного неориентированного графа / П. В. Разумовский,

М. Б. Абросимов // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2021. - № 4(60). - С. 106-117.

[45] Разумовский, П. В. Схемы построения минимальных вершинных 1-расширений полных двухцветных графов / П. В. Разумовский, М. Б. Абросимов // Прикладная дискретная математика. Приложение. -2021. - № 14. - С. 165-168.

[46] Разумовский, П. В. Минимальные вершинные расширения цветных полных графов / П. В. Разумовский, М. Б. Абросимов // Вестник ЮжноУральского государственного университета. Серия: Математика. Механика. Физика. . - 2021. - Т. 13, № 4. - С. 77-89.

[47] Разумовский, П. В. Минимальные расширения цветных звездных графов / П. В. Разумовский, М. Б. Абросимов // International journal of open information technologies. - 2022. - Т. 10, № 2. - С. 1-7.

[48] Салий, В. Н. Оптимальные реконструкции графов / В. Н. Салий // Саратов : Изд-во Сарат. ун-та. - 2008. - С. 59-65.

[49] Симонов, А. С. Высокоскоростная сеть Ангара: архитектура и результаты применения / А. С. Симонов, И. А. Жабин, Е. Р. Куштанов [и др.] // Вопросы кибербезопасности. - 2019. - № 4(32). - С. 46-53.

[50] Судани, Х. Х. К. Рёберно-отказоустойчивые расширения 8-, 9- и 10-вершинных графов / Х. Х. К. Судани // International Journal of Open Information Technologies. - 2020. - Т. 8, № 8. - С. 46-50.

[51] Судани, Х. Х. К. Модели и алгоритмы построения оптимальных рёберных отказоустойчивых реализаций вычислительных систем : дис. ... канд. техн. наук : 05.13.18 / Судани Хайдер Хуссейн Карим. -Томск: 2021. - 149 с.

[52] Сухов, С. А. Свидетельство о государственной регистрации программы для ЭВМ № 2016610073 Российская Федерация. DSR Generator : № 2015660808 : заявл. - 10.11.2015 : опубл. 11.01.2016

[53] Сухов, С. А. О количестве минимальных 1-расширений циклов с числом вершин до 26 и 28 / С. А. Сухов, М. Б. Абросимов, Г. Бринкман // Компьютерные науки и информационные технологии : Материалы Международной научной конференции, Саратов, 30 июня -02 июля 2016 года - Саратов: ИЦ "Наука". - 2016. - С. 9-11.

[54] Ajima, Y. Tofu: A 6D Mesh/Torus Interconnect for Exascale Computers / Y. Ajima, S. Sumimoto, T. Shimizu // IEEE Computer. - 2009. - Vol. 42, № 11. - P. 36-40.

[55] Ajima, Y. Tofu Interconnect 2: System-on-Chip Integration of HighPerformance Interconnect / Y. Ajima, T. Inoue, S. Hiramoto // International Supercomputing Conference / Springer. - 2014. - P. 498-507.

[56] Ajima, Y. The Tofu Interconnect D / Y. Ajima, K. Takahiro, T. Okamoto et.al. // 2018 IEEE International Conference on Cluster Computing (CLUSTER). IEEE. - 2018. - P. 646-654.

[57] Ajima, Y. High-dimensional Interconnect Technology for the K Computer and the Supercomputer Fugaku [Электронный ресурс] / Y. Ajima // URL: https://www.fujitsu.com/global/documents/about/resources/publications/ technicalreview/topics/article005.pdf (дата обращения 02.04.2023). - 2020.

[58] Alverson, R. The Gemini System Interconnect / R. Alverson, D. Roweth, L. Kaplan // 2010 18th IEEE Symposium on High Performance Interconnects. - 2010. - P. 83-87.

[59] Avizienis, A. Fault-tolerance and fault-intolerance : Complementary approaches to reliable computing / A. Avizienis // Proc. Intern. Conf. on Reliable Software. - 1975. - P. 458-464.

[60] Biggs, N. L. Distance-Transitive Graphs / N. L. Biggs // Cambridge University Press. - 1993. - P. 155-163.

[61] Brinkmann, G. Isomorphism rejection in structure generation programs / G. Brinkmann // Discrete Mathematical Chemistry, DIMACS Series in

Discrete Mathematics and Theoretical Computer Science. - 2000. - V. 51. -P. 25-38.

[62] Bruck, J. Fault-Tolerant Meshes and Hypercubes with Minimal Numbers of Spares / J. Bruck, R. Cypher, C.-T. Ho // IEEE Transactions on computers. -1993. - Vol. 42, № 9. - P. 1089-1104.

[63] Colburn, C. J. Orderly algorithms for generating restricted classes of graphs / C. J. Colburn, R. C. Read // Journal of Graph Theory. - 1979. -Vol. 3. - P. 187-195.

[64] Colburn, C. J. Orderly algorithms for graph generation / C. J. Colburn, R. C. Read // Intern. J. Computer Math. - 1979. - Sec. A.7. - P. 167-172.

[65] Faradzhev, I. A. Constructive enumeration of combinatorial objects / I. A. Faradzhev // Colloques internationaux C.N.R.S. №260, Problemes Combinatoires et Theorie des Graphes, Orsay. - 1976. - P. 131-135.

[66] Harary, F. A survey of the theory of hypercube graphs / F. Harary, J. P. Hayes, H.-J. Wu // Computers & Mathematics with AppBlications. -1988. - 15 (4). - P. 277-289.

[67] Harary, F. Edge fault tolerance in graphs / F. Harary, J. P. Hayes // Networks.

- 1993. - Vol. 23. - P. 135-142.

[68] Harary, F. Node fault tolerance in graphs / F. Harary, J. P. Hayes // Networks.

- 1996. - Vol. 27. - P. 19-23.

[69] Haring, R. A. The IBM Blue Gene/Q Compute Chip / R. Haring, M. Ohmacht, T. W. Fox et. al. // IEEE Micro. - 2012. - 32(2). - P. 48-60.

[70] Hayes, J. A Microprocessor-based Hypercube Supercomputer / J. Hayes, T. N. Mudge, Q. F. Stout, S. Colley // IEEE Micro. - 1986. - 6(5). - P. 6-17.

[71] Hayes, J. P. A graph model for fault-tolerant computing system / J. P. Hayes // IEEE Trans. Comput. - 1976. - Vol. 25, № 9. - P. 875-884.

[72] McKay, B. D. Practical graph isomorphism / B. D. McKay // Congr. Numer.

- 1980. - Vol. 30. - P. 45-87.

[73] McKay, B. D. Isomorphism-free exhaustive generation / B. D. McKay // Journal of Algorithms. - 1998. - Vol. 26. - P. 306-324.

[74] McKay, B. D. Practical Graph Isomorphism, II / B. D. McKay, A. Piperno // Journal of Symbolic Computation, 60. - 2014. - P. 94-112.

[75] Meringer, M. Fast Generation of Regular Graphs and Construction of Cages / M. Meringer // Journal of Graph Theory. - 1999. - № 30. -P. 137-146.

[76] Meuer, H. TOP 500 The List [Электронный ресурс] / H. Meuer, E. Strohmaier, J. Dongarra, H. Simon // URL: https://www.top500.org (дата обращения 26.03.2023).

[77] Neuwirth, S. Scalable communication architecture for network-attached accelerators / S. Neuwirth., D. Frey, M. Nuessle, U. Bruening // High Performance Computer Architecture (HPCA), 2015 IEEE 21st International Symposium / IEEE. - 2015. - P. 627-638.

[78] Ray-Shung, C. 1-edge fault-tolerant designs for meshes / C. Ray-Shung, H. Lih-Hsing // Parallel Processing Letters. - 1994. - Vol. 4, № 4. -P. 385-389.

[79] Razumovsky, P. V. The search for minimal edge 1-extension of an undirected colored graph / P. V. Razumovsky // Izvestiya of Saratov University. New Series. Series: Mathematics. Mechanics. Informatics. - 2021. - Vol. 21, № 3. - P. 400-407.

[80] Read, R. C. Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations / R. C. Read // Annals of Discrete Mathematics. - 1978. - Vol. 2. - P. 107-120.

[81] Shantanu, D. Designing fault-tolerant systems using automorphisms / D. Shantanu, J. P. Hayes // Journal of Parallel and Distributed Computing. -1991. - 12(3). - P. 249-268.

[82] Sloane, N.J.A. The on-line encyclopedia of integer sequences [Электронный ресурс] // URL:https://oeis.org (дата обращения

23.02.2023).

[83] Sung, T. Y. Optimal k-fault-tolerance network for token rings / T. Y. Sung, T. Y. Ho, C. P. Chang, L. H. Hsu // J. Inform. Science and Engineering. -2000. - № 16. - P. 381-390.

[84] Wang, J.-C. Scheduling of Unstructured Communication on the Intel iPSC/860 [Электронный ресурс] / J.-C. Wang, S. Ranka // School of Computer and Information Science // URL:https://surface.syr.edu/lcsmith_other/48 (дата обращения 15.04.2023).

Приложение А Свидетельство о государственной регистрации программы для ЭВМ Supgeng

В данном приложении приведено изображение свидетельства о регистрации государствнной программы для ЭВМ «Supgeng», которая может генерировать попарно неизоморфные суперграфы заданного графа.

Приложение Б Свидетельство о государственной регистрации программы для ЭВМ FTConstructor

В данном приложении приведено отсканированное изображение свидетельства о регистрации государствнной программы для ЭВМ «Построение оптимальных отказоустойчивых реализаций графов БТСош^иСот».

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