Aperiodic graph

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 cycles have a length that is divisible by two. 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 strongly connected and that "k" divides the lengths of all cycles in "G".Consider the results of performing a depth-first search of "G", starting at any vertex, and assigning each vertex "v" to a set "V""i" 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 harv|Jarvis|Shier|1996 that this partition into sets "V""i" has the property that each edge in the graph goes from a set "V""i" 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", connecting a vertex on levels "i" of the depth-first search tree to a vertex on level "j", let "k""e" = "j" - "i" - 1.
* Compute the greatest common divisor of the set of numbers "k""e".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 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 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 road coloring problem. According to the solution of this problem harv|Trahtman|2007, 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.

References

*citation
contribution = Graph-theoretic analysis of finite Markov chains
last1 = Jarvis | first1 = J. P. | last2 = Shier | first2 = D. R.
year = 1996
url = http://www.ces.clemson.edu/~shierd/Shier/markov.pdf
editor1-last = Shier | editor1-first = D. R. | editor2-last = Wallenius | editor2-first = K. T.
title = Applied Mathematical Modeling: A Multidisciplinary Approach
publisher = CRC Press
.

*citation
title = The road coloring problem
last = Trahtman | first = A. N.
year = 2007
id = arxiv | 0709.0099
.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

  • Road coloring problem — In graph theory the road coloring theorem, known until recently as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from… …   Wikipedia

  • Markov chain — A simple two state Markov chain. A Markov chain, named for 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 …   Wikipedia

  • Perron–Frobenius theorem — In linear algebra, the Perron–Frobenius theorem, proved by Oskar Perron (1907) and Georg Frobenius (1912), asserts that a real square matrix with positive entries has a unique largest real eigenvalue and that the corresponding… …   Wikipedia

  • Periodic function — Not to be confused with periodic mapping, a mapping whose nth iterate is the identity (see periodic point). In mathematics, a periodic function is a function that repeats its values in regular intervals or periods. The most important examples are …   Wikipedia

  • mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… …   Universalium

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

  • Discrete geometry — A collection of circles and the corresponding unit disk graph Combinatorial geometry redirects here. The term combinatorial geometry is also used in the theory of matroids to refer to a simple matroid, especially in older texts. Discrete geometry …   Wikipedia

  • Order (mathematics) — Contents 1 In algebra 2 In arithmetic 3 In analysis 4 …   Wikipedia

  • Solar variation — Solar variations are changes in the amount of solar radiation emitted by the Sun. There are periodic components to these variations, the principal one being the 11 year solar cycle (or sunspot cycle), as well as aperiodic fluctuations. Solar… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”