This article is cited 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.

UDC: 519.1

DOI: 10.17223/2226308X/9/44