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

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

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



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






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


Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика, 2020, том 20, выпуск 1, страницы 105–115 (Mi isu832)  

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

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

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

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

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

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

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

DOI: https://doi.org/10.18500/1816-9791-2020-20-1-105-115

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

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

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

Образец цитирования: М. Б. Абросимов, Х. Х. К. Судани, А. А. Лобов, “Построение минимальных рёберных расширений графа без проверки на изоморфизм”, Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика, 20:1 (2020), 105–115

Цитирование в формате AMSBIB
\RBibitem{AbrSudLob20}
\by М.~Б.~Абросимов, Х.~Х.~К.~Судани, А.~А.~Лобов
\paper Построение минимальных рёберных расширений графа без проверки на изоморфизм
\jour Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика
\yr 2020
\vol 20
\issue 1
\pages 105--115
\mathnet{http://mi.mathnet.ru/isu832}
\crossref{https://doi.org/10.18500/1816-9791-2020-20-1-105-115}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/isu832
  • http://mi.mathnet.ru/rus/isu/v20/i1/p105

    ОТПРАВИТЬ: 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
  • Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика
    Просмотров:
    Эта страница:21
    Полный текст:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020