Изменения
→Основные свойства
|id = lem1
|about = об эйлеровости графа
|statement= Граф де Брюина <tex> B(n, l)\ - </tex> эйлеров
|proof= Ориентированный граф является эйлеровым, если число входящих рёбер равно числу исходящих. Докажем, что это верно для <tex> B(n, l) </tex>. А именно, что <tex> \forall v \in V </tex> верно, что <tex> deg_{out}(v) = n = deg_{in}(v)</tex>. Докажем первое равенство, второе аналогично. Существует ровно <tex> n </tex> символов алфавита, которые можно добавить в конец слова <tex> \alpha</tex>, соответствующему вершине <tex> v </tex>. Получим ровно <tex> n </tex> различных слов. И у всех этих слов различные суффиксы длины <tex> l </tex>. Таким образом, из вершины <tex> v </tex> выходит ровно <tex> n </tex> рёбер и входит тоже <tex> n </tex> рёбер. Значит, граф де Брюина <tex> - </tex> эйлеров.
}}
|id = lem2
|about = о количестве вершин и рёбер в графе
|statement= В графе де Брюина <tex> B(n, l): \ |V| = n^l, |E| = n^{l+1}</tex>|proof= Число вершин очевидно находится из определения графа и равно <tex> n^l </tex>. Число рёбер следует из доказательства предыдущей леммы: каждой вершине инцидентно ровно <tex> 2 2n </tex> ребраребер. Таким образом, <tex> |E| = \frac{1}{2} \cdot n^l \cdot 2n = n^{l+1} </tex>
}}
|id = lem3
|about = о равносильном определении
|statement= В графе де Брюина <tex> B(n, l): e = \ (u, v) \in E \Leftrightarrow </tex> <tex> prefix_{l-1}(v) = suffix_{l-1}(u) </tex>
|proof= <tex> \Leftarrow </tex>
Составим слово длины <tex> l+1 \ L = a \gamma b </tex>, где тогда <tex> \gamma - b = suffix(L), a \gamma = prefix(L) </tex> общая часть слов, соответствующих вершинам . При этом <tex> u, v |a \gamma| = |\gamma b| = |L|-1 = l </tex>. А символы Если выбрать <tex> a, b \ - </tex> как первый и последний символ этих слов <tex> u, v </tex> соответственно. Из определения графа де Брюина следует, что и взять <tex> \gamma = prefix_{l-1}(v) = suffix_{l-1}(u) </tex>, то ребро существуетмежду этими вершинами есть по определению.
<tex> \Rightarrow </tex>Возьмём подстроку слова <tex> L </tex> (из определения) без крайних символов (её длина <tex> l - 1 </tex>). Так же из определения следует, что это будет суффиксом строки, соответствующей вершине <tex> u </tex>, и префиксом для строки, соответствующей <tex> v </tex>.
}}
|id = lem4
|about = о графе с <tex> l = 1 </tex>
|statement= Граф де Брюина <tex> B(n, 1) \ - </tex> полный граф.
|proof = Действительно, для любых (необязательно различных) вершин <tex> u, v \ \exists L = \alpha \beta </tex>, где <tex> \alpha, \beta - </tex> слова (символы), соответствующие вершинам <tex> u, v </tex>. И тогда очевидно, что существует ребро <tex> e = (u, v)\ \forall u, v \in V </tex>.
}}
