THE PROCEDURE OF GENERATING A MAXIMUM EMPTY SUB-GRAPHS
The practical significance of combinatorial problems is associated with the development of artificial intelligence, which has moved from the theoretical field to the demanded practical sphere. A large number of intelligent problems are naturally reformulated in the language of graphs, and their solution requires the use of graph-theoretic methods. In particular, a large number of tasks to describe a variety of subject areas is reduced to the so-called orthogonality graphs, which very naturally allow us to describe the different relations of objects of the subject area. In turn, for the study of orthogonality graphs, it is necessary to study the sets of their maximal empty subgraphs, which requires a sufficiently effective procedure for generating the latter. This should take into account certain conditions that must be satisfied by empty subgraphs. As a rule, the conditions are the consequences arising from the substantive restrictions on the objects of the subject area. Therefore, it seems relevant to create a procedure for generating in a certain sense a complete set of empty subgraphs for a given graph of orthogonality, which would allow to take into account the substantive features of the subject area. The latter should include, first and foremost, the attitude of the proximity objects, which allows to significantly reduce the bust with the product of the empty sub-graphs. The paper presents a theoretical basis for such a procedure generating a complete set of maximal empty subgraphs of a given orthogonality graph and a brief description of it. The procedure receives the adjacency matrix of the graph at the input, implemented in C++, and showed good results in the generation of objects of the domain specified by the orthogonality graph. Its distinctive feature is the ability to take into account the different ratios of locality of objects of the subject area, which significantly speeds up the work.