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

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

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



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






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


Модел. и анализ информ. систем, 2017, том 24, номер 6, страницы 788–801 (Mi mais601)  

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

Задача о кратчайшем пути в кратном графе

А. В. Смирнов

Ярославский государственный университет им. П.Г. Демидова, ул. Советская, 14, г. Ярославль, 150003 Россия

Аннотация: В статье вводится определение неориентированного кратного графа произвольной натуральной кратности $k>1$. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение $k$ связанных ребер, которые соединяют 2 или $k+1$ вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна какому-либо кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом $k$ связанных ребер какого-либо мультиребра. Если вершина является общим концом какого-либо мультиребра, то она не может быть общим концом никакого другого мультиребра.
Отдельно рассматривается класс делимых кратных графов, основной особенностью которых является возможность выделения $k$ частей, согласованных на всех связанных ребрах и не содержащих общих ребер. Каждая из частей является обычным графом.
Для кратного графа обобщаются понятия степени вершины, связности графа, пути, цикла, веса ребра и длины пути.
Вводится понятие множества достижимости по обычным и по кратным ребрам, определяется свойство смежности двух множеств достижимости. Показано, что проверка связности кратного графа может быть выполнена за полиномиальное время с помощью алгоритма, основанного на поиске множеств достижимости и проверки их смежности.
Рассматривается критерий существования кратного пути между двумя вершинами и ставится задача о кратчайшем кратном пути. Строится алгоритм поиска кратчайшего пути в кратном графе, который использует алгоритм Дейкстры для поиска кратчайших путей в подграфах, соответствующих отдельным множествам достижимости.

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17-07-00823_а
Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект № 17-07-00823 А).


DOI: https://doi.org/10.18255/1818-1015-2017-6-788-801

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

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

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

Образец цитирования: А. В. Смирнов, “Задача о кратчайшем пути в кратном графе”, Модел. и анализ информ. систем, 24:6 (2017), 788–801

Цитирование в формате AMSBIB
\RBibitem{Smi17}
\by А.~В.~Смирнов
\paper Задача о кратчайшем пути в кратном графе
\jour Модел. и анализ информ. систем
\yr 2017
\vol 24
\issue 6
\pages 788--801
\mathnet{http://mi.mathnet.ru/mais601}
\crossref{https://doi.org/10.18255/1818-1015-2017-6-788-801}
\elib{http://elibrary.ru/item.asp?id=30730617}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais601
  • http://mi.mathnet.ru/rus/mais/v24/i6/p788

    ОТПРАВИТЬ: 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. А. В. Смирнов, “Остовное дерево в делимом кратном графе”, Модел. и анализ информ. систем, 25:4 (2018), 388–401  mathnet  crossref  elib
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:266
    Полный текст:65
    Литература:5

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019