NEIGHBORHOODS IN PROBLEMS OF DISCRETE MATHEMATICS

This article develops and extends the results previously published on the initiative of Academician V. M. Glushkov [1, 2]. We provide a Peta lled analysis of the concept of ''neighborhood,'' which is basic not o nly to the theory of local algorithms but also to other approaches to the solution of problems of discrete mathematics. The importance of th is concepts stems from the fact that many characteristics describing p roblems of discrete mathematics are inherently local. Virtually all pr oblems of discrete mathematics have the following general structure. G iven is a system of sets (M), M = {U-1, U-2,..., U-n} = {U}. On each s et M of this system are defined the relations R(1), R(2),..., R(rho). It is required to evaluate some predicates P-1, P-2,..., P-l defined o n the couples [U, M]. For instance, for problems in graphs, the set M is some graph G defined by its edges and isolated vertices, U-1, are t he edges and the isolated vertices, R(1) is a function from M to C-+ w eighting the edges of the graph, R(2) is a binary relation, which is a relation for the edges of the graph G, P-1 is a predicate that define s some property of the edge a in the graph, for instance, the membersh ip of the edge a in the minimum covering of the vertices of the graph G by its edges.