De Bruijn graph
De Bruijn graph — граф де Брёйна.
The De Bruijn graph is a directed graph of order whose vertices comprise the set . The arcs of connect each vertex , where and , to vertices and .
The De Bruijn graph of symbols is a directed graph representing overlaps between -sequences of a symbols. has vertices from . The arcs of connect each vertex to a vertex such that .
The De Bruijn undirected graph, denoted , is obtained from by deleting the orientation of all directed edges and omitting multiple edges and loops. Clearly, is a complete graph of order .