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