De Bruijn Graph

DEFINITION

In Graph Theory , an

n

-dimensional de Bruijn graph of

m

symbols is a Directed Graph with

m^n

vertices and the edges defined as below.

The vertices consist of all possible

n

way combinations of the

m

symbols. If we have the symbols

s_1,\cdots,s_m

then the set of vertices is:

:

V=\{(s_1,\cdots,s_1,s_1),(s_1,\cdots,s_1,s_2),\cdots,(s_m,\cdots,s_m,s_m)\}

If one of the vertices can be expressed by shifting all symbols by one place to the left and adding a new symbol at the end of another vertex, then the latter has a directed edge to the former vertex. Thus the set of (directed) edges is:

:

E=\{((v_1,v_2,\cdots,v_n),(w_1,w_2,\cdots,w_n)) : v_2=w_1,v_3=w_2,\cdots,v_n=w_{n-1}\}

Properties

If $n=1$ then the condition for any two vertices forming an edge holds vacuously, and hence all the vertices are connected forming a total of $m^2$ edges.

Each vertex has exactly $m$ incoming and $m$ outgoing edges.

EXAMPLES

For simplified notation, let our symbols be the Whole Numbers 1,2,3,etc. Then, following are some examples of de Bruijn graphs.

de Bruijn (2,1) : 2 symbols and 1 dimension

de Bruijn (2,2) : 2 symbols and 2 dimensions

de Bruijn (3,2) : 3 symbols and 2 dimensions

	CATEGORIES ABOUT DE BRUIJN GRAPH

	graphs

	graph families

	dynamical systems

	automata theory

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

Information About

De Bruijn Graph