|
This article is cited in 1 scientific paper (total in 1 paper)
Applied Theory of Automata and Graphs
On attractors in finite dynamic systems of complete graphs orientations
A. V. Zharkova Saratov State University, Saratov
Abstract:
Finite dynamic systems of complete graphs orientations are considered. The states of such a system $S=(\Gamma_{K_n},\alpha)$, $n>1$, are all possible orientations $G$ of the complete graph $K_n$, and evolutionary function $\alpha$ transforms a given state $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. The following criterion for belonging states to attractors in $S$ is given: a state $G$ belongs to an attractor if and only if it hasn't a sink or its indegrees vector is a permutation of numbers $0,1,\dots,n-1$. All attractors in $S$ are the attractors of length $1$, each of which consists of states without sinks, and the attractors of length $n$, each of which consists of states with indegrees vectors being permutations of numbers $0,1,\dots,n-1$. Any such an attractor represents a circuit, for every state $G$ in which if the indegrees vector of $G$ is $(d^-(v_1),d^-(v_2),\dots,d^-(v_n))$, then the indegrees vector of $\alpha(G)$ is $(d^-(v_1)+1,d^-(v_2)+1,\dots,d^-(v_n)+1)$, where the addition is calculated modulo $n$. Note that in system $S$, the number of attractors of length $n$ is equal to $(n-1)!$ and the number of states belonging to them is equal to $n!$.
Keywords:
attractor, complete graph, evolutionary function, finite dynamic system, graph, graph orientation.
Citation:
A. V. Zharkova, “On attractors in finite dynamic systems of complete graphs orientations”, Prikl. Diskr. Mat. Suppl., 2016, no. 9, 112–114
Linking options:
https://www.mathnet.ru/eng/pdma304 https://www.mathnet.ru/eng/pdma/y2016/i9/p112
|
Statistics & downloads: |
Abstract page: | 105 | Full-text PDF : | 33 | References: | 24 |
|