|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Задача о кратчайшем пути в кратном графе
А. В. Смирнов Ярославский государственный университет им. П.Г. Демидова,
ул. Советская, 14, г. Ярославль, 150003 Россия
Аннотация:
В статье вводится определение неориентированного кратного графа произвольной натуральной кратности $k>1$. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение $k$ связанных ребер, которые соединяют 2 или $k+1$ вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна какому-либо кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом $k$ связанных ребер какого-либо мультиребра. Если вершина является общим концом какого-либо мультиребра, то она не может быть общим концом никакого другого мультиребра.
Отдельно рассматривается класс делимых кратных графов, основной особенностью которых является возможность выделения $k$ частей, согласованных на всех связанных ребрах и не содержащих общих ребер. Каждая из частей является обычным графом.
Для кратного графа обобщаются понятия степени вершины, связности графа, пути, цикла, веса ребра и длины пути.
Вводится понятие множества достижимости по обычным и по кратным ребрам, определяется свойство смежности двух множеств достижимости. Показано, что проверка связности кратного графа может быть выполнена за полиномиальное время с помощью алгоритма, основанного на поиске множеств достижимости и проверки их смежности.
Рассматривается критерий существования кратного пути между двумя вершинами и ставится задача о кратчайшем кратном пути. Строится алгоритм поиска кратчайшего пути в кратном графе, который использует алгоритм Дейкстры для поиска кратчайших путей в подграфах, соответствующих отдельным множествам достижимости.
Ключевые слова:
кратный граф, делимый граф, множество достижимости, связность, кратный путь, кратчайший путь.
Поступила в редакцию: 23.08.2017
Образец цитирования:
А. В. Смирнов, “Задача о кратчайшем пути в кратном графе”, Модел. и анализ информ. систем, 24:6 (2017), 788–801
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais601 https://www.mathnet.ru/rus/mais/v24/i6/p788
|
Статистика просмотров: |
Страница аннотации: | 791 | PDF полного текста: | 449 | Список литературы: | 32 |
|