|
This article is cited in 1 scientific paper (total in 1 paper)
Applied Theory of Coding, Automata and Graphs
On number of inaccessible 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, formulas for calculating the number of inaccessible and the number of accessible states in finite dynamic systems of complete graphs orientations are given. Namely, in the considered system $(\Gamma_{K_n}, \alpha)$, $n>1$, the state ${G}\in \Gamma_{K_n}$ is inaccessible if and only if in this digraph ${G}$ there is no source and there is a sink. In the finite dynamic system $(\Gamma_{K_n}, \alpha)$, $n>1$, the number of inaccessible states is $n \big(2^{{(n-1)(n-2)}/{2}} - (n-1) 2^{{(n-2)(n-3)}/{2}}\big)$ and the number of accessible states is $2^{{n(n-1)}/{2}} - n \big(2^{{(n-1)(n-2)}/{2}} - (n-1) 2^{{(n-2)(n-3)}/{2}}\big)$. The corresponding table is given for the finite dynamic systems of complete graphs orientations with the number of vertices from $2$ to $10$.
Keywords:
accessible state, complete graph, evolutionary function, finite dynamic system, graph, graph orientation, inaccessible state, index, sink, source, tournament.
Citation:
A. V. Zharkova, “On number of inaccessible states in finite dynamic systems of complete graphs orientations”, Prikl. Diskr. Mat. Suppl., 2020, no. 13, 100–103
Linking options:
https://www.mathnet.ru/eng/pdma509 https://www.mathnet.ru/eng/pdma/y2020/i13/p100
|
Statistics & downloads: |
Abstract page: | 79 | Full-text PDF : | 33 | References: | 21 |
|