RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Model. Anal. Inform. Sist.: Year: Volume: Issue: Page: Find

 Model. Anal. Inform. Sist., 2017, Volume 24, Number 6, Pages 788–801 (Mi mais601)

The shortest path problem for a multiple graph

A. V. Smirnov

P.G. Demidov Yaroslavl State University, 14 Sovetskaya str., Yaroslavl, 150003 Russia

Abstract: In the article, the definition of an undirected multiple graph of any natural multiplicity $k>1$ is stated. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is the union of $k$ linked edges, which connect 2 or $k+1$ vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common ending vertex to $k$ linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of any other multi-edge. Also, a class of the divisible multiple graphs is considered. The main peculiarity of them is a possibility to divide the graph into $k$ parts, which are adjusted on the linked edges and which have no common edges. Each part is an ordinary graph. The following terms are generalized: the degree of a vertex, the connectedness of a graph, the path, the cycle, the weight of an edge, and the path length. There is stated the definition of the reachability set for the ordinary and multiple edges. The adjacency property is defined for a pair of reachability sets. It is shown, that we can check the connectedness of some multiple graph with the polynomial algorithm based on the search for the reachability sets and testing their adjacency. There is considered a criterion of the existence of a multiple path between two given vertices. The shortest multiple path problem is stated. Then we suggest an algorithm of finding the shortest path in a multiple graph. It uses Dijkstra's algorithm of finding the shortest paths in subgraphs, which correspond to different reachability sets.

Keywords: multiple graph, divisible graph, reachability set, connectedness, multiple path, shortest path.

 Funding Agency Grant Number Russian Foundation for Basic Research 17-07-00823_а This work was supported by the Russian Foundation for Basic Research under the Grant No 17-07-00823 A.

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

Full text: PDF file (302 kB)
References: PDF file   HTML file

UDC: 519.17

Citation: A. V. Smirnov, “The shortest path problem for a multiple graph”, Model. Anal. Inform. Sist., 24:6 (2017), 788–801

Citation in format AMSBIB
\Bibitem{Smi17} \by A.~V.~Smirnov \paper The shortest path problem for a multiple graph \jour Model. Anal. Inform. Sist. \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/eng/mais601
• http://mi.mathnet.ru/eng/mais/v24/i6/p788

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. A. V. Smirnov, “Ostovnoe derevo v delimom kratnom grafe”, Model. i analiz inform. sistem, 25:4 (2018), 388–401
•  Number of views: This page: 339 Full text: 90 References: 13