Построение всех неизоморфных суперграфов без проверки на изоморфизм | Прикладная дискретная математика. 2020. № 48. DOI: 10.17223/20710410/48/7

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