51
правка
Изменения
→Применение графов де Брюина
Известно, что пароль имеет длину <tex> l </tex>, и состоит из цифр от <tex> 1 </tex> до <tex> n </tex>. Требуется вывести кратчайшую последовательность цифр, которая гарантированно содержит пароль как подстроку.
}}
[[Файл: De_brujin_binary_graph.png|справа|300px|thumb|Построенный граф Де Брюина для двоичного алфавита со словами <tex> L </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 </tex> и <tex> 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>.
Даны неповторяющиеся последовательности ''нуклеотидов'' (''риды'') длины <tex> l </tex>. Известно, что все подстроки генома длины <tex> l </tex> входят в данное множество ридов. Построить возможный геном.
}}
[[Файл: De Brujin Graph In Science.png|справа|300px|thumb|Подграф графа Де Брюина для ридов, указанных на рёбрах. Искомый геном: '''ACGTACTAT''']]
'''Пояснение''':
'''Решение''':
Решение этой задачи очень простое после решения предыдущей задачи. Построим граф G, где вершинами будут являться суффиксы и префиксы длины <tex> l - 1 </tex> всех ридов. Получили подграф графа де Брюина <tex> (4, l-1) </tex> (подграф, так как в нём есть не обязательно все <tex> 4^{l - 1} </tex> вершины), где каждому ребру соответствует рид. Найдём в нём эйлеров циклпуть. Он существует, так как на геном было наложено условие о том, что все его подстроки длины <tex> l </tex> входят в наше множество ридов. Этот цикл путь является возможным ответом. Очевидно, что единственно верный ответ (коим является реальный геном реального существа) получить мы можно не сможемвсегда, потому что так как не всегда в графе есть единственный эйлеров цикл может быть не единственным, и цикл можно сдвигатьпуть.
'''Комментарий''':
