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

В 1976 г. John P. Hayes предложил основанную на графах модель для исследования отказоустойчивости дискретных систем. Технической системе сопоставляется граф. Элементам системы соответствуют вершины графа, а связям между элементами — рёбра или дуги графа. Под отказом элемента системы понимается удаление из графа системы соответствующей вершины вместе со всеми её рёбрами. Формализацией отказоустойчивой реализации системы является расширение графа. Граф $G^*$ называется вершинным $k$-расширением графа $G$, если после удаления любых $k$ вершин из графа $G^*$ граф $G$ вкладывается в получившийся граф. Вершинное $k$-расширение графа $G$ называется минимальным, если оно имеет наименьшее число вершин и рёбер среди всех вершинных $k$-расширений графа $G$. В работе предлагается алгоритм построения всех неизоморфных минимальных вершинных $k$-расширений заданного графа без проверки на изоморфизм методом канонических представителей.