Geodesic
On number of inaccessible states in finite dynamic systems of complete graphs orientations
Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 100-103
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, inaccessible state, index, sink, tournament.
Mots-clés : graph orientation, source 
@article{PDMA_2020_13_a28,
     author = {A. V. Zharkova},
     title = {On number of inaccessible states in finite dynamic systems of complete graphs orientations},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {100--103},
     year = {2020},
     number = {13},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2020_13_a28/}
}
TY  - JOUR
AU  - A. V. Zharkova
TI  - On number of inaccessible states in finite dynamic systems of complete graphs orientations
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2020
SP  - 100
EP  - 103
IS  - 13
UR  - http://geodesic.mathdoc.fr/item/PDMA_2020_13_a28/
LA  - ru
ID  - PDMA_2020_13_a28
ER  - 
%0 Journal Article
%A A. V. Zharkova
%T On number of inaccessible states in finite dynamic systems of complete graphs orientations
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2020
%P 100-103
%N 13
%U http://geodesic.mathdoc.fr/item/PDMA_2020_13_a28/
%G ru
%F PDMA_2020_13_a28
A. V. Zharkova. On number of inaccessible states in finite dynamic systems of complete graphs orientations. Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 100-103. http://geodesic.mathdoc.fr/item/PDMA_2020_13_a28/

[1] Barbosa V. C., An atlas of edge-reversal dynamics, Chapman/CRC, London, 2001 | MR | Zbl

[2] Khrennikov A., Nilsson M., “On the number of cycles of $p$-adic dynamical systems”, J. Number Theory, 90 (2001), 255–264 | DOI | MR | Zbl

[3] Salii V. N., “Ob odnom klasse konechnykh dinamicheskikh sistem”, Vestnik Tomskogo gosuniversiteta. Prilozhenie, 2005, no. 14, 23–26

[4] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, Nauka, M., 1997 | MR

[5] Zharkova A. V., “O vetvlenii i neposredstvennykh predshestvennikakh sostoyanii v konechnoi dinamicheskoi sisteme vsekh vozmozhnykh orientatsii grafa”, Prikladnaya diskretnaya matematika. Prilozhenie, 2013, no. 6, 76–78 | MR

[6] Zharkova A. V., “Nedostizhimye sostoyaniya v dinamicheskikh sistemakh, assotsiirovannykh s tsepyami i tsiklami”, Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika, 11:4 (2011), 116–123