SOLVING APPLIED PROBLEMS USING BASIC ALGORITHMIC PRIMITIVES OF GRAPH THEORY

Abstract

The possibility of formulating applied problems in terms of graph theory is considered. In particular, the problems of the optimal structure of the enterprise, control over financial operations, and determination of the optimal sequence of works are considered. An approach to solving such problems using algorithmic primitives on graphs is implemented. The use of graphs as models of many applied problems is due to both the clarity of the concept of a graph and the availability of exact algorithms on graphs with polynomial complexity.The process of solving the problem of constructing an optimal structure sequentially includes the calculation of strongly connected components on the graph of the problem, the construction of a graph of components, and topological sorting of the graph of components in order to transition to a linear structure. The optimal structure of the enterprise is understood as a linear ordering of its subdivisions. The method of solving the problem of control over financial operations is based on the properties of depth-first search for an acyclic graph. The classification of edges of a depth-first search forest allows us to make certain assumptions about hidden connections in the presence of reverse edges. It is worth noting that the proposed method does not give an answer about the quantitative nature of the connection, fixing only its fact. A partial case of the general linear programming problem is the problem of determining the sequence of work execution, given by a system of difference constraints. Solving a system of difference constraints is reduced to calculating the weight of the shortest path in the corresponding constraint graph. To calculate the shortest path from one vertex, the Bellman–Ford Algorithm was used, the application of which allows obtaining a result even in the presence of edges of negative weight.The correctness of theoretical considerations is confirmed by practical calculations using specially developed software. The calculations were performed in the Mathcad v. 13 environment. The corresponding procedures STRONG_ COMP, DFS_CTRL, BELL_FORD_CONST were developed.