Aperiodic graph
Encyclopedia
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
area of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
is said to be aperiodic if there is no integer k > 1 that divides the length of every cycle
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
of the graph. Equivalently, a graph is aperiodic if the greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
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 graphBipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
, all cycles have a length that is divisible by two. Therefore, no directed bipartite graph can be aperiodic. In any directed acyclic graph
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
, it is a vacuous truth
Vacuous truth
A vacuous truth is a truth that is devoid of content because it asserts something about all members of a class that is empty or because it says "If A then B" when in fact A is inherently false. For example, the statement "all cell phones in the room are turned off" may be true...
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
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
, 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 strongly connected and that k divides the lengths of all cycles in G.Consider the results of performing a depth-first search
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
of G, starting at any vertex, and assigning each vertex v to a set Vi where i is the length (taken mod k) of the path in the depth-first search tree from the root to v. It can be shown that this partition into sets Vi has the property that each edge in the graph goes from a set Vi to another set V(i + 1) mod k. Conversely, if a partition with this property exists for a strongly connected graph G, k must divide the lengths of all cycles in G.
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
Strongly connected component
A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a path from b to a....
of G, ignoring the edges that pass from one strongly connected component to another.
Jarvis and Shier describe a very similar algorithm using breadth first search in place of depth-first search; the advantage of depth-first search is that the strong connectivity analysis can be incorporated into the same search.
Applications
In a strongly connected graphStrongly connected component
A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a path from b to a....
, if one defines a Markov chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
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 road coloring problem. According to the solution of this problem , a strongly connected directed graph in which all vertices have the same outdegree has a synchronizable edge coloring if and only if it is aperiodic.