51
правка
Изменения
Нет описания правки
|about = о количестве вершин и рёбер в графе
|statement= В графе де Брюина <tex> B(n, l): |V| = n^l, |E| = n^{l+1}</tex>
|proof= Число вершин очевидно находится из определения графа и равно <tex> n^l </tex>. Число рёбер следует из доказательства предыдущей леммы: каждой вершине инцидентно ровно <tex> 2 </tex> ребра. Таким образом, <tex> |E| = \frac{1}{2} \cdot n^l \cdot 2n = n^{l+1} </tex>
}}
3. Считаем префикс <tex> pref </tex> и суффикс <tex> suff </tex> длины <tex> l </tex> для текущего. Причём установим в алфавите отношение порядка и будем рассматривать его символы как цифры в <tex> n </tex>-значной системе счисления.
4. Проводим ребро <tex> (pref, suff) </tex> в графе. Переходим к п.<tex> 2 </tex> (например, будем перебирать в порядке лексикографического возрастания), пока не будут перебраны все слова длины <tex> l+1 </tex>.
'''Корректность''': перебраны все слова длины <tex> l+1 </tex>, следовательно, были рассмотрены все возможные пары вершин, между которыми проведено ребро.
1. Составим граф де Брюина <tex> (n, l-1) </tex>.
2. Найдём в построенном графе эйлеров цикл. Он существует, так как граф де Брюина эйлеров по первой лемме 1.
3. Слово, соответствующее первой вершине цикла, возьмём полностью (<tex> l - 1 </tex> символов), затем будем последовательно добавлять в конец строки последний символ слова вершины, в которую был осуществлён переход. Так как рёбер <tex> n^l </tex>, получим последовательность длиной <tex> n^l + l - 1 </tex>.
