De Bruijn Graph

A De Bruijn Graph is a directed graph that represents overlaps between sequences of symbols.

• See: Graph Theory, Graph Vertex, De Bruijn Sequence.

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/De_Bruijn_graph Retrieved:2015-11-2.
  • In graph theory, an n-dimensional 'De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mⁿ vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence. If we have the set of m symbols [math]\displaystyle{ S:=\{s_1,\dots,s_m\} }[/math] then the set of vertices is: : [math]\displaystyle{ V=S^n=\{(s_1,\dots,s_1,s_1),(s_1,\dots,s_1,s_2),\dots,(s_1,\dots,s_1,s_m),(s_1,\dots,s_2,s_1),\dots,(s_m,\dots,s_m,s_m)\}. }[/math] If one of the vertices can be expressed as another vertex by shifting all its symbols by one place to the left and adding a new symbol at the end of this vertex, then the latter has a directed edge to the former vertex. Thus the set of arcs (aka directed edges) is : [math]\displaystyle{ E=\{((v_1,v_2,\dots,v_n),(v_2,\dots,v_n,s_i)) : i=1,\dots,m \}. }[/math] Although De Bruijn graphs are named after Nicolaas Govert de Bruijn, they were discovered independently by both De Bruijn and I. J. Good. Much earlier, Camille Flye Sainte-Marie implicitly used their properties.

---