|
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.
Citation:
A. V. Zharkova, “On indices of states in finite dynamic systems of complete graphs orientations”, Prikl. Diskr. Mat. Suppl., 2019, no. 12, 176–179
Linking options:
https://www.mathnet.ru/eng/pdma464 https://www.mathnet.ru/eng/pdma/y2019/i12/p176
|
|