RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2020, номер 48, страницы 82–92 (Mi pdm706)  

Прикладная теория графов

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

И. А. К. Камил, Х. Х. К. Судани, А. А. Лобов, М. Б. Абросимов

Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского, г. Саратов, Россия

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

Ключевые слова: суперграф, изоморфизм, канонический код, исключение изоморфизма.

Финансовая поддержка Номер гранта
Министерство науки и высшего образования Российской Федерации FSRR-2020-0006
Работа выполнена при поддержке Минобрнауки России в рамках выполнения государственного задания (проект № FSRR-2020-0006).


DOI: https://doi.org/10.17223/20710410/48/7

Полный текст: PDF файл (739 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.17

Образец цитирования: И. А. К. Камил, Х. Х. К. Судани, А. А. Лобов, М. Б. Абросимов, “Построение всех неизоморфных суперграфов без проверки на изоморфизм”, ПДМ, 2020, № 48, 82–92

Цитирование в формате AMSBIB
\RBibitem{KamSudLob20}
\by И.~А.~К.~Камил, Х.~Х.~К.~Судани, А.~А.~Лобов, М.~Б.~Абросимов
\paper Построение всех неизоморфных суперграфов без проверки на изоморфизм
\jour ПДМ
\yr 2020
\issue 48
\pages 82--92
\mathnet{http://mi.mathnet.ru/pdm706}
\crossref{https://doi.org/10.17223/20710410/48/7}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm706
  • http://mi.mathnet.ru/rus/pdm/y2020/i2/p82

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:36
    Полный текст:5
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020