Графы де Брюина

2017-12-02T19:58:33Z

178.71.28.215: /* Использование графов де Брюина */

== Основные определения ==

{{Определение
|id = de_bruijn_graph
|definition = '''Графом де Брюина''' (англ. ''De Bruijn graph'') с параметром <tex>l</tex> для <tex>n</tex>-буквенного алфавита называется ориентированный граф <tex>G(V, E)</tex>, где <tex> V - </tex> множество всех слов длины <tex>l</tex> в заданном алфавите, и <tex>e = (u, v) \in E \Leftrightarrow \exists </tex> слово <tex>L</tex> длины <tex>l+1</tex> в заданном алфавите такое, что <tex> u = prefix(L) \wedge v = suffix(L) </tex>
}}

== Основные свойства ==
* <tex> |V| = n^l </tex>. Очевидно из определения <tex> V </tex>.
* <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>

== Использование графов де Брюина ==

{{Задача
|definition =
Известно, что пароль имеет длину <tex> l </tex>, и состоит из цифр от 1 до <tex> n </tex>. Требуется вывести кратчайшую последовательность цифр, которая гарантированно содержит пароль как подстроку.
}}

'''Решение''':

1. Составим граф де Брюина <tex> (n, l-1) </tex>.

2. Найдём в построенном графе эйлеров цикл. Он существует, так как граф де Брюина эйлеров (см. свойства)

3. Слово, соответствующее первой вершине цикла, возьмём полностью (<tex> l - 1 </tex> символов), затем будем последовательно добавлять в конец строки последний символ слова вершины, в которую был осуществлён переход. Так как рёбер <tex> n^l </tex>, получим последовательность длиной <tex> n^l + l - 1 </tex>.

'''Корректность''':

1. Очевидно, что последовательность меньшей длины составить нельзя: в полученной последовательности ровно <tex> n^l </tex> подстрок длины <tex> l </tex>, и именно столько чисел можно составить из цифр от 1 до <tex> n </tex>.

2. Двум разным рёбрам <tex> e_1 = (u_1, v_1), e_2 = (u_2, v_2) </tex> соответствует два ''различных'' слова <tex> L </tex> длины <tex> l </tex>. Иначе <tex> u_{1} = prefix(L) = u_{2} \wedge v_{1} = suffix(L) = v_{2} </tex>. То есть это одно и то же ребро, при этом кратных рёбер в графе нет.

3. Отсюда следует, что в последовательности содержится <tex> n^l </tex> различных подстрок длины <tex> l </tex>. И короче последовательность получить нельзя. Значит, мы получили ответ за <tex> O((|E| \cdot (l-1)) + (|E| + |V|)) = O(|E| \cdot (l-1)) </tex>, то есть за время построения графа де Брюина <tex> (n, l-1) </tex>.

Викиконспекты - Вклад участника [ru]

Графы де Брюина