The neural network analysis of colored graphs

The article deals with the problem of colored graph identification. This problem arises when solving tasks in the subject area which is formalized in terms of graph theory including cases connected with the investigation of “chemical structure - property” dependence. The authors propose the model of chemical structure in the form of a colored graph. The upper bound for the algorithm complexity is obtained, and its feasibility is shown. The learning samples are represented by graphs with a given property. The problem solved in the paper is the method development and analysis allowing to identify the property of graph that is not included in the learning samples. To solve the problem it is proposed to use the mechanism of artificial neural network of the original structure, the principles of which differ significantly from generally accepted, which is in the signals form and signals distribution ways across the network. The graph analysis is based on simple chains statistics for which the breadth-first search algorithm is described, and the algorithm analysis is given. The proposed algorithm allows also to handle disconnected graphs and thus to analyze multi-component systems. The article presents the formal result of its training as a formula allowing to calculate the output signal for input signals vector. The use of artificial neural network for graphs identification is demonstrated. The obtained results represent mathematical software which enables creating a reasonable decision rules for a systems identification formalized in graph theory terms.