---
tag: T2W58MMTWB
kind: concept
name: De Bruijn graph
aliases: [de-bruijn-diagram, de-bruijn-digraph]
sources:
  - wikipedia: en:2346823@r1368876410
    locator: De Bruijn graph
    note: adopted
    mention: wikipedia://en/2346823
    sections: [Summary]
same_as:
  wikidata: Q3066095
  wikipedia: De Bruijn graph
inventory: [N47SH1FQGG]
---

## Summary

In graph theory, an $n$-dimensional **De Bruijn graph** of $m$ symbols is a [[directed graph|0KFYGSHHF5]] representing overlaps between sequences of symbols. It has $m^{n}$ vertices, consisting of all possible length-$n$ sequences of the given symbols; the same symbol may appear multiple times in a sequence. For a [[set|0BSJ7RQ9BW]] of $m$ symbols $S = \{s_{1}, \ldots, s_{m}\},$ the set of vertices is: