グラフ理論では、m個のシンボルのn次元De Bruijnグラフは、シンボルのシーケンス間の重なりを表す有向グラフである。与えられたシンボルのすべての可能な長さnのシーケンスからなるmn個の頂点を持ちます。同じシンボルが連続して複数回現れることがあります。 m個の記号${\displaystyle S:=\{s_{1},\dots ,s_{m}\}}$のセットを持つと、頂点の集合は次のようになります。
${\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})\}.}$
頂点の1つが、そのシンボルをすべて1つ左にシフトし、この頂点の最後に新しいシンボルを追加することによって頂点の1つが別の頂点として表現される場合、後者は前の頂点への有向エッジを有する。したがって、アークのセット（別名有向エッジ）は次のようになります。
${\displaystyle E=\{((v_{1},v_{2},\dots ,v_{n}),(v_{2},\dots ,v_{n},s_{i})):i=1,\dots ,m\}.}$
De BruijnグラフはNicolaas Govert de Bruijnにちなんで命名されましたが、De BruijnとI.J. Goodの両方で独立して発見されました。以前は、Camille Flye Sainte-Marieは暗黙のうちにそのプロパティを使用していました。