Изменения

{{Теорема|statement===Алгоритм разделения АВЛ-дерева Задача о проверке на два, где в первом дереве все ключи меньше заданного x, а во втором пустоту пересечения двух КС- больше==грамматик неразрешима.|proof=Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_A = \{1(G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex> и . Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>T_\overline{2A}</tex> такие, таким образом показав, что <tex>T_{1} \leqslant x</tex> дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и <tex>x < T_{2}</tex>алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.

ПредположимДля любого экземпляра ПСП <tex>(x_1, x_2, что корень нашего дерева ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n)</tex> над алфавитом <tex>\Sigma</tex> можно подобрать символ <tex>\# \notin \Sigma</tex>. Для каждого экземпляра построим грамматики:* <tex>G_1 : S \rightarrow aSa \mid a\#a</tex> для всех <tex>a \in \Sigma</tex>. Тогда <tex>L(G_1) = \{ w\#w^R \leqslant xmid w \in \Sigma^* \}</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево где обозначение <tex>T_w^R</tex> {1{---}}разворот <tex>w</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи * <tex>G_2 : S \leqslant xrightarrow x_iSy^R_i \mid x_i\#y^R_i</tex>). Если же корень оказался для всех <tex>i = 1, 2, \dots n</tex> x. Тогда </tex>L(G_2) = \{ x_{i_1} x_{i_2} \dots x_{i_m} \# (y_{i_1} y_{i_2} \dots y_{i_m})^R \mid i_1, то мы спускаемся той же рекурсиейi_2, но только в левое поддерево и ищем там\dots i_m \in \{ 1, 2, \dots n \}, m \geqslant 1 \}</tex>.

Пусть мы пришли в поддерево Если данный экземпляр ПСП имеет решение, то <tex>SL(G_2)</tex>, корень которого содержит хотя бы одну строку вида <tex>w\leqslant x#w^R</tex>. В таком случае этот корень со своим левым поддеревом должен отойти в дерево , поэтому <tex>T_{1}</tex>. Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево <tex>S</tex>, удаляем корень, запоминая его значение L(не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL'амиG_1). Таким образом, мы отделяем сбалансированное АВЛ-дерево \cap L(бывшее левое поддерево <tex>S</tex>G_2). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины <tex>S\ne \varnothing</tex> , и запускаем балансировку. Обозначим полученное дерево за <tex>T'</tex>. Теперь нам нужно объединить его с уже построенным ранее <tex>T_{1}</tex> (оно может быть пустымнаоборот, если мы первый раз нашли такое дерево он не имеет решения, то <tex>S</tex>L(G_2). Для этого мы ищем в дереве <tex>T_{1}</tex> самое правое поддерево <tex>P</tex> высотыне содержит строк такого вида, равной высоте соответственно <tex>T'</tex> L(спускаясь от корня всегда в правые поддеревьяG_1). Делаем новое дерево <tex>K</tex>, сливая <tex>P</tex> и <tex>T'</tex> \cap L(очевидно, все ключи в <tex>T_{1}</tex> меньше ключей в <tex>T'</tex>, поэтому мы можем это сделатьG_2). Теперь в дереве <tex>T_{1}= \varnothing</tex> у отца вершины, в которой мы остановились при поиске дерева <tex>P</tex>, правым поддеревом делаем дерево <tex>K</tex> и запускаем балансировку. После нужно спуститься в правое поддерево бывшего дерева <tex>S</tex> (по ссылке, которую мы ранее запомнили) и обработать его.

Если Таким образом мы пришли в поддерево <tex>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_{2}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>. Рассмотри пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево <tex>T_{1}</tex>. <tex>x = 76</tex>. {| cellpadding="2"| || [[Файл:AVL.jpg|thumb|left|525px|Рис. 1. Разделение АВЛ-дерева на два.]]|} Корень дерева <tex>\leqslant x</tex>, поэтому он со всем выделенным поддеревом должен отойти в дерево <tex>T_{1}</tex>. По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево <tex>T'</tex> (рис. 2). Так как это первая ситуация, в которой корень рассматриваемого поддерева был <tex>\leqslant x</tex>, <tex>T'</tex> становится <tex>T_{1}</tex>. Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень <tex>> x</tex>. Следовательно, строим из него и его правого поддерева <tex>T_{2}</tex> и спускаемся в левое поддерево. Снова корень <tex>\leqslant x</tex>. Строим новое <tex>T'</tex> и объединяем его с уже существующим <tex>T_{1}</tex> (рис. 3). {| cellpadding="2"| || [[Файл:АВВЛ2.jpg|thumb|left|525px|Рис. 2. Создание T'.]]|}{| cellpadding="2"| || [[Файл:AVL3.jpg|thumb|left|1250px|Рис. 3. Объединение T' и T1.]]|} Далее действуем по алгоритму и в итоге получаем (рис. 4): {| cellpadding="2"| || [[Файл:End.jpg|thumb|left|525px|Рис. 4. АВЛ-деревья после разделения.]]|} Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>. Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>. Вернемся свели проблему соответствий Поста к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины. Пусть мы пришли в поддерево <tex>S</tex> с корнем <tex>\leqslant x</tex>. Тогда сольем его с уже построенным на тот момент <tex>T_overline{1A}</tex> (<tex>T_{1}</tex> пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, <tex>S \leqslant T_{1}</tex> и <tex>h(T_{1}) \leqslant h(S)</tex>). Но так как обычная процедура слияния сливает два АВЛ-дерева, а <tex>S</tex> не является корректным АВЛ-деревом, мы немного ее изменим. Пусть мы в дереве <tex>S</tex> нашли самое правое поддерево <tex>K</tex>, высота которого равна высоте <tex>T_{1}</tex>. Тогда сделаем новое дерево <tex>T'</tex>, корнем которого будет вершина <tex>S</tex> (без нее это дерево является сбалансированным)следовательно, правым поддеревом {{---}} <tex>T_{1}</tex>, левым {{---}} <tex>K</tex>. И подвесим <tex>T'</tex> задача о проверке на то место, где мы остановились при поиске <tex>K</tex>. Запустим балансировку. В случае, когда корень поддерева, в которое мы пришли, <tex>> x</tex>, все аналогично. Разберем пример на рис. 1. Пусть мы рекурсивно спустились до узла <tex>77</tex>. Ключ больше <tex>x</tex>, поэтому эта вершина станет деревом <tex>T_{2}</tex> и передастся наверх. Теперь мы поднялись в узел <tex>75</tex>. Он со своим левым поддеревом станет деревом <tex>T_{1}</tex> и мы снова поднимемся наверх в узел <tex>70</tex>. Он со своим левым поддеревом снова должен отойти в дерево <tex>T_{1}</tex>, и так как теперь дерево <tex>T_{1}</tex> уже не пустое, то их надо слить. После слияния по описанному выше алгоритму получим (рис. 5) {| cellpadding="2"| || [[Файл:Ex.jpg|thumb|left|525px|Рис. 5.]]|} После мы поднимемся в вершину с ключом <tex>80</tex>. Она с правым поддеревом отойдет в дерево <tex>T_{2}</tex> (рис. 6).  {| cellpadding="2"| || [[Файл:Ex2am.jpg|thumb|left|525px|Рис. 6.]]|} И на последней итерации мы поднимемся в корень дерева с ключом <tex>50</tex>, он с левым поддеревом отойдет в дерево <tex>T_{1}</tex>, после чего алгоритм завершится. Пусть поддеревьев с ключами <tex>\leqslant x</tex> оказалось больше, чем поддеревьев с ключами <tex>> x</tex>. Докажем для них логарифмическую асимптотику. Дерево на последнем уровне имеет высоту <tex>H_{k}</tex> (она может быть не равна <tex>1</tex>, если мы придём в <tex>x</tex>). Его мы передаем наверх и вставляем в поддерево высотой <tex>H_{k-1}</tex>. <tex>H_{k} \leqslant H_{k-1}</tex>, так как разница высот поддеревьев у любой вершины не больше <tex>1</tex>, и мы при переходе от <tex>H_{k}</tex> к <tex>H_{k-1}</tex> поднимаемся как минимум на одну вершину вверх. Слияние этих поддеревьев мы выполним за <tex>H_{k-1} - H_{k}</tex>, получим в итоге дерево высоты не большей, чем <tex>H_{k-1}</tex>. Его мы передадим наверх, поэтому в следующий раз слияние будет выполнено за <tex>H_{k-2} - H_{k - 1}</tex> и так далее. Таким образом мы получим <tex>(H - H_{1}) + (H_{1} - H_{2}) + (H_{2} - H_{3}) + \cdots + (H_{k - 1} пустоту пересечения двух КС- H_{k}) = H - H_{k} = O(\log{n})</tex>. Итоговая асимптотика алгоритма {{---}} <tex>O(\log{n})</tex>. = Гамма-алгоритм ={{Задача|definition=Определить, является ли граф планарным, и, если да, произвести его плоскую укладкуграмматик неразрешима.

Существует [[Теорема Понтрягина-Куратовского|теорема Понтрягина-Куратовского]], которая говорит, что граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Но этот критерий очень трудно проверить на практике, поэтому данная теорема представляет лишь теоретический интерес. Чтобы проверить планарность графа и произвести его плоскую укладку, удобно пользоваться гамма-алгоритмом. == Входные данные == На вход алгоритму подаются графы со следующими свойствами:# Граф связный,# Граф содержит хотя бы один цикл,# Граф не имеет [[Мост, эквивалентные определения|мостов]]. Если нарушено свойство <tex>1</tex>, то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство <tex>2</tex>, то граф {{---}} дерево и нарисовать его плоскую укладку тривиально.  Более подробно рассмотрим случай, когда в графе <tex>G</tex> нарушено свойство <tex>3</tex>. Сначала все мосты нужно убрать, далее произвести отдельную укладку всех компонент следующим образом: уложим одну компоненту связности, а следующую компоненту, связанную с первой в графе <tex>G</tex> мостом, будем рисовать в той грани, в которой лежит вершина, принадлежащая мосту. Иначе может сложиться ситуация, когда концевая вершина моста будет находиться внутри плоского графа, а следующая компонента - снаружи. Таким образом мы сможем соединить мостом нужные вершины. Далее будем так поступать с каждой новой компонентой. == Описание алгоритма == Рассмотрим работу алгоритма, параллельно разбирая на примере каждый шаг.Пусть дан граф <tex>G</tex> (рис. 1). {| cellpadding="2"| || [[Файл:Гамма-алгоритм1.jpg|thumb|left|370px|Рис. 1. Исходный граф.]]|} <tex>1.</tex> Первый этап - '''инициализация''' алгоритма.  В графе <tex>G</tex> выбирается любой простой цикл и производится его укладка на плоскость. Пусть в примере это будет цикл <tex>\{1, 2, 3, 4, 5, 6\}</tex>. После его укладки получаем две грани: <tex>\Gamma_{1}</tex> и <tex>\Gamma_{2}</tex> (рис. 2). {| cellpadding="2"| || [[Файл:Гамма-алгоритм2.jpg|thumb|left|370px|Рис. 2. Укладка цикла на плоскость.]]|} Уже уложенную во время работы алгоритма часть будем обозначать <tex>G_{plane}</tex>. В примере сейчас <tex>G_{plane}</tex> {{---}} выбранный цикл <tex>\{1, 2, 3, 4, 5, 6\}</tex>. <tex>2.</tex> Второй этап - общий шаг. Построим множество '''сегментов'''. Каждый сегмент <tex>S</tex> относительно уже построенного <tex>G_{plane}</tex> представляет собой одно из двух:# ребро, оба конца которого принадлежат <tex>G_{plane}</tex>, но само оно не принадлежит <tex>G_{plane}</tex>,# связную компоненту графа <tex>G \backslash G_{plane}</tex>, дополненную всеми ребрами графа <tex>G</tex> такими, у которых один из концов принадлежит связной компоненте, а второй принадлежит графу <tex>G_{plane}</tex>. Вершины, одновременно принадлежащие <tex>G_{plane}</tex> и какому-либо сегменту, назовем '''контактными'''. На рис. 3 изображены сегменты для нашего примера. Контактные вершины обведены в квадрат. {| cellpadding="2"| || [[Файл:Гамма-алгоритм3.jpg|thumb|left|370px|Рис. 3. Выделение сегментов.]]|} Пусть в каком-то сегменте нет ни одной контактной вершины. В таком случае граф до выделения <tex>G_{plane}</tex> был несвязным, что противоречит условию. Пусть контактная вершина в сегменте только одна. Это значит, что в графе был мост, чего быть не может так же по условию. Таким образом, в каждом сегменте имеется не менее двух контактных вершин. Соответственно, в каждом сегменте есть цепь между любой парой контактных вершин. Пусть грань <tex>\Gamma</tex> '''вмещает''' сегмент <tex>S</tex>, если номера всех контактных вершин <tex>S</tex> принадлежат этой грани, <tex>S \subset \Gamma</tex>. Очевидно, таких граней может быть несколькопримеров. Множество таких граней обозначим <tex>\Gamma(S)</tex>, а их число {{---}} <tex>|\Gamma(S)|</tex>. Итак, рассмотрим все сегменты <tex>S_{i}</tex> и для каждого определим число <tex>|\Gamma(S_{i})|</tex>. Если найдется такой номер <tex>i</tex>, что <tex>|\Gamma(S_{i})| = 0</tex>, то граф не планарен, алгоритм завершает работу. Иначе выбираем такой сегмент <tex>S_{i}</tex>, для которого число <tex>|\Gamma(S_{i})|</tex> минимально. Если таких сегментов несколько, можно выбрать любой из них. Найдем в этом сегменте цепь между двумя контактными вершинами и уложим ее в любую грань из множества <tex>|\Gamma(S_{i})|</tex>, совместив контактные вершины сегмента с соответствующими вершинами грани. Выбранная грань разобьется на две. Выбранный сегмент после того, как из него взяли цепь, либо исчезнет, либо распадется на меньшие части, в которых будут новые контактные вершины, ведущие к вершинам обновленного <tex>G_{plane}</tex>. В примере для любого <tex>i</tex>: <tex>S_{i} \subset \{\Gamma_{1}, \Gamma_{2}\}</tex>, то есть <tex>|\Gamma(S_{i})| = 2</tex>. Следовательно, можем выбрать любой <tex>S_{i}</tex>. Пусть это будет сегмент <tex>S_{1}</tex>. В нем есть цепь <tex>\{1, 4\}</tex>. Вставим эту цепь в грань <tex>\Gamma_{1}</tex>, например, и этот сегмент исчезнет. После укладки цепи граф <tex>G</tex> и сегменты будут выглядеть так (рис. 4):

{| cellpadding="2"| || По двум КС-грамматикам <tex>G_1</tex> и <tex>G_2</tex> можно построить КС-грамматику для [[Файл:ГаммаЗамкнутость КС-алгоритм4языков относительно различных операций#.D0.9A.D0.BE.D0.BD.D0.BA.D0.B0.D1.82.D0.B5.D0.BD.D0.B0.D1.86.jpgD0.B8.D1.8F|thumb|left|500px|Рисконкатенации]] задаваемых ими языков <tex>L(G_1)L(G_2)</tex>. 4По аналогии с этим мы можем рассматривать язык <tex>L(G_1)\#L(G_2)\#</tex>, где <tex>\#</tex> {{---}} новый символ, не встречающийся в алфавите. Граф Заметим, что пересечение языков непусто, то есть <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex>, тогда и сегменты после второго этапатолько тогда, когда <tex>L(G_1)\#L(G_2)\#</tex> содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]]|}.

<tex>3.</tex> Третий и последующие этапы аналогичны второму. Повторять вышеуказанные действия нужно либо до тех пор, пока не будет получена плоская укладка, то есть множество сегментов не останется пустым, либо пока не будет получено, что граф не планарен.  Разберем пример до конца. Повторим снова общий шаг. Теперь <tex>|\Gamma(S_{1})| = |\Gamma(S_{3})| = 1</tex>, <tex>|\Gamma(S_{2})| = |\Gamma(S_{4})| = 2</tex>. Возьмем <tex>S_{1}</tex>. В ней цепь <tex>\{2, 5\}</tex>Таким образом, которую мы уложим в грань <tex>\Gamma_{2}</tex>, после чего этот сегмент исчезнет. Теперь картина будет следующая (рис. 5): {| cellpadding="2"| || [[Файлимеем:Гамма-алгоритм5.jpg|thumb|left|500px|Рис. 5. Граф и сегменты после третьего этапа.]]|} На следующем шаге <tex>|\Gamma(S_{1})| = |\Gamma(S_{3})| = 2</tex>, <tex>|\Gamma(S_{2})| = 1</tex>. Выбираем сегмент <tex>S_{2}</tex>, содержащий цепь <tex>\{3, 5\}</tex>. Уложим ее в грань <tex>\Gamma_{2}</tex>, после чего этот сегмент снова исчезнет (рис. 6). Утверждение {| cellpaddingstatement="2"| || [[Файл:Гамма-алгоритм6.jpg|thumb|left|500px|Рис. 6. Граф и сегменты после четвертого этапа.]]|} Теперь Пусть дана грамматика <tex>|\Gamma(S_{1})| = 1G</tex>, а <tex>|\GammaL(S_{3}G)| = 2L</tex>. Уложим сначала цепь <tex>\{2, 4\}</tex> из первого сегмента, он пропадет, потом уложим цепь <tex>\{6, 7, 5\}</tex> из третьего. В результате граф будет полностью уложен на плоскость, множество сегментов останется пустым (рис. 7). {| cellpadding="2"| || [[ФайлТогда следующие задачи неразрешимы:Гамма-алгоритм7.jpg|thumb|left|300px|Рис. 7. Плоская укладка графа.]]|} Таким образом, мы получили плоскую укладку исходного графа <tex>G</tex>. Опишем алгоритм коротко и формально:# Инициализация. Выбирается простой цикл в исходном графе и изображается на плоскости. # Общий шаг. Этот шаг повторяется до тех пор, пока граф не будет уложен или пока не будет получено, что граф не планарен. #* строится множество сегментов#* для каждого сегмента вычисляется величина Содержит ли <tex>|\Gamma(S)|L</tex>тандемный повтор. Если существует <tex>i</tex>: <tex>|\Gamma(S_{i})| = 0</tex>, то граф не планарен, алгоритм завершает работу#* выбирается сегмент с минимальным числом Содержит ли <tex>|\Gamma(S_{i})|L</tex>#* в этом сегменте выбирается цепь между двумя контактными вершинами #* эта цепь укладывается в любую грань, вмещающую данный сегмент# Либо получена плоская укладка графа, либо граф оказался не планарен. == Доказательство корректности гамма-алгоритма == Перед доказательством корректности приведем ряд важных вспомогательных лемм и теорем.  Пусть два сегмента <tex>S_{1}</tex> и <tex>S_{2}</tex> называются '''конфликтующими''' относительно уже уложенной части, если:# грань вмещает каждый из сегментов <tex>S_{1}</tex> и <tex>S_{2}</tex># в этих сегментах есть две цепи между контактными вершинами <tex>L_{1}</tex> и <tex>L_{2}</tex> соответственно такие, что их невозможно уложить в одну грань без пересечения Например, на рис. 1 конфликтующими являются сегменты <tex>S_{1}</tex> и <tex>S_{2}</tex>.  {| cellpadding="2"| || [[Файл:Гамма-алгоритм8.jpg|thumb|left|520px|Рис. 1. Конфликтующие сегменты.]]|} {{Лемма|id=lemma1|about=1|statement=Конфликтующие сегменты <tex>S_{1}</tex> и <tex>S_{2}</tex> обладают следующим свойством: если <tex>|\Gamma(S_{1})| \geq 2</tex> и <tex>|\Gamma(S_{2})| \geq 2</tex>, то <tex>\Gamma(S_{1}) = \Gamma(S_{2}) = 2</tex>. |proof=Сначала докажем, что <tex>\Gamma(S_{1}) = \Gamma(S_{2})</tex>. Предположим противное. Тогда по условию леммы найдутся три различные грани <tex>\Gamma_{1}, \Gamma_{2}</tex> и <tex>\Gamma_{3}</tex> такие, что <tex>\Gamma_{1} \in \Gamma(S_{1}), \Gamma_{2} \in \Gamma(S_{2}), \Gamma_{3} \in Q = \Gamma(S_{1}) \cap \Gamma(S_{2}) \neq \emptyset</tex>. Тогда любые цепи <tex>L_{1} \subset S_{1}</tex> и <tex>L_{2} \subset S_{2}</tex> укладываются в <tex>\Gamma_{1}</tex> и <tex>\Gamma_{2}</tex> соответственно. Но это значит, что любая пара цепей <tex>L_{1}</tex> и <tex>L_{2}</tex> одновременно укладывается вне грани <tex>\Gamma_{3}</tex>. Следовательно, они одновременно укладываются и внутри грани <tex>\Gamma_{3}</tex>, причем без пересечений. Но это противоречит тому, что <tex>S_{1}</tex> и <tex>S_{2}</tex> {{---}} конфликтующие сегменты. Таким образом, <tex>\Gamma(S_{1}) = \Gamma(S_{2})</tex>. Теперь покажем, что <tex>|Q| = 2</tex>. Доказательство снова поведем методом от противного. Пусть <tex>|Q| \geq 3</tex>. Тогда снова существует три различные грани <tex>\Gamma_{1}, \Gamma_{2}</tex> и <tex>\Gamma_{3} \in Q</tex>. Аналогичными рассуждениями снова приходим к противоречию с тем, что <tex>S_{1}</tex> и <tex>S_{2}</tex> {{---}} конфликтующие сегментыпалиндром.