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

doi:10.17223/20710410/48/7

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Построение всех неизоморфных суперграфов без проверки на изоморфизм	2 MB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/48/7

#метод канонических представителей

#отказоустойчивость

Title: Построение всех неизоморфных суперграфов без проверки на изоморфизм
Title: Constructing all nonisomorphic supergraphs with isomorphism rejection
Creator: Судани, Хайдер Хуссейн Карим
|
Лобов, Александр Андреевич
|
Абросимов, Михаил Борисович
|
Камил, Ихаб Абдулджаббар Камил
Date: 2020
DOI: 10.17223/20710410/48/7
Description: Важное направление в теории графов — построение графов с заданными свойствами без непосредственной проверки на изоморфизм. Программы, выполняющие такие построения, называются генераторами. Известны генераторы неориентированных графов с заданным числом вершин, деревьев, регулярных графов, двудольных графов, турниров и т. д. Граф G = (V, а) является частью графа H = (W,в), если все вершины и рёбра графа G принадлежат H, то есть V С W и а С в. В этом случае граф H является суперграфом графа G. В исследованиях по теории графов часто свойства графа изучаются через какие-то его части. Возникает и обратная задача: по известной части построить графы, которые её содержат. Такая задача имеет место, например, при исследовании отказоустойчивых реализаций дискретных систем. В работе предлагается алгоритм построения для заданного графа всех его суперграфов с заданным числом рёбер без проверки на изоморфизм. Предлагается специальный матричный код и алгоритм генерации суперграфов методом канонических представителей на его основе. Рассматриваются оптимизации метода и вопросы, связанные с его параллельной реализацией.