Программные средства анализа отказоустойчивости технических систем на основе вершинной целостности графа
В настоящее время в связи с применением графовых моделей при проектировании отказоустойчивых сложных технических систем особое внимание уделяется исследованию мер целостности графов. Вершинная целостность – одна из детерминированных мер целостности графа. Система считается полностью работоспособной, если соответствующий ей граф связный. Вершинная целостность позволяет оценить частичную потерю работоспособности системы вследствие отказа ее элементов. Вершинной целостностью графа G = (V, E) называется величина I(G) = = min S  V {| S | + w(G – S)}, где w(G – S) – порядок наибольшей компоненты связности графа G – S, который получа-ется из G удалением всех вершин, входящих в S. Значение w(G – S) характеризует размер самого крупного фрагмента системы, образованного после выхода из строя сразу всех элементов из S. Понятие вершинной целостности графа введено Багга, Барфутом, Энтрингером и Свортом. Известно, что задача вычисления I(G) для графа общего вида является NP-трудной. Для нахождения точного значения вершинной целостности необходимо знание всех сепараторов графа. В работе представлены алгоритм и программные средства нахождения приближенного значения I(G). Предлагаемый алгоритм ограничивается рассмотрением всех минимальных сепараторов, поэтому дает лишь верхнюю оценку вершинной целостности. Трудоемкость алгоритма полиномиально зависит от числа вершин и числа минимальных сепараторов входного графа. Результаты экспериментов показали, что вычисленные оценки являются хорошими и часто достижимыми. При выполнении вычислительных экспериментов точное значение вершинной целостности определялось с помощью исчерпывающего перебора всех сепараторов входного графа.