Aperiodic graph
In the mathematical area of graph theory, a directed graph is said to be aperiodic if there is no integer k > 1 that divides the length of every cycle of the graph. Equivalently, a graph is aperiodic if the greatest common divisor of the lengths of its cycles is one; this greatest common divisor for a graph G is called the period of G.
Graphs that cannot be aperiodic
In any directed bipartite graph, all cycle lengths are even. Therefore, no directed bipartite graph can be aperiodic. In any directed acyclic graph, it is a vacuous truth that every k divides all cycles (because there are no directed cycles to divide) so no directed acyclic graph can be aperiodic. And in any directed cycle graph, there is only one cycle, so every cycle's length is divisible by n, the length of that cycle.
Testing for aperiodicity
Suppose that G is
Thus, we may find the period of a strongly connected graph G by the following steps:
- Perform a depth-first search of G
- For each e in G that connects a vertex on level i of the depth-first search tree to a vertex on level j, let ke = j − i − 1.
- Compute the greatest common divisor of the set of numbers ke.
The graph is aperiodic if and only if the period computed in this fashion is 1.
If G is not strongly connected, we may perform a similar computation in each strongly connected component of G, ignoring the edges that pass from one strongly connected component to another.
Jarvis and Shier describe a very similar algorithm using
Applications
In a strongly connected graph, if one defines a Markov chain on the vertices, in which the probability of transitioning from v to w is nonzero if and only if there is an edge from v to w, then this chain is aperiodic if and only if the graph is aperiodic. A Markov chain in which all states are recurrent has a strongly connected state transition graph, and the Markov chain is aperiodic if and only if this graph is aperiodic. Thus, aperiodicity of graphs is a useful concept in analyzing the aperiodicity of Markov chains.
Aperiodicity is also an important necessary condition for solving the
References
- Jarvis, J. P.; Shier, D. R. (1996), "Graph-theoretic analysis of finite Markov chains", in Shier, D. R.; Wallenius, K. T. (eds.), Applied Mathematical Modeling: A Multidisciplinary Approach (PDF), CRC Press.
- .