Изменения

* <tex> l = 1 \Leftrightarrow G - </tex> полный граф. Действительно, для любых (необязательно различных) вершин <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>.* <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> G - </tex> эйлеров. Это следует из предыдущего свойства, так как <tex> deg(v) = 0 </tex>.* <tex> e = (u, v) \in E \Leftrightarrow </tex> <tex> prefix_{l-1}(v) = suffix_{l-1}(u) </tex>. <tex> \Leftarrow </tex>Составим слово <tex> L = a \gamma b </tex>, где <tex> \gamma - </tex> общая часть слов, соответствующих вершинам <tex> u, v </tex>. А символы <tex> a, b \ - </tex> первый и последний символ этих слов соответственно. Из определения графа де Брюина следует, что ребро существует. <tex> \Rightarrow </tex>Возьмём подстроку слова <tex> L </tex> (из определения) без крайних символов (её длина <tex> l - 1 </tex>). Так же из определения следует, что это будет суффиксом строки, соответствующей вершине <tex> u </tex>, и префиксом для строки, соответствующей <tex> v </tex>. == Алгоритм построения == {{Задача|definition =Дан алфавит длины <tex> n </tex> и длина слов <tex> l </tex>. Построить по ним граф де Брюина.}}'''Алгоритм: ''' 1. Создаём пустой граф из <tex> n^l </tex> вершин. 2. Генерируем слово длины <tex> l+1 </tex>. 3. Считаем префикс <tex> pref </tex> и суффикс <tex> suff </tex> длины <tex> l </tex> для текущего. Причём установим в алфавите отношение порядка и будем рассматривать его символы как цифры в <tex> n </tex>-значной системе счисления.  4. Проводим ребро <tex> (pref, suff) </tex> в графе. Переходим к п.2 (например, будем перебирать в порядке лексикографического возрастания), пока не будут перебраны все слова длины <tex> l+1 </tex>. '''Корректность''': перебраны все слова длины <tex> l+1 </tex>, следовательно, были рассмотрены все возможные пары вершин, между которыми проведено ребро. '''Время работы''': <tex> O(n^{l+1} \cdot substring) = O(|E| \cdot l) </tex> == Использование графов де Брюина ==