Applied Theory of Automata and Graphs
On indices of states in finite dynamic systems of complete graphs orientations
A. V. Zharkova Saratov State University
Abstract:
Finite dynamic systems of complete graphs orientations are considered.
The states of such a system
$(\Gamma_{K_n},\alpha)$,
$n>1$, are all possible orientations of a given complete graph
$K_n$, and evolutionary function
$\alpha$ transforms a given state (tournament)
$G$ by reversing all arcs in
$G$ that enter into sinks, and there
are no other differences between the given
$G$ and the next
$\alpha(G)$ states.
In this paper, the algorithm for calculating indices of states in finite dynamic systems of complete graphs orientations is proposed.
Namely, in the considered system
$(\Gamma_{K_n},\alpha)$,
$n>1$, the index of the state
$G\in \Gamma_{K_n}$ is 0 if and only if it hasn't a sink or its indegrees vector
$(d^{-}(v_1),d^{-}(v_2),\ldots,d^{-}(v_n))$ is a permutation of numbers
$\{0,1,\ldots,n-1\}$.
If these conditions for this state
$G$ are not met, then its index is
$f$, where
$f$ is the power of the largest set of the form $\{n-1,n-2,\ldots, n-f\}\subseteq\{d^{-}(v_1),d^{-}(v_2),\ldots,d^{-}(v_n)\}$.
The maximal index of the states in the system is found: it is equal to
$0$ for
$n=2$ and
$n-3$ for
$n>2$.
The corresponding table is given for the finite dynamic systems of orientations of complete graphs with the number of vertices from
$2$ to
$7$.
Keywords:
complete graph, evolutionary function, finite dynamic system, graph,
graph orientation, index, tournament.
UDC:
519.1
DOI:
10.17223/2226308X/12/49
Fulltext:
PDF file (598 kB)