Schemes for constructing minimal vertex 1-extensions of complete bicolored graphs.pdf С точки зрения безопасности вычислительных систем большое значение имеет их надёжность, одним из аспектов которой является отказоустойчивость. Существуют разные математические модели отказоустойчивости. В данной работе рассматривается модель, предложенная Джоном Хейзом [1]. Техническая система моделируется графом. Элементам системы соответствуют вершины графа, а связям между элементами - рёбра (или дуги, если связи не являются симметричными). Если элементы имеют разный тип, то соответствующим им вершинам графа приписываются метки типа или цвета. Таким образом, моделью технической системы является граф с вершинами разного цвета, или цветной граф. Основные определения теории графов используются в соответствии с [2]. Будем рассматривать неориентированные графы. Понятия минимальных расширений для графов даются в соответствии с [1, 3]. Определение 1. Граф G* = (V *, a*, f*) называется минимальным вершинным k-расширением n-вершинного i-цветного графа G = (V, a,f), если выполняются следующие условия: 1) граф G* является вершинным k-расширением цветного графа G, то есть граф G можно вложить с учётом цветов в каждый граф, получающийся из графа G* удалением любой его вершины вместе с инцидентными рёбрами; 2) граф G* содержит n + ik вершин, то есть |V*| = |V| + ik; 3) a* имеет минимальную мощность среди всех графов, удовлетворяющих условиям 1 и 2. В работе [1] рассматривается задача построения минимального вершинного 1-расширения для цветного дерева особого вида. В [4] решается задача о генерации цветных графов без проверки на изоморфизм. В данной работе мы рассмотрим полные графы Kni,n2 с вершинами двух цветов, то есть i = 2. Для удобства будем считать, что n1 C n2. Как следует из определения, минимальное вершинное 1-расширение графа Kn1,n2 содержит две дополнительные вершины. Далее представлено полное решение задачи построения всех минимальных вершинных 1-расширений для графов Kn1,n2. Заметим, что в работе [5] введена модель для изучения отказов связей, которой соответствует минимальное рёберное k-расширение. Если рассматриваются графы без кратных рёбер, то полные графы не имеют минимальных рёберных k-расширений ни при каких натуральных значениях k. Аналогичная ситуация имеет место и для цветных полных графов. Напомним, что объединением двух графов G1 = (V1, a1) и G2 = (V2, a2) называется граф G1 U G2 = (V1 U V2, a1 U a2). Если V1 П V2 = 0, то естественным образом операция переносится и на случай цветных графов. Теорема 1. Полный двухцветный граф K1,1 имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение - граф K1,1 U K1,1 (рис. 1). аб Рис. 1. Полный двухцветный граф K1,1 (а ) и его минимальное вершинное 1-расширение (б ) Теорема 2. Полные n-вершинные двухцветные графы вида K1n2, где n2 > 1,име-ют единственное с точностью до изоморфизма минимальное вершинное 1-расширение, которое содержит 2n2+1 дополнительных рёбер и строится следующим образом: добавляются вершина v1 первого цвета и вершина v2 второго цвета. Вершина v1 соединяется со всеми вершинами второго цвета, вершина v2 соединяется также со всеми вершинами второго цвета и с одной из вершин первого цвета. На рис. 2 приведены полный двухцветный граф K1,3 и его минимальное вершинное 1-расширение. Рис. 2. Граф K1,3 (а) и его минимальное вершинное 1-расширение (б ) Теорема 3. Полные n-вершинные двухцветные графы вида КП1П2, 1 < n1 n2, имеют единственное с точностью до изоморфизма минимальное вершинное 1-расширение, которое содержит 2n дополнительных ребра и строится следующим образом: добавляются вершина v1 первого цвета и вершина v2 второго цвета. Вершины v1 и v2 соединяются рёбрами со всеми вершинами исходного графа. На рис. 3 приведены полный двухцветный граф K2,2 и его минимальное вершинное 1-расширение. Рис. 3. Граф K2,2 (а) и его минимальное вершинное 1-расширение (б ) Таким образом, схемы построения минимальных вершинных 1-расширений найдены для всех возможных полных двухцветных графов.

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