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

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