De Bruijn graph とは

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