Построение всех неизоморфных суперграфов без проверки на изоморфизм

Важное направление в теории графов — построение графов с заданными свойствами без непосредственной проверки на изоморфизм. Программы, выполняющие такие построения, называются генераторами. Известны генераторы неориентированных графов с заданным числом вершин, деревьев, регулярных графов, двудольных графов, турниров и т. д. Граф $G = (V, \alpha)$ является частью графа $H = (W, \beta)$, если все вершины и рёбра графа $G$ принадлежат $H$, то есть $V \subseteq W$ и $\alpha \subseteq \beta$. В этом случае граф $H$ является суперграфом графа $G$. В исследованиях по теории графов часто свойства графа изучаются через какие-то его части. Возникает и обратная задача: по известной части построить графы, которые её содержат. Такая задача имеет место, например, при исследовании отказоустойчивых реализаций дискретных систем. В работе предлагается алгоритм построения для заданного графа всех его суперграфов с заданным числом рёбер без проверки на изоморфизм. Предлагается специальный матричный код и алгоритм генерации суперграфов методом канонических представителей на его основе. Рассматриваются оптимизации метода и вопросы, связанные с его параллельной реализацией.