Изменения

{{Определение|definition =Пусть задан граф '''Формулировка задачи:''' По заданному слову <tex>GX[0..m-1]</tex>, тогда его рёберным графом найти в тексте или словаре <tex>L(G)</tex> называется Y[[Основные_определения_теории_графов|граф0..n-1]], для которого верны следующие утверждения* любая вершина графа <tex>L(G)</tex> представляет ребро графа <tex>G</tex>все слова,* две вершины графа <tex>Lсовпадающие с этим словом (Gили начинающиеся с этого слова)</tex> смежны тогда и только тогда, когда их соответствующие рёбра смежны в с учетом <tex>Gk</tex>возможных различий.}}

[[Файл:Line_graph_example.png|400px|thumb|center|Граф G и его реберный граф L(G)]]==СвойстваОписание задачи с точки зрения динамического программирования==Пусть <tex>d_{{Утверждение|statement=Рёберный граф [[Отношение_связности,_компоненты_связности|связного графа]] связен.|proof= Если G связенi, он содержит [[Основные_определения_теории_графов|путь]], соединяющий любые два его ребра, что переводится в путь графа L(G), содержащий любые две вершины графа L(G).j}}{{Утверждение|statement=Задача о максимальном независимом множестве для рёберного графа соответствует задаче нахождения максимального паросочетания в исходном графе. }}{{Утверждение|statement=Рёберное [[Раскраска_графа#chromatic_number_difinition|хроматическое число]] графа </tex> - расстояние между префиксами строк <tex>x</tex> и <tex>Gy</tex> равно вершинному хроматическому числу его рёберного графа , длины которых равны, соответственно, <tex>L(G)i</tex>.}}{{Утверждение|statement=Рёберный граф рёберно-транзитивного графа является вершинно-транзитивным графом.}}{{Утверждение|statement=Если граф и <tex>Gj</tex> [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров граф]], то его рёберный граф является [[Гамильтоновы_графы|Гамильтоновым графом]].есть|proof=Для доказательства приведем контрпример к обратному утверждению. На следующем рисунке граф <tex>Ld_{i,j} = d(x(1,i), y(G1,j))</tex> {{---}} Гамильтонов граф, а граф .Чтобы решить задачу <tex>Gk</tex> не является Эйлеровым графом.различий, [[Файлwikipedia:ru:Line_graph_gam_euler.PNGМатрица_расстояний|300pxматрицу расстояний]]}}{{Утверждение|statement=Ребра графа надо преобразовать таким образом, чтобы <tex>Gd_{i,j}</tex> можно разбить на полные подграфы таким образом, чтобы ни одна из вершин не принадлежала более чем двум подграфам.}}{{Утверждение|statement=Реберный граф реберного графа представлял минимальное расстояние между <tex>Lx(G1, i)</tex> '''не''' является исходным графом и любой подстрокой <tex>y</tex>, заканчивающейся символом <tex>Gy_j</tex>.}}Для этого достаточно ввести условие:

{{Теорема|id=Теорема1|statement=Если <tex>G</tex> {{---}} это <tex>(p,q)</tex>-граф Оставшуюся часть матрицы вычислим с вершинами, имеющими степени использованием цен редактирования расстояния Левенштейна и рекуррентного соотношения для <math>d_i</math>, то <tex>L(G)</tex> имеет <tex>q</tex> вершин и <math>q_L</math> ребер, где<math>q_L = -q + {\dfrac{1}{2}}\sum\limits_i{d_{i}^{2}}</math>|proof=По определению реберного графа граф <tex>L(G)</tex> имеет <tex>q</tex> вершин. Каждые <math>d_i</math> ребер, инцидентных вершине <math>v_i</math>, дают вклад <math>\begin{pmatrix} d_i \\ 2 \end{pmatrixj}</math> в число ребер графа <tex>L(G)</tex>, так что<math>q_L = \sum\limits_i{\begin{pmatrix} d_i \\ 2 \end{pmatrix}} = \dfrac{1}{2}\sum\limits_i{d_i(d_i-1)} = \dfrac{1}{2}\sum\limits_i{d_i^2}-\dfrac{1}{2}\sum\limits_i{d_i} = \dfrac{1}{2}\sum\limits_i{d_i^2-q}</math>}}:

==Построение=={| cellpadding="0"| [[Файл:line_graph_build_1.png|200px]] || [[Файл:line_graph_build_2.png|200px]] || [[Файл:line_graph_build_3.png|200px]] || [[Файл:line_graph_build_4.png|200px]]|-|Граф <tex>G</tex> || Новые вершины <tex>Lw(Ga,{\varepsilon})= 1</tex> || Добавлены рёбра в <tex>L(G)</tex> || Рёберный граф <tex>L(G)</tex>|}

<tex>w({\varepsilon}, b) = 1</tex> <tex>w(a, b) = \left\{\begin{array}{llcl}0&,\ a{\ne}b\\1&,\ a=b\\\end{array}\right.</tex> <tex>d_{i,j} = min(d_{i-1,j} + w(x_i,{\varepsilon}), d_{i,j-1} + w({\varepsilon}, y_j), d_{i-1,j-1} + w(x_i, y_i))</tex> Теперь каждое значение, не превосходящее <tex>k</tex>, в последней строке указывает позицию в тексте, в которой заканчивается строка, имеющая не больше <tex>k</tex> отличий от образца.===Пример===Источники информацииРассмотрим этот подход к решению задачи на примере: пусть <tex>X=ABCDE, Y=ACEABPCQDEABCR</tex>. Построим матрицу расстояний для этого случая:*[[wikipediaФайл:ru:Рёберный_граф Table_k_razlichiy.png]] Последняя строка матрицы показывает, что вхождения образца с точностью до <tex>2</tex> отличий, заканчиваются в позициях <tex>3</tex>, <tex>10</tex>, <tex>13</tex> и <tex>14</tex>. Соответствующими подстроками являются <tex>ACE</tex>, <tex>ABPCQDE</tex>, <tex>ABC</tex> и <tex>ABCR</tex>. ==Алгоритм== [[Алгоритм_Укконена| Wikipedia Алгоритм Укконена]] говорит, что при вычисления расстояний между строками, диагонали матрицы можно пронумеровать целыми числами <tex>p {\in} [-m, n]</tex>, таким образом, чтобы диагональ <tex>p</tex> состояла из элементов <tex>(i, j)</tex>, у которых <tex>j - i = p</tex>. Пусть <tex>r_{p,q}</tex> представляет наибольшую строку <tex>i</tex>, у которой <tex>d_{i,j} = q</tex> и <tex>(i, j)</tex> лежит на диагонали <tex>p</tex>. Таким образом, <tex>q</tex> – это минимальное число различий между <tex>x(1, r_{p,q})</tex> и любой подстрокой текста, заканчивающейся <tex>y_{r_{p,q}+p}</tex>. Значение <tex>m</tex> в строке <tex>r_{p,q}</tex>, для <tex>q < k</tex>, указывает, что в тексте имеется вхождение образца с точностью до <tex>k</tex> отличий, заканчивающееся в <tex>y_{m+p}</tex>. Таким образом, чтобы решить задачу <tex>k</tex> различий, достаточно вычислить значения <tex>r_{p,q}</tex> для <tex>q < k</tex>. Рассмотрим алгоритм вычисления <tex>r_{p,q}</tex>. '''for''' p = 0 '''to''' n r(p,-1) = -1 '''for''' p = -(k+1) '''to''' -1 r(p,|p|-1) = |p|-1 r(p,|p|-2) = |p|-2 '''for''' q = -1 '''to''' k r(n+1,q) = -1 '''for''' q = 0 '''to''' k '''for''' p = -q '''to''' n r = max(r(p,q-1) + 1, r(p-1,q-}} Реберные графы ]]1), r(p+1,q-1) + 1) r = min(r, m) '''while''' r < m '''and''' r + p < n '''and''' x(r+1) = y(r+1+p) r++ r(p,q) = r* Харари Фрэнк '''Теория графовif'''r(p,q) = m имеется вхождение с k отличиями, заканчивающееся в y(p+m)Алгоритм вычисляет значения <tex>r_{p,q}</tex> на <tex>n+k+1</tex> диагоналях. Для каждой диагонали переменной строки <tex>r</tex> можно присвоить не больше <tex>m</tex> различных значений, что приводит к времени вычислений <tex>O(mn)</tex>. Рассмотрим как можно ускорить решение этой задачи, используя другие методы.===Предварительные вычисления=== На этапе предварительной обработки, с помощью алгоритма Вейнера<ref>[http: Пер//europa. с англzbh.uni-hamburg.de/pubs/ Предислpdf/GieKur1997. Вpdf Giegerich R. П, Kurtz S. Козырева; Под ред{{---}} From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction]</ref> строится [[wikipedia:ru:Суффиксное_дерево|суффиксное дерево]] строки <tex>y{\#}x{\$}</tex>, где <tex>\#</tex> и <tex>\$</tex> – символы, не принадлежащие алфавиту, над которыми построены строки <tex>x</tex> и <tex>y</tex>. ГЭтот алгоритм требует линейных затрат памяти, и, для алфавита фиксированного размера, линейного времени.ПДля неограниченных алфавитов этот алфавит можно преобразовать так, что он будет выполняться за время <tex>O(n\log{\sigma})</tex>, где <tex>\sigma</tex> – число различающихся символов образца.ГавриловаСтадия предварительной обработки требует время <tex>O(n)</tex> и <tex>O(n\log{m})</tex> для постоянного и неограниченного алфавитов, соответственно. Изд===Модификация предыдущего алгоритма=== В приведенном выше алгоритме перед циклом <tex>while</tex> для диагонали <tex>p</tex>, переменной <tex>r</tex> было присвоено такое значение, что <tex>x(1, r)</tex> сопоставляется с точностью до <tex>k</tex> различий с некоторой подстрокой текста, заканчивающейся <tex>y_{r+p}</tex>. 4-еТогда функция цикла <tex>while</tex> находит максимальное значение для которого <tex>x(r+1, r+h) = y(r+p+1, r+p+h)</tex>. Обозначим это значение как <tex>h</tex>. — МЭто эквивалентно нахождению длины самого длинного общего префикса суффиксов <tex>x(r+1, m)\$</tex> и <tex>y(r+p+1,n){\#}x{\$}</tex> предварительно вычисленной конкатенированной строки.: Книжный дом "ЛИБРОКОМ"Символ <tex>\#</tex> используется для предотвращения ситуаций, в которых может ошибочно рассматриваться префикс, состоящий из символов как <tex>y</tex>, 2009так и <tex>x</tex>. — 296 Обозначим <tex>lca(r,p)</tex> как самый низкий общий предок в суффиксном дереве слистьями, определенными вышеуказанными суффиксами, тогда нужное значение <tex>h</tex> задается <tex>length(lca(r,p))</tex>.===Оценка времени работы=== Суффиксное дерево имеет <tex>O(n)</tex> узлов. Для поддержки определения самого низкого общего предка за линейное время, алгоритмам <tex>LCA</tex> требуется преобразование дерева, проводимое за линейное время. — ISBN 978-5-397-00622-4Значения <tex>r_{p,q}</tex> вычисляются на <tex>n+k+1</tex> диагоналях. Более того, для каждой диагонали надо вычислить <tex>k+1</tex> таких значений, что в общей сложности дает <tex>O(kn)</tex> запросов.Таким образом, общее время работы алгоритма k различий составляет <tex>O(kn)</tex> для алфавитов фиксированного размера, и <tex>O(Глава 8: Реберные графыn * \log{m} + kn)</tex> для неограниченных алфавитов.===Параллельная версия алгоритма=== В 1989 году Ландау и Вишкин разработали параллельную версию алгоритма. стрОна позволяет уменьшить время работы до <tex>O(\log{n}+k)</tex>, при использовании одновременно <tex>n</tex> процессоров. 91-104Для данной оценки необходимо, чтобы каждый из процессоров выполнял последовательный запрос <tex>LCA</tex> за <tex>O(1)</tex>.

[[Категория: Алгоритмы и структуры данных]]==Источники информации==* [[Категорияhttp: Основные определения теории графов]//algolist.manual.ru/search/fsearch/k_razl.php k-различий - алгоритм Ландау-Вишкина]