ド・ブラウン・グラフ

グラフ理論において、個の記号からなる次元ド・ブラウン・グラフ（De Bruijn graph）は、記号の列間の重複を表現する有向グラフである。このグラフは個の頂点を持ち、それらの頂点は与えられた記号から構成される考えうるすべてのの列からなる。同じ記号が列内に複数回現れてもよい。このようなグラフはしばしばと表記される。個の記号の集合 } に対し、頂点集合は次のようになる。

ある頂点のすべての記号を1つ左へシフトし、その終端に新しい記号を付け加えたものが別の頂点に一致する場合、前者の頂点から後者の頂点への有向辺が存在する。したがって、弧（すなわち有向辺）の集合は次のようになる。

ド・ブラウン・グラフはニコラース・ホーヴァート・ド・ブラウンにちなんで名付けられているが、ド・ブラウンとによって独立に考案された。それよりずっと以前に、Camille Flye Sainte-Marieがその性質を暗黙的に使用していた。

性質の場合、任意の2つの頂点が辺を形成するための条件は自明に満たされるため、すべての頂点が連結され、合計本の辺が形成される。各頂点の入次数と出次数はともに、ちょうどである。各次元ド・ブラウン・グラフは、同じ記号集合を持つド・ブラウン・グラフの有向である。各ド・ブラウン・グラフはオイラーグラフでありハミルトングラフである。これらのグラフのオイラー閉路およびハミルトン閉路（線グラフの構成を介して互いに等価である）はである。

最も小さい3つの2値ド・ブラウン・グラフの線グラフとしての構成を以下に示す。図からわかるように、次元ド・ブラウン・グラフの各頂点はド・ブラウン・グラフの辺に対応し、次元ド・ブラウン・グラフの各辺はド・ブラウン・グラフの長さ2の路に対応している。

力学系 2値ド・ブラウン・グラフは、ローレンツ・アトラクタのような力学系の理論におけるオブジェクトに似るように描画できる。

この類似性は厳密なものにできる。次元記号のド・ブラウン・グラフは、以下ののモデルである。

ベルヌーイ写像（の場合はとも呼ばれる）はエルゴード的な力学系であり、種類の記号列に対する片側シフトであると理解できる。この力学系の軌道はド・ブラウン・グラフ上の歩道（walk）に対応し、その対応関係は、区間内の各実数を、の進法表現における最初の桁に対応する頂点にマッピングすることで与えられる。等価な表現として、ド・ブラウン・グラフ上の歩道は片側における軌道に対応する。

thumb|upright=1.35|2つのと1つの配列の有向グラフ。では各頂点を1回ずつ訪問するのに対し、では各辺を1回ずつ通過する。

これに似た埋め込みを使用することで、2値ド・ブラウン・グラフが2のを持つこと、および5以下のを持つことを示すことができる。

用途一部ののトポロジーはド・ブラウン・グラフである。分散ハッシュテーブルプロトコルであるはド・ブラウン・グラフを使用している。バイオインフォマティクスにおいて、ド・ブラウン・グラフはシーケンシングリードをゲノムへと組み立てるに使用される。考えうるすべての k-mer を含む上記の完全なド・ブラウン・グラフの代わりに、de novo シーケンスアセンブラは、シーケンシングデータセット内で観測された k-mer のみを含むド・ブラウン部分グラフを利用する。時系列予測において、観測値の離散的な部分列（n-gram）をグラフのノードにマッピングすることにより、時間的パターンをエンコードするようド・ブラウン・グラフが適応されてきた。これにより、記号的または離散化された時系列データにおける順次的な依存関係のモデリングが可能になる。多変量ド・ブラウン・グラフはこのアイデアを拡張し、複数の相関する変数にわたるパターンを結合してエンコードすることで、多変量時系列における複雑な変数間の時間的ダイナミクスの表現を可能にする。

ド・ブラウン・グラフ

Źródło i licencja