Изменения
Нет описания правки
{{Определение
|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 </tex> и <tex> v = suffix(L) </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>
{{Задача
|definition =
Известно, что пароль имеет длину <tex> l </tex>, и состоит из цифр от <tex> 1 </tex> до <tex> n </tex>. Требуется вывести кратчайшую последовательность цифр, которая гарантированно содержит пароль как подстроку.
}}
'''Корректность''':
1. Очевидно, что последовательность меньшей длины составить нельзя: в полученной последовательности ровно <tex> n^l </tex> подстрок длины <tex> l </tex>, и именно столько чисел можно составить из цифр от <tex> 1 </tex> до <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>. То есть это одно и то же ребро, при этом кратных рёбер в графе нет.
'''Пояснение''':
Геном (как и его части <tex> - </tex> риды) является словом из 4-символьного алфавита <tex> \{A, G, C, T\} </tex>, где символы так же называются нуклеотидами. В реальности длины ридов находятся обычно в диапазоне <tex> 100</tex>-<tex> 1000 </tex> нуклеотидов, а геном может содержать от <tex> 10^6 </tex> нуклеотидов у простейших организмов. При этом учёные могут получать информацию только о ридах (в силу размера последовательностей) физическим путем (''метод секвенирования'').
'''Решение''':
'''Комментарий''':
К сожалению, в реальности есть очень много проблем (кроме того, что алгоритм работает за <tex> O(4^l \cdot l) </tex>). Во-первых, как можно догадаться из пояснения: едва ли риды обязательно будут неповторяющимися. Во-вторых, данные о ридах тоже получаются с некоторой вероятностью (как правило, ошибка в нуклеотиде имеет вероятность около <tex> 0.001</tex>, но вблизи "края" генома может достигать и <tex> 0.3</tex>). В-третьих, риды не могут иметь фиксированную длину. Таким образом, задача решается за экспоненциальное время, и с довольно жёсткими условиями на входные данные. Однако многие реальные ''ассемблеры'', собирающие геномы (или их части, заметно превышающие размер рида), действительно используют идеи графа де Брюина, но более усложнённые.
== См. также ==
