Содержание
- 2. Пример таких структур a и b. Нужно найти кратчайшее преобразование a в b указанными ниже операциями
- 3. Набор операций DCJ для Задачи преобразования: расклеить две вершины и склеить четыре образовавшиеся свободных (т.е. степени
- 4. 4 первых операции в задаче преобразования для DCJ : расклеить какую-либо вершину (Cut), склеить два свободных
- 5. Разрешены ещё две операции для DCJ : удалить (Rem) связный участок рёбер с именами из a,
- 6. до конца семестра будем изучать: Точный линейный по времени работы алгоритм кратчайшего преобразования одной структуры в
- 7. Случай паралогов рассматривается в другой нашей статье: Multiplicatively exact algorithms for transformation and reconstruction of directed
- 8. Компьютерная программы для этих алгоритмов и для алгоритма реконструкции очень востребованы! Попробуйте ваши силы. Для циклических
- 9. Ещё ссылки по этой задаче преобразования: Горбунов К.Ю., Любецкий В.А. Почти точный линейный алгоритм преобразования графов
- 10. Примеры этих операций над структурой a, которые последовательно преобразуют a в структуру b: 1) удалить связный
- 11. Каждой операции приписана цена – строго положительное рациональное число. В Лекции 9 алгоритм приведён для равных
- 12. Начало ребра с именем 5 помечаем 51 , а его конец помечаем 52. Важное определение! Общий
- 13. Для пары структур общим называется ребро, присутствующее в a и в b. Иначе ребро называется специальным.
- 14. граф G=a+b: В a и b специальные рёбра помечены цветом, в G=a+b их краям соответствуют жирные
- 15. Пример 2 : переход от G=a+b. G=a+b:
- 16. Как получить общий граф G=a+b по структурам a и b ? Т.е. приведём определение a+b :
- 17. Укажите структуры a и b, из которых получен следующий общ-ий граф G. (Например, 12b11 это цикл
- 18. Ответ: a+b . Что тут не восстановилось?
- 19. В a+b могут быть висячие рёбра, петли, изолированные вершины? Ответ: В примере 1, если ребра 1
- 20. Вершину внутри aa или bb, и помеченную вершину (цепь длины =0 или вершину петли) назовём сингулярной;
- 21. Итак, графы G состоят из циклов, цепей, изолирован-ных вершин, у которых каждому ребру приписано имя a
- 22. Отрезком в G назовём максимальный по включению связный участок из обычных рёбер. В зависимости от длины
- 23. Определение 1. Финальным графом (=графом финального вида) называется общий граф G, состоящий из обычных рёбер циклов
- 24. Операции над парами структур переносятся на a+b и наоборот по коммутативности: Эта диаграмма определяет связь операций
- 25. Лемма 0 (главная-1). Пусть цены DCJ-операций равны между собой, цены удаления сингулярных a- и b-вершин произволь-ные
- 26. Операция над G называется одноимённо с операцией над стру-ктурой: как DCJ-операции и удаление. Они примерно такие:
- 27. Примеры применения этих DCJ (= каждая из них называется переклейкой) и операции удаления к графу G
- 28. 2) DM-переклейка: удалить два ребра с одинаковой пометкой и образовавшиеся свободные края соединить рёбрами с той
- 29. Точное определение! Одинарная склейка (OM): добавление a-ребра между свободными вершинами: (1) обычными b-инцидентными вершинами; обычной b-инцидентной
- 30. Пусть цены всех операций равные. Приведение этого G: OM-замкнуть в цикл каждую из двух цепей, затем
- 31. Точное определение! Полуторная переклейка (SM): удалить ребро и добавить ребра с той же пометкой, соединяющего один
- 32. Во всех операциях, если образовались две смежные одноимённые сингулярные вершины, то соединяющее их ребро стягивается в
- 33. 3) SM для крестика 4-5) a-Rem и b-Rem Для того же G из примера 1 приведение
- 34. Точное определение! Двойная переклейка (DM): на слайде 26 общий случай – удаляются два одноименных ребра и
- 35. a a a a a a a a a a a a … … … …
- 36. Предполагается (только) равенство цен DCJ-операций. ТЕОРЕМЫ 1A. Построен линейный точный Алгоритм приведения любого графа G. Ниже
- 37. Автономным алгоритмом A (=автономным приведени-ем) назовём последовательность операций над графом G : ВЫРЕЗАТЬ все обычные рёбра;
- 38. Как ЗАМКНУТЬ цепь в цикл DCJ-операциями? Ответ: (типы цепи сверху вниз: 1b, 2b, 3b, 1a, 3,
- 39. При замыкании обычное ребро может появиться! Нап-р, при замыкании цепи aabbaa появляется обычное ребро b. Тогда
- 40. Как ИЗМЕЛЬЧИТЬ цикл ? (Затем удалить сингулярные вершины.) Цикл из сингулярных рёбер имеет чётное число В
- 41. Удаление сингулярной вершины: два идущих подряд ребра aa или bb заменить одним ребром с тем же
- 42. Если в G имеется какое-то обычное ребро Х, то его следует ВЫРЕЗАТЬ. Это ОЗНАЧАЕТ применить операции
- 43. На следующем слайде показаны все случаи ВЫРЕЗАНИЯ: соседи вырезаемого ребра есть сингулярное невисячее и обычное, сингулярное
- 44. здесь все ВЫРЕЗАНИЯ DM SM
- 45. Обычные рёбра внутри цепи удаляются DM справа налево: остаётся одно ребро (если отрезок нечётный) или два
- 46. Пример автономного приведения данного графа G: Определение 2а. Операция, которая уменьшает число сингулярных вершин в G,
- 47. Автономное приведение G, получим цепочку Е : особая a b неособая a неособая a a a
- 48. Определение 3. СИСТЕМОЙ УЧАСТКОВ в приводящей цепочке Е (от G ) назовём любое множество связных участков,
- 49. Определения 4. Приводящий алгоритм – это алг на графе G, который выдаёт приводящую цепочку для G
- 50. обозначим А() цепочку автономного приведения на данном аргуме-нте , т.е. от G до фг и от
- 51. Доказательство. E: G → … → R → … → S → … → фг A(G)
- 52. Смысл Леммы 2: чтобы T(Е) (где G=G(Е) фиксировано – закреплённый конец) было минимальным Р(E) должно быть
- 53. Определение 5. Пусть T любой приводящий алгоритм. Неравенство треугольника для T означает: для любой операции o
- 54. Док-во. Можно считать цены операций – натур. числа; все их суммы – натур. числа. Предположим неравенство
- 55. Лемма 1. Пусть wa и wb – цены удаления сингулярных a- и b-вершин, wa ≤ wb,
- 56. ещё характеристике графа G: D – число цепей, которые замыкаются в цикл неособой операцией (при автономном
- 57. Пример к лемме 1, автономное приведение графа G: Для циклической части, выполним 5 DM-переклеек, одно a-удаление
- 58. По леммам 1 и 2 получим!!: для любой приводящей цепочки Е с системой участков, начинающейся с
- 59. Для описания Алгоритма с произвольными ценами операций нужно важное Определение типа цепи, которое неявно встречалось выше
- 60. ( 0 – цепь без сингулярных вершин) ТИПЫ ЦЕПЕЙ: с сингулярными вершинами и ровно 1висячая, 2
- 61. Определение 5 типа цепи (если цепь не содержит обычных рёбер): 1a – нечётная цепь с одним
- 62. Определение 5 типа цепи (если без обычных рёбер): тип 3* – чётная цепь без висячих рёбер,
- 63. Операции SM на конкретных типах: 1а+1b=1b*, 3a+2b=1a* , 3a+2b' = 1a* , 3a'+2b= 1a*, 3a'+2b'= 1a',
- 64. 3a+3b=3* и 2a+2b=2+1'a Качество комбинации (=цепочки) операций o по определению равно P(o, {все типы в Ar})
- 65. Качества семи операции SM на конкретных типах указаны в квадратных скобках, проверьте! : 1a+1b=1*b [wa+wb], 3a+2b
- 66. В качестве примера вычислим качество SM-операции на 1a+1b=1*b : слева нечётные цепи, справа чётная. И s={o},
- 67. Взаимодействиями являются семь выше указанных SM-опе-раций на указанных политипах = множествах типов аргуме-нтов в одном из
- 68. И ещё 3-арные взаимодействия с политипами: 3*+(1a+2b)=1*b [wa+2wb–1], 3*+(1a+2b')=1*b [2wa+wb–1], 3*+(1b+2a)=1*b [wa+2wb–1], (3a+1b)+2=1*b [wa+2wb–1], (3a'+1b)+2=1*b [2wa+wb–1],
- 69. Обозначим множество цепей в G. Именно, над цепями выполняются: операции или их композиции!, т.е. такая композиция
- 70. Пусть f(x,y,z) взаимодействие на цепях с политипом {t1, t2, t3}. Аргументов может быть 2 цепи или
- 71. Максимальная область M – это область, на которой достигает максимума функция (от области X, «качество области
- 72. ИТАК, весь алгоритм определяется: (следующие шаги называются этапами): 0) по данным структурам a и b образовать
- 73. Для этого используем целочисленное линейное программирование (ЦЛП): каждому взаимодействию f сопоставим целочисленную 0 переменную
- 74. ЗАВЕРШЕНО описание алгоритма (для одного из соотношений цен) ! Лемма 4 (главная-2). Для нашего Алгоритма выполняется
- 75. Проблема 2. Найти другое пригодное в алгоритме семейство 1. Определение 7: b) Множество называется полным,
- 76. 2-ая задача = задача РЕКОНСТРУКЦИИ (без паралогов) была рассмотрена в начале этого семестра. Она состоит в
- 77. Следствие 1 к Лемме 1. Эти операции f и их качества P(f) поднимаются на фактор-множество по
- 78. Доказательство Следствий. 1) При замене цепи в том же типе тип значения не меняется. Перебором. 2)
- 79. Следствие 1 к Лемме 1. Эти операции f и их качества P(f) поднимаются на фактор-множество по
- 81. Скачать презентацию