On the upper bound for the number of additional edges in minimal vertex extensions of colored circles.pdf Будем рассматривать неориентированные графы с вершинами двух типов или цветов. Для исследования отказоустойчивости дискретных систем J. P. Hayes [1] предложил графовую модель и рассмотрел отказоустойчивые реализации некоторых классов графов. Основные понятия используются в соответствии с работой [2]. Определение 1. Граф G* = (V*,а*) называется минимальным вершинным к-расширением n-вершинного графа G = (V, а) с вершинами p типов, если выполняются следующие условия: 1) граф G* является вершинным к-расширением графа G, то есть граф G вложим в каждый подграф графа G*, получающийся удалением любых его к вершин; 2) граф G* содержит n + к ■ p вершин, то есть | V* | = | V| + к ■ p; 3) а* имеет минимальную мощность при выполнении условий 1 и 2. Рассмотрим цепь Pn c n + 2 вершинами двух типов: двумя вершинами первого типа степени 1 и n вершинами второго типа. Найдём минимальный по количеству рёбер граф P**, состоящий из n + 3 вершин (две вершины первого типа, а остальные — второго), такой, что при удалении любой вершины второго типа существует путь между вершинами первого типа, проходящий по n вершинам второго типа. Лемма 1. Минимальное количество дополнительных рёбер в P** равно |_n/2j +3. Если вершины цепи Pn пронумерованы от 0 до n + 1, добавленная вершина в цепи P** имеет номер n + 2, то для получения Pn* к Pn нужно добавить следующие рёбра: а) n — нечётное, n > 1 : {0, 2}; {n + 2,n - 2}; {n + 2,n}; {n + 2,n +1}; {к, к + 3}, 1 ^ к ^ n - 4; б) n — чётное, n > 2: {0, 2}; {n + 2,n - 3}; {n + 2,n - 1}; {n + 2,n}; {n + 2,n + 1}; {к, к + 3}, 1 ^ к ^ n - 5; в) n = 1: {n + 2, 0}, {n + 2, 2}; г) n = 2: {n + 2, 0}, {n + 2,1}, {n + 2, 2}, {n + 2, 3}. На рис. 1 приведены иллюстрирующие лемму примеры. Будем рассматривать циклы Cn с вершинами двух типов. Поставим каждому циклу в соответствие последовательность чисел e0,e1,... , ek-1, такую, что 1) к — количество рёбер в цикле Cn, соединяющих две вершины разного типа, т.е. количество групп последовательных вершин одного типа, причём вершины, соседние с крайними из каждой группы, имеют другой тип; 2) i-я группа содержит ei последовательно соединённых вершин одного типа. Пусть тип вершин в i-й группе отличается от типа вершин в (i - 1)-й группе для любого i > 0. Типы вершин в нулевой и (к - 1)-й группе тоже не совпадают; 3) eo + e1 +-----+ ek-1 = n. Такой цикл будем обозначать Cn(e0, e1,..., ek-1). Пусть СП — минимальное вершинное 1-расширение цикла Cn(e0, e1,... , ek-1). Тогда минимальное количество рёбер, которые нужно добавить к СП, чтобы получить СП, можно оценить следующим образом. Теорема 1. Количество дополнительных рёбер m в минимальном вершинном 1-расширении цикла Cn(e0, e1,... , ek-1) СП удовлетворяет условию fc-1 m < Е Lei/2j +3 ^ [n/2j + 3к. г=0 Одно из вершинных 1-расширений строится по лемме 1 последовательным рассмотрением всех групп вг.

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