Software & Systems

Проблеме исследования мер целостности графов уделяется особое внимание, поскольку она тесно связана с анализом и синтезом сложных технических систем, включая вычислительные системы, коммуникационные и транспортные сети, трубопроводные системы. Для таких систем отказоустойчивость является важнейшим показателем качества функционирования [1, 2]. Под отказоустойчивостью системы принято понимать ее свойство сохранять работоспособность (правильность функционирования) при наличии ошибок или отказов элементов системы.

Принято выделять два уровня отказоустойчивости: полная отказоустойчивость - система продолжает работать в случае отказов отдельных ее элементов без существенной потери функциональных свойств; амортизация отказов - система деградирует, то есть сохраняет работоспособность с частичной потерей функций [3]. Полная отказоустойчивость достигается в первую очередь введением избыточности, например, дублированием элементов системы с возможностью замены отказавшего элемента на исправный, который берет на себя соответствующие функции. Избыточность в виде аппаратных, программных и информационных ресурсов является классическим подходом обеспечения отказоустойчивости, который, как правило, ведет к повышению стоимости систем [2]. Поэтому проектирование сложных технических систем - это прежде всего поиск компромисса между допустимой стоимостью и требуемой отказоустойчивостью системы. Для решения подобных задач привлекаются различные математические модели и методы оптимизации.

В задачах анализа и синтеза отказоустойчивых систем достаточно широко используются методы теории графов и комбинаторной оптимизации. Техническая система представляется в виде связного графа, вершины которого соответствуют элементам системы, а ребра – связям между элементами [3]. Тогда отказ элемента технической системы можно интерпретировать как удаление надлежащего элемента графа, а потерю связи между элементами - как отсутствие ребра или цепи между соответствующими вершинами графа. В рамках теоретико-графового представления в работе [3] предложена модель исследования полной отказоустойчивости. Моделируя исходную систему в виде связного графа, последний погружается в некоторый минимальный избыточный граф, который рассматривается в качестве отказоустойчивой реализации исходной системы. Минимизация избыточности – одна из основных целей при проектировании отказоустойчивых систем. Для исследования амортизации отказов также применяются теоретико-графовые модели и методы. Система считается полностью работоспособной, если соответствующий ей граф связный. Отказы ведут к повреждению надлежащих элементов графа. Меры целостности графа позволяют оценить частичную потерю работоспособности системы вследствие отказа ее элементов или связей между ними [4]. Вершинная целостность - одна из детерминированных мер целостности графа.

Все не определяемые ниже термины теории графов можно найти в [5]. Будем рассматривать только простые графы, то есть конечные неориентированные графы без петель и кратных ребер.

Пусть G = (V, E) - простой связный граф с множеством вершин V и множеством ребер E, при этом n = | V | ³ 1. Под вершинной целостностью (Vertex Integrity) графа G = (V, E) понимается числовой параметр I(G), вычисляемый по формуле

I(G) = min S Í V {| S | + w(G - S)},                         (1)

где w(G - S) - порядок наибольшей компоненты связности графа G - S, который получается из G удалением всех вершин из S Í V [6]. Множество S, для которого достигается равенство в (1), принято называть I-множеством. В неполном связном графе G всякое I-множество является сепаратором этого графа [7]. Таким образом, перебирая все сепараторы графа G и подставляя их в выражение | S | + w(G - S), можно вычислить значение I(G). Доказано, что для графов общего вида задача вычисления вершинной целостности NP-трудная и полиномиально разрешимая на деревьях, расщепляемых и интервальных графах, графах перестановок [8, 9]. Ввиду высокой вычислительной сложности нахождения точных значений вершинной целостности произвольного графа G актуальны нижние и верхние оценки для I(G). Некоторые нижние оценки для I(G) приведены в работе [4]. Они выражаются через такие числовые параметры графа, как число вершинной связности, хроматическое число и плотность графа. В общем случае для вершинной целостности графа G = (V, E) верны естественные границы 1 £ I(G) £ n, при этом наибольшее значение достигается на полном графе, а наименьшее - на безреберном.

В данной работе предлагаются способ конструктивного оценивания значения I(G) с помощью множества всех минимальных сепараторов графа и программные средства вычисления верхней оценки для I(G) и соответствующего приближения к I-множеству. Для изложения результатов работы введем некоторые определения и обозначения, касающиеся мер целостности графов.

Множество всех вершин графа G = (V, E), смежных с некоторой вершиной v Î V, образует в G окрестность вершины v, которую принято обозначать через N (v). Под замкнутой окрестностью вершины v Î V в G понимается множество N [v] = N (v) È {v}. Пусть C Í V. Тогда множества вершин N (C) = (È v Î C N (v)) \ C, N [C] = N (C) È C называются окрестностью и замкнутой окрестностью соответственно для C в графе G. Множество вершин S Í V разделяет несмежные вершины u и v графа G, если в графе G - S вершины u и v принадлежат различным компонентам связности. Множество S при этом называют (u, v)-сепарато­ром (или (u, v)-разделяющим множеством вершин) графа G, и минимальным (u, v)-сепаратором, если в нем нет собственного подмножества, являю- щегося (u, v)-сепаратором графа G. Сепаратор S минимальный, если в G существует такая пара вершин u и v, что S является минимальным (u, v)-сепаратором. Другими словами, любой минимальный сепаратор разделяет хотя бы одну пару несмежных вершин графа. Очевидно, что пару смежных вершин графа разделить нельзя, используя лишь сепараторы как разделяющие множества вершин. Поэтому всякий связный граф, отличный от полного графа, всегда имеет сепараторы, а значит, и минимальные сепараторы [5]. Необходимо отметить, что при удалении из графа G = (V, E) некоторой вершины v Î V неизменно удаляются все ребра, инцидентные этой вершине. Полученный в результате граф обозначают G – v. Подобным образом граф G - S получается из G удалением всех вершин, входящих в S Í V, вместе с инцидентными им ребрами. Если граф G - S несвязен, множество вершин всякой его компоненты связности называется областью связности этого графа.

Известно [10], что множество S Í V является минимальным сепаратором графа G = (V, E), если и только если существуют две различные области связности C1 и C2 графа G - S, такие что

N (C1) = N (C2) = S.                                                 (2)

Необходимое и достаточное условие (2) позволяет находить в графе G минимальные сепараторы, включая минимальные сепараторы, близкие к некоторой вершине этого графа. Минимальный (u, v)-сепаратор S такой, что S Í N(v) называется минимальным сепаратором, близким к вершине v. Значит, близкий к v минимальный сепаратор лежит в окрестности вершины v. Для произвольной вершины v Î V можно определить в G = (V, E) близкие к ней минимальные сепараторы следующим образом:

–      вначале найти множество вершин N [v], образующих замкнутую окрестность вершины v в графе G;

–      затем построить граф H = G - N [v] и выявить в нем все области связности;

–      установить для всякой выявленной области связности C графа H множество вершин N (C), образующих окрестность для C в графе G. Каждое такое множество определяет в G минимальный сепаратор, близкий к вершине v.

Исходя из определения минимальных сепараторов, можно доказать следующие свойства, характеризующие отношение их близости с вершинами графа. Если вершина v Î V смежна со всеми другими вершинами графа G = (V, E), то есть вершина v доминирует над вершинами из V \ {v}, то в G не существует минимального сепаратора, близкого к v. В этом случае N[v] = V и граф H = G - N[v] пустой. Во всех других случаях могут существовать несколько минимальных сепараторов, близких к v. Возможны случаи, когда один и тот же минимальный сепаратор близок к различным несмежным вершинам графа. При этом, если u и v не являются смежными вершинами, существует ровно один минимальный (u, v)-сепара­тор, близкий к v. Кроме того, для всякого минимального сепаратора графа G = (V, E) всегда найдется хотя бы одна вершина v Î V, к которой он близок. Приведенные выше свойства минимальных сепараторов указывают стратегию их перебора: начиная с некоторого множества минимальных сепараторов можно это множество последовательно пополнять путем выявления минимальных сепараторов, близких к вершинам, входящим в ранее обнаруженные минимальные сепараторы.

Обозначим через M множество всех минимальных сепараторов графа G = (V, E). Если G = (V, E) - хордовый граф (в частности дерево), то | M | = O(n), где n = | V | [11]. Заметим, что граф считается хордовым, если ни один из его порожденных подграфов не является простым циклом длины строго больше трех. Однако существуют графы, которые могут содержать O(2n) минимальных сепараторов. Например, такими являются графы типа «гамак» [11]. Примечательно, что для графов, возникающих при моделировании сложных технических систем, число минимальных сепараторов, как правило, ограничено сверху полиномом от n.

Для верхнего оценивания вершинной целостности графа G и нахождения соответствующего приближения к I-множеству достаточно последовательно осуществлять просмотр элементов множества M и подставлять их в выражение | S | + w(G - S). Наименьшее полученное значение выражения | S | + w(G - S) является верхней оценкой для I(G), а минимальный сепаратор S, на котором достигнуто это наименьшее значение, приближением к I-множеству. В этом суть предлагаемого алгоритма VIMS.

В алгоритме VIMS процесс генерации множества всех минимальных сепараторов реализуется процедурой LIST_MIN_SEP (List of all minimal separators):

LIST_MIN_SEP - Процедура генерации всех минимальных сепараторов

Вход: граф G = (V, E)

Выход: множество M всех минимальных сепараторов графа G

0.   M ¬ Æ

1.   Для каждой вершины v Î V

2.         H ¬ G – N [v]

3.         Для каждой области связности C графа H

4.                S ¬ N (C)

5.                Если S ¹ Æ, то M ¬ M È {S}

6.   Для каждого S Î M

7.         Для каждой вершины x Î S

8.                X ¬ S È N (x)

9.                H ¬ G – X

10.                    Для каждой области связности C графа H

11.                    S ¬ N (C)

12.                           Если S ¹ Æ, то M ¬ M È {S}

Основные этапы процедуры LIST_MIN_SEP следующие. На шаге 0 множество M полагается пустым. Далее на шагах 1-5 выполняется просмотр всех вершин входного графа G и определяются минимальные сепараторы, близкие к ним. В результате формируется некоторое подмножество искомого множества M. На шагах 6-12 это подмножество пополняется новыми минимальными сепараторами, близкими к вершинам, которые принадлежат ранее найденным минимальным сепараторам. Заметим, что везде при выполнении шагов 2, 4, 8, 11 окрестности вершин и областей связности вычисляются применительно к графу G. Как было отмечено выше, один и тот же минимальный сепаратор может быть близок к различным несмежным вершинам графа. Этот факт учитывает теоретико-множественная операция объединения, осуществляемая на 5-м и 12-м шагах процедуры LIST_MIN_SEP. Процесс генерации завершается, как только будут исчерпаны все возможности пополнения множества M. Следует заметить, что алгоритмы, подобные процедуре LIST_MIN_SEP, известны в литературе [11, 12]. Все они базируются на свойствах хордовых графов и минимальных сепараторов.

Алгоритм VIMS, включая процедуру LIST_ MIN_SEP, находит для заданного графа G = (V, E) верхнюю оценку вершинной целостности и соответствующее приближение к I-множеству за время O(n3 × | M |), где n = | V |. Когда G содержит полиномиальное число минимальных сепараторов, алгоритм VIMS способен за полиномиальное время находить оценку вершинной целостности этого графа.

Алгоритм VIMS реализован в виде комплекса программ VIMS на языке программирования С++ в среде разработки Code::Blocks. С помощью данного комплекса программ были выполнены вычислительные эксперименты. Эксперименты осуществлялись на компьютере с процессором Intel® Core™ i3 CPU & 2.40 GHz и ОЗУ размером 3 Гб. Вычисленная верхняя оценка I* и время работы алгоритма VIMS (в секундах) сравнивались с точным значением вершинной целостности графа, полученным методом полного перебора всех сепараторов входного графа, и временем нахождения точного значения. Вычислительные эксперименты проводились на случайных связных графах различной размерности. Результаты экспериментов для n = | V | = 20 представлены в таблице 1.

Алгоритм VIMS был также опробован на графах с известным типом структур - графах Гретша, Хивуда, Хватала, графах типа «гамак» и «двухмерная решетка» [5]. Эти графы специально были выбраны для тестирования, поскольку они имеют регулярную структуру и большое число сепараторов. Результаты вычислительных экспериментов на этих графах представлены в таблице 2.

Таблица 1

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

Table 1

Random graph experiment results

Таблица 2

Результаты экспериментов на графах со специальной структурой

Table 2

Specialized structure graph experiment results

Результаты экспериментов позволяют сделать вывод: вычисленные с помощью алгоритма VIMS значения оценок являются хорошими и часто достижимыми. При этом время работы алгоритма VIMS существенно меньше времени реализации полного перебора всех сепараторов входного графа. Однако было замечено, что алгоритм VIMS дает большую ошибку на графах с регулярной структурой (например, типа «двухмерная решетка»), чем на графах с нерегулярной структурой. Для проверки отклонения оценки вершинной целостности от точного значения были проведены вычислительные эксперименты на множестве графов со структурой типа «двухмерная решетка». Результаты экспериментов представлены в таблице 3. В ней через n1 обозначена высота двухмерной решетки, а через n2 – ширина. Из результатов экспериментов видно, что наибольшая ошибка возникает в случае, когда n1 = n2 (высота и ширина решетки совпадают), что приводит к уменьшению доли минимальных сепараторов к общему числу сепараторов.

Таблица 3

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

Table 3

Two-dimensional array experiment results

Разработанный комплекс программ VIMS – это совокупность программных модулей, позволяющих выполнять следующие действия:

–      построение случайного связного графа с заданным числом вершин;

–      ввод из внешнего файла графа, заданного списком окрестностей его вершин;

–      удаление из графа некоторого множества вершин и инцидентных им ребер;

–      определение компонент связности графа и мощности максимальной (по числу вершин) компоненты;

–      нахождение всех минимальных сепараторов заданного графа;

–      вычисление вершинной целостности графа и I-множества методом исчерпывающего перебора всех различных подмножеств множества вершин и нахождения среди них сепараторов;

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

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

Применение вычислительной техники в критических областях, а также стремительное развитие сетей коммуникаций и средств связи стимулируют разработку математического и программного обеспечения процессов создания отказоустой- чивых систем. В работе исследована одна из детерминированных мер целостности графа, применяемая в проектировании сложных технических систем, если структура системы представляется неориентированным графом. Эта мера позволяет оценить частичную потерю работоспособности системы в случае отказа ее отдельных элементов. Она базируется на самой простой модели разрушения графа, когда отказ элемента системы интерпретируется как удаление вершины графа вместе с инцидентными ей ребрами. Но даже в этом простейшем случае вычисление меры целостности графа является NP-трудной задачей. Между тем актуальны модели разрушений графа, учитывающие более сложные последствия отказов элементов, отражающие иерархичность построения сложных систем и управления ими. Перспективны изучение соответствующих мер целостности графа и разработка для них алгоритмов и программ вычисления точных и приближенных значений.

Литература

1.     Хорошевский В.Г. Архитектура вычислительных систем. М.: МГТУ им. Н.Э. Баумана, 2008. 520 с.

2.     Громов Ю.Ю., Драчев В.О., Набатов К.А., Ивано- ва О.Г. Синтез и анализ живучести сетевых систем. М.: Машиностроение, 2007. 152 с.

3.     Абросимов М.Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012. 192 с.

4.     Быкова В.В. О мерах целостности графа // Прикладная дискретная математика. 2014. № 4. С. 96–111.

5.     Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2012. 392 с.

6.     Barefoot C.A., Entringer R. & Swart H.C. Vulnerability in graphs – a comparative survey. J. Combin. Math. Combin. Computing, 1987, no. 1, pp. 13–22.

7.     Atici M. & Crawford R. The integrity of small cage graphs. Australasian J. of Combinatorics, 2009, no. 43, pp. 39–55.

8.     Clark L.H., Entringer R.C. & Fellows M.R. Computational complexity of integrity. J. Combin. Math. Combin. Computing, 1987, no. 2, pp. 179–191.

9.     Drange P.G., Dregi M.S. & Hof P. On the computational complexity of vertex integrity and component order connectivity, 2014. URL: http://arxiv.org/abs/1403.6331v1 (дата обращения: 23.06.2015).

10.  Berry A. & Bordat J.-P. Structuring the minimal separators of an undirected graph. Technical Report 152, LIM, Marseille, 1996, 8 p.

11.  Bodlaender H.L. & Fomin F.V. Tree decompositions with small cost. Discrete Applied Mathematics, 2005, no. 145 (2), pp. 143–154.

12.  Berry A., Bordat J.-P. & Cogis O. Generating all the minimal separators of a graph. Int. J. of Foundations of Computer Science, 2000, no. 11, pp. 397-404.