Normal form of (0,1)-matrixes and algorithms of its construction
Existing preconditions for defining of normal form of square (0,l)-matnx are discussed, new theoretical results, which were the basis for defining a normal form of (0,l)-matrix are proved. There exists a particular definition of the matrix canonical form for different classes and different kinds of conversions. The most well known are the canonical appearance of a decomposable matrix and an imprimitive matrix. The definition of a normal form of a square (0,l)-matrix is given by means of the canonical appearance of those matrix. Due to the strict connection of a square (0,l)-matrix with a graph matrix and the fact that a graph is given accurate within isomorphism, the problem appears to pick out a representative, the simplest one, from the class of isomorphic graphs. Such representative is defined as the graph normal form. It is noted that all the results which are valid for a normal form of a square (0,l)-matrix can be applied to a normal form of a graph matrix. The algorithm of construction of a normal form of (0,l)-matrix based on determinations of the types of graph connectivity is given. A classical problem of graph theory - separation of graph connectivity components - is simultaneously solved in constructing a normal form of a graph matrix.