|
This article is cited in 1 scientific paper (total in 1 paper)
Applied Theory of Coding and Graphs
The finite dynamic system of all possible orientations of a given graph with all accessible states and with inaccesible states
A. V. Zharkova Saratov State University
Abstract:
The finite dynamic systems $(\Gamma_G, \alpha)$ is considered, the states of which are all possible orientations of a given graph $G$, and the evolutionary function $\alpha$ transforms a given state $\overrightarrow{G}$ by reversing all arcs in $\overrightarrow{G}$ that enter into sinks, and there are no other differences between the given $\overrightarrow{G}$ and the next $\alpha(\overrightarrow{G})$ states. We characterize the systems in which all states are accessible and in which there are inaccessible states. Namely, in a finite dynamic system $(\Gamma_G,\alpha)$ all states are accessible if and only if the (connected) components in the graph $G$ are complete graphs with $n$ vertices for $1\leq n\leq3$ and only they. Otherwise, the system under consideration has inaccessible states. The number of graphs forming systems with all accessible states is counted. Namely, the number of graphs $G$ with $n$ vertices that form finite dynamic systems $(\Gamma_G,\alpha)$, all states of which are accessible, is equal to $1+\left\lfloor{n}/{2}\right\rfloor+\left\lfloor{n}/{3}\right\rfloor+\sum\limits_{i=1}^{\left\lfloor (n-3)/{2}\right\rfloor}\left\lfloor(n-2i)/{3}\right\rfloor$. The table is given with the number of graphs with the number of vertices from 1 to 12, forming systems with all accessible states and with inaccessible states.
Keywords:
accessible state, directed graph, evolutionary function, finite dynamic system, fault-tolerance, graph, inaccessible state.
Citation:
A. V. Zharkova, “The finite dynamic system of all possible orientations of a given graph with all accessible states and with inaccesible states”, Prikl. Diskr. Mat. Suppl., 2022, no. 15, 105–107
Linking options:
https://www.mathnet.ru/eng/pdma589 https://www.mathnet.ru/eng/pdma/y2022/i15/p105
|
Statistics & downloads: |
Abstract page: | 72 | Full-text PDF : | 54 | References: | 17 |
|