Дата публикации: 2020

Дата публикации в реестре: 2020-07-05T11:55:43Z

Аннотация:

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

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2020. № 48. С. 82-92