Abstract:
Graph models occupy an important place in tasks related to information security, including the construction of models and methods for managing the continuous operation of systems and system recovery, countering denials of service. Finite dynamic systems of complete graphs orientations are considered. States of a dynamic system are all possible orientations of a given complete graph, and evolutionary function transforms the given complete graph orientation by reversing all arcs that enter into sinks and there are no other differences between the given and the next digraphs. In this paper, the algorithm to calculate indices of system states is proposed. Namely, the index of the state is equal to 0 if it does not have a sink or its indegrees vector (a vector whose components are the degrees of entry of all its vertices located in descending order) contains all possible degrees of entry, otherwise its index is equal to the power of the largest set of consecutive degrees of entry, starting with the maximum possible degree, which is a subvector of its indegrees vector. As a consequence, the states with non-zero index belong to a basin with an attractor of length 1, whose generator state has a source and no sink. The maximal index of the states in the system is found. The corresponding tables are given for complete graphs with the number of vertices from 1 to 8 inclusive.
Fulltext:
PDF file (381 kB)