Вычисление верхней оценки вершинной целостности графа на основе минимальных сепараторов

Рассматривается трудно вычисляемый числовой параметр графа, называемый вершинной целостностью и используемый в анализе и синтезе отказоустойчивых сложных технических систем. Для нахождения данного параметра необходимо знание всех сепараторов исходного графа. Предлагается алгоритм, который ограничивается построением и анализом только всех минимальных сепараторов. Поэтому алгоритм даёт верхнюю оценку вершинной целостности графа. Вычислительная сложность предлагаемого алгоритма полиноминально зависит от числа вершин и числа минимальных сепараторов графа. Результаты экспериментов показали, что вычисленные оценки являются хорошими и часто достижимыми.