Calculation of upper bounds for graph vertex integrity based on the minimal separators.pdf Все последние десятилетия проблеме исследования мер целостности графов уделяется особое внимание, поскольку она тесно связана с вопросами анализа и синтеза сложных технических систем, для которых отказоустойчивость является важнейшим показателем качества функционирования. Вершинная целостность - одна из детерминированных мер целостности графа [1]. Пусть G = (V, E) -простой связный граф с множеством вершин V и множеством рёбер E, при этом n = |V | ^ 1 -порядок графа G. Под вершинной целостностью (Vertex Integrity) графа G понимается числовой параметр I(G), вычисляемый по формуле I (G) = mm {|S| + w (G - S)}, (1) где w (G - S) -порядок наибольшей компоненты связности графа G - S, который получается из G удалением всех вершин, входящих в S С V. Множество S, для которого достигается равенство в (1), принято называть I-множеством. В неполном связном графе G всякое I-множество является сепаратором этого графа [2]. Доказано [3], что задача вычисления вершинной целостности графа NP-трудная. Ввиду высокой вычислительной сложности нахождения точных значений вершинной целостности произвольного графа актуальны нижние и верхние оценки для I (G). Множество всех вершин графа G = (V,E), смежных с некоторой вершиной v G V, образует в G окрестность вершины v, которая обозначается через N(v). Под замкнутой окрестностью вершины v понимается множество N[v] = N(v) U {v}. Множество вершин N(S) = I (J N(v) I \S называется окрестностью для S С V в G. Множество \ves J вершин S С V разделяет несмежные вершины u и v графа G, если в графе G - S вершины u и v принадлежат различным компонентам связности. Множество S при этом называют (u, v)-сепаратором; (u, v)-сепаратор называют минимальным, если в нём нет собственного подмножества, являющегося (u, v)-сепаратором. Сепаратор S минимальный, если в G существует такая пара вершин u и v, что S является минимальным (u, v)-сепаратором, то есть минимальным относительно, по крайней мере, двух вершин этого графа. Известно, что S - минимальный сепаратор графа G, если и только если существуют две различные области связности C1 и C2 графа G - S, такие, что N(C1) = N(C2) = S [4]. Если S является минимальным (u, v)-сепаратором и S С N(v), то S называется минимальным сепаратором, близким к v. Обозначим через M множество всех минимальных сепараторов графа G = (V, E). В общем случае множество M может содержать экспоненциальное число сепараторов. В настоящей работе предлагается алгоритм, позволяющий с помощью минимальных сепараторов вычислять верхнюю оценку меры вершинной целостности и находить соответствующие приближения к I-множествам заданного графа за время O(n3|M|). Поиск всех минимальных сепараторов осуществляется по следующему алгоритму. Алгоритм. Поиск минимальных сепараторов Вход: Граф G(V, E) Выход: M - множество всех минимальных сепараторов графа G 1. M := 0 2. Для каждого v G V 3. H := G - N[v] 4. Для каждой области связности C графа H 5. S := N(v) П N(C) 6. Если S = 0, то M := M U {S} 7. Для каждого S G M 8. Для каждого x G S 9. X := S U N(x) 10. H := G - X 11. Для каждой области связности C графа H 12. S := N(C) П X 13. Если S = 0, то M := M U {S} Каждый из найденных минимальных сепараторов подставляется в выражение | S| + + w (G - S). Минимальное полученное значение I * является верхней оценкой I (G). Программный код алгоритма написан на языке С+-Н в среде разработки Code::Blocks. Вычисленное значение верхней оценки I* и время работы ta предложенного алгоритма сравнивались с точным значением вершинной целостности графа, полученным методом полного перебора за время t. Вычислительный эксперимент был проведён на случайных связных графах различных порядков; результаты эксперимента для n =20 представлены в таблице. № графа t I ta I * I * -1 t/ta 1 31,922 15 0,066 16 1 483,6667 2 27,653 16 0,638 16 0 43,34326 3 27,634 15 3,636 15 0 7,60011 4 25,34 16 16,881 16 0 1,501096 5 25,95 15 0,05 16 1 519 6 26,487 15 0,624 15 0 42,44712 7 26,717 15 5,793 15 0 4,611945 8 26,04 15 0,05 15 0 520,8 9 24,56 15 0,03 16 1 818,6667 10 23,096 14 0,587 14 0 39,34583 Алгоритм был также опробован на графах с известным типом структур (на двумерных решётках, на графах Гретша, Хватала, Хивуда и др.). Результаты экспериментов позволяют говорить о том, что вычисленные значения оценок являются хорошими и часто достижимыми. При этом время нахождения оценки существенно меньше, чем при использовании метода полного перебора. Однако было замечено, что алгоритм даёт большую ошибку на графах с регулярной структурой (например, на двумерной решётке).

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