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