The Steiner Problem in Directed Graphs

The final qualifying work on the topic: «The Steiner problem in directed graphs" consists of an introduction, five sections, a conclusion, and references. The total volume of work is 115 pages of text containing, 11 images and 16 tables. The list of references contains 15 sources, including 5 foreign ones. Keywords: Steiner problem, minimal Steiner tree, Euclidean graphs, directed graphs, exact methods for solving the Steiner problem, approximate methods of the Steiner problem This work is devoted to study of exact and approximate methods for solving the Steiner problem in directed graphs. Relevance: Exact algorithms for solving the Steiner problem can be used to solve problems of small dimensions. Approximate algorithms are aimed to solve high-power problems on graphs; however, the question of the possibility of using it in practice is still open. Especially when solving the Steiner problem on directed graphs, which is not so widely discussed in the literature, in contrast to problems on undirected networks in a given metric space. Note that many similar problems posed in practice are reduced to a Euclidean graph, in which each vertex has Euclidean coordinates, and the length of each edge is given by the distance between the incident vertices. The relevance of the study of various algorithms for solving the Steiner problem on directed graphs given in the Euclidean space/plane is determined. Scientific novelty: the use of a distance matrix between vertices in the description of a directed graph. Computer program development for solving the Steiner problem on directed graphs. The introduction gives a general description of the work, substantiates the relevance of research, formulates the purpose of the work, reveals the scientific novelty and practical significance of the results obtained. A brief overview of the content of the work is given in sections. In the first section, an overview of the subject area is given and the classical formulations of the Steiner problem are presented, and the main exact and approximate algorithms for solving the Steiner problem on directed graphs are considered. In the second section, a theoretical analysis of the task is carried out. A basic model of the study object is presented in the form of a distance matrix describing the initial graph, as well as an output binary matrix of mappings, which is used to display the minimal Steiner tree obtained from the results of using the selected algorithm for solving the Steiner problem with image to the original distance matrix. The substantiation of the choice of exact methods for solving the Steiner problem on directed graphs and two approximate methods for solving this problem is given. A model of visualization of the required minimal Steiner tree is also given. The third section provides a detailed description of the methodology for solving the problem. The fourth section provides a practical implementation of the solution to the problem in the form of a program that implements the operation of the algorithms described in the third section to provide the possibility of conducting experimental studies. The fifth section describes the experiments done to study the qualitative and quantitative indicators of the algorithms. Conclusions on the applicability of algorithms for solving the Steiner problem are formulated and recommendations are made on their use. In the conclusion, the main results of the research are presented in detail. Student: Gorbacheva Arina Andreevna Academic Supervisor: Mokeev Dmitry Borisovich