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

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

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



Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика:
Год:
Том:
Выпуск:
Страница:
Найти






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


Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика, 2019, том 19, выпуск 4, страницы 479–486 (Mi isu823)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Научный отдел
Информатика

Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей

М. Б. Абросимовa, И. А. К. Камилba, А. А. Лобовa

a Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского, Россия, 410012, г. Саратов, ул. Астраханская, д. 83
b Министерство науки и технологий Ирака, Багдад, Ирак

Аннотация: В 1976 г. John P. Hayes предложил основанную на графах модель для исследования отказоустойчивости дискретных систем. Технической системе сопоставляется граф. Элементам системы соответствуют вершины графа, а связям между элементами — рёбра или дуги графа. Под отказом элемента системы понимается удаление из графа системы соответствующей вершины вместе со всеми её рёбрами. Формализацией отказоустойчивой реализации системы является расширение графа. Граф $G^*$ называется вершинным $k$-расширением графа $G$, если после удаления любых $k$ вершин из графа $G^*$ граф $G$ вкладывается в получившийся граф. Вершинное $k$-расширение графа $G$ называется минимальным, если оно имеет наименьшее число вершин и рёбер среди всех вершинных $k$-расширений графа $G$. В работе предлагается алгоритм построения всех неизоморфных минимальных вершинных $k$-расширений заданного графа без проверки на изоморфизм методом канонических представителей.

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

DOI: https://doi.org/10.18500/1816-9791-2019-19-4-479-486

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

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.17
Поступила в редакцию: 20.05.2019
Принята в печать:30.06.2019

Образец цитирования: М. Б. Абросимов, И. А. К. Камил, А. А. Лобов, “Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей”, Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика, 19:4 (2019), 479–486

Цитирование в формате AMSBIB
\RBibitem{AbrKamLob19}
\by М.~Б.~Абросимов, И.~А.~К.~Камил, А.~А.~Лобов
\paper Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей
\jour Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика
\yr 2019
\vol 19
\issue 4
\pages 479--486
\mathnet{http://mi.mathnet.ru/isu823}
\crossref{https://doi.org/10.18500/1816-9791-2019-19-4-479-486}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/isu823
  • http://mi.mathnet.ru/rus/isu/v19/i4/p479

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. И. А. К. Камил, Х. Х. К. Судани, А. А. Лобов, М. Б. Абросимов, “Построение всех неизоморфных суперграфов без проверки на изоморфизм”, ПДМ, 2020, № 48, 82–92  mathnet  crossref
    2. М. Б. Абросимов, Х. Х. К. Судани, А. А. Лобов, “Построение минимальных рёберных расширений графа без проверки на изоморфизм”, Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика, 20:1 (2020), 105–115  mathnet  crossref
  • Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика
    Просмотров:
    Эта страница:56
    Полный текст:6
    Литература:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020