Русская Википедия:Книжное вложение
Книжное вложение в теории графов — обобщение планарного вложения графа до вложения в книгу — набор полуплоскостей, имеющих одну и ту же прямую в качестве границы. Обычно требуется, чтобы вершины графа лежали на этой границе, а рёбра должны находиться внутри одной страницы. Книжная толщина (или число страниц) графа — наименьшее число полуплоскостей для всех книжных вложений графа.Шаблон:Sfn Книжное вложение используется для некоторых других инвариантов графа, включая ширину страницыШаблон:Sfn и книжное число скрещиванийШаблон:Sfn.
Любой граф с n вершинами имеет книжную толщину максимум <math>\lceil n/2\rceil</math>. Эта граница близка для полных графовШаблон:Sfn. Однако подразделение каждого ребра может сократить книжную толщину к величине, пропорциональной корню квадратному из n.Шаблон:Sfn Графы с книжной толщиной один являются внешнепланарными графами,Шаблон:Sfn а графы с книжной толщиной не более двух являются подгамильтоновыми, которые всегда планарныШаблон:Sfn. Любой планарный граф имеет книжную толщину, не превышающую четырёхШаблон:Sfn. Все минорно замкнутые семейства графов, и, в частности, графы с ограниченной древесной шириной или ограниченным родом, также имеют ограниченную книжную толщинуШаблон:Sfn. Определение точной книжной толщины заданного графа является NP-трудной задачи, независимо от того, известен или нет порядок вершин на корешкеШаблон:SfnШаблон:Sfn.
Одной из начальных поводов для изучения книжного вложения было применение его в разработке СБИС, где вершины книжного вложения представляют компоненты, а рёбра представляют соединения между компонентамиШаблон:Sfn[1]. При визуализации графов два стандартных стиля представления графов, дуговые диаграммыШаблон:Sfn и круговые расположенияШаблон:Sfn, можно построить с помощью книжного вложения. Различные начальные и конечные точки движения пешеходов и машин, которые регулируются светофором, могут быть смоделированы математически как вершины графа, а рёбра будут представлять пары начало-конец, книжное же вложение этого графа можно использовать для создания режима работы светофора, чтобы обеспечить регулировку движения с минимальным числом состояний светофораШаблон:Sfn. В задачах биоинформатики, работающих со структурами РНК, одностраничное книжное вложение представляет классическую форму Шаблон:Не переведено 5, а двухстраничное вложение представляет псевдоузлыШаблон:Sfn. Книжное вложение используется также в общей алгебреШаблон:Sfn и теории узловШаблон:SfnШаблон:Sfn.
Открытыми проблемами, касающимися книжного вложения, являются
- Ограничена ли книжная толщина произвольного графа функцией его подразбиенийШаблон:Sfn
- Достаточно ли знать порядок вершин на корешке, чтобы проверить, что граф имеет трёхстраничное вложение[2]
- Существует ли планарный граф, книжная толщина которого равна четырёмШаблон:Sfn
- Сколько пересечений на корешке необходимо для трёхстраничного топологического вложения (в этом случае рёбра могут переходить со страницы на страницу через корешок) произвольного графаШаблон:Sfn.
История
Название «книга» было введено Персингером и Атнеосеном (C. A. Persinger, Gail Atneosen) в 1960-е годыШаблон:SfnШаблон:Sfn[3]. Атнеосен уже использовал вложение графов в книги, но формальная концепция книжного вложения была сформулирована Кайненом и Оллманом (C. Kainen, L. Taylor Ollman) в начале 1970-х и были добавлены некоторые дополнительные ограничения на способ вложения — в их формулировке вершины графа должны лежать на корешке книги, каждое ребро должно лежать на одной странице (не пересекать корешок) и любые два ребра пересекаются только в общих конечных вершинах[4] [5].
Важными вехами в дальнейшем развитии книжного вложения является доказательство Михалисом Яннакакисом в конце 1980-х, что книжная толщина планарных графов не превосходит четырёхШаблон:SfnШаблон:Sfn, и открытие в конце 1990-х тесной связи между книжным вложением и биоинформатикой.Шаблон:Sfn
Определения
Книга является частным видом топологического пространства (называемого также Шаблон:Не переведено 5 полуплоскостей)Шаблон:Sfn[6]. Оно состоит из одной прямой ℓ, называемой корешком[7] книги, вместе с набором одной или более полуплоскостей, называемых страницами или листами книги. Каждая полуплоскость должна иметь одну и ту же прямую ℓ в качестве границы. Книги с конечным числом (k) страниц могут быть вложены в трёхмерное пространство, например, посредством выбора в качестве прямой ℓ оси z прямоугольной системы координат, а в качестве i-ой страницы (из k) можно взять множество точек p, таких что кратчайший отрезок, соединяющий p с осью z, имеет угол 2πi/k по отношению к плоскости xzШаблон:Sfn.
Визуализация книги конечного графа G в книгу B есть рисунок графа G в B, так что любая вершина графа G рисуется на корешке B, а любое ребро G рисуется в виде кривой, лежащей внутри одной страницы B. k-страничное книжное число пересечений графа G — это минимальное число пересечений в рисунке на k-страничной книгеШаблон:Sfn.
Книжное вложение графа G в B — это вложение графа G в пространство B. То есть это рисунок графа G в B, при котором рёбра не пересекаются. Любой конечный граф имеет книжное вложение в книгу с достаточно большим числом страниц. Например, всегда есть возможность вложить каждое ребро на свою собственную страницу. Толщина книги, число страниц, или стэковое число графа G — это минимальное число страниц, которое требуется для книжного вложения графа G. Другой параметр, измеряющий качество книжного вложения, кроме числа страниц, — это ширина страницы. Это максимальное число рёбер, которое пересекает луч, перпендикулярный корешку внутри отдельной страницы. Эквивалентно (для книжных вложений, в которых каждое ребро нарисовано как монотонная кривая), это максимальный размер подмножества рёбер, таких что интервалы, определённые на корешке конечными точками рёбер, все пересекаютсяШаблон:Sfn[8][9].
Существенно для этих определений, что рёбра могут лежать только на одной странице. Как заметил уже Амеозен, если рёбра могут переходить со страницы на страницу (через корешок), то любой граф можно вложить в трёхстраничную книгуШаблон:SfnШаблон:SfnШаблон:Sfn. Однако для трёхстраничного топологического книжного вложения, в котором пересечение корешка разрешено, остаётся интересной задача определения наименьшего числа пресечения корешка, позволяющего вложить граф в книгуШаблон:Sfn[10].
Конкретные графы
Как показано на первом рисунке, книжная толщина полного графа <math>K_5</math> равна трём. Поскольку он непланарен, его книжная толщина больше двух, но существует книжное вложение с тремя страницами. Книжная толщина любого полного графа с <math>n\ge 4</math> вершинами равна в точности <math>\lceil n/2\rceil</math>. Этот результат даёт Шаблон:Не переведено 5 максимальной книжной толщины любых графов с <math>n</math> вершинамиШаблон:Sfn. Двухстраничное число пересечений полного графа <math>K_n</math> равно
- <math>(1/4) \left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor\left\lfloor\frac{n-2}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor,</math>
что соответствует недоказанной гипотезе Энтони Хилла. То есть, если гипотеза Хилла верна, то рисунком этого графа, минимизирующего число пересечений, является двухстраничный рисунок[11].
Толщина книги полного двудольного графа <math>K_{a,b}</math> почти равна <math>\min\{a,b\}</math> — для каждой вершины меньшей доли можно расположить рёбра, инцидентные этим вершинам, на собственной странице. Эта граница не всегда строгая. Например, <math>K_{4,4}</math> имеет толщину книги три, а не четыре. Однако, когда две стороны графа сильно разбалансированы, с <math>b>a(a-1)</math>, толщина книги <math>K_{a,b}</math> равна в точности <math>a</math>.Шаблон:Sfn[12] Толщина книг двоичных графов де Брёйна, графов тасованного обмена, и Шаблон:Не переведено 5 (когда эти графы достаточно велики, чтобы не быть планарными) равна в точности трём.[13]
Свойства
Поведение при подразбиениях
Шаблон:Unsolved Разбиение каждого ребра графа на двухрёберные пути путём добавления новых вершин для каждого ребра может иногда увеличить толщину книги (например, алмаз имеет книжную толщину один, но его подразбиение имеет книжную толщину два). Однако такое подразбиение может также существенно уменьшить книжную толщину графа после разбиения. Например, книжная толщина полного графа Kn is Θ(n) пропорциональна числу его вершин, но разбиение каждого ребра на два даёт подразбиение с много меньшей книжной толщиной, лишь O(√n).Шаблон:Sfn. Несмотря на существование примеров, подобных вышеприведённому, Бланкеншип и ОпоровскиШаблон:Sfn высказали гипотезу, что книжная толщина подразбиений не может быть существенно меньше, чем у исходного графа. В частности, они предположили, что существует некая функция f, что для любого графа G и графа H, полученного заменой каждого ребра G путём из двух рёбер, если книжная толщина графа H равна t, то книжная толщина графа G не превышает f(t).Шаблон:Sfn К 2013 гипотеза Бланкеншипа-Опоровски оставалась недоказанной.Шаблон:Sfn
Планарность и внешняя планарность
Книжная толщина данного графа G не превышает 1 тогда и только тогда, когда G внешнепланарен. Внешнепланарный граф — это граф, имеющий планарное вложение, в котором все вершины принадлежат внешней грани вложения. Для таких графов расположение вершин в том же порядке вдоль корешка, в котором они появляются на внешней грани (при повторном появлении вершины на внешней грани берётся только одна копия вершины) даёт одностраничное вложение графа. И наоборот, одностраничное книжное вложение является автоматически внешенпланарным — если граф вложен в одну страницу, присоединение второй полуплоскости даёт полную плоскость, а внешняя грань будет содержать всю добавленную полуплоскость, при этом все вершины будут лежать на этой внешней граниШаблон:SfnШаблон:Sfn.
Любое книжное вложение с двумя страницами является специальным случаем планарного вложения, поскольку объединение двух страниц книги является пространством, топологически эквивалентным плоскости. Таким образом, любой граф с книжной толщиной два автоматически является планарным. Точнее, книжная толщина графа G не больше двух тогда и только тогда, когда G является подграфом планарного графа, который имеет гамильтонов циклШаблон:Sfn. Если дан граф с книжным вложением в две страницы, граф может быть расширен до планарного гамильтонова графа путём добавления (на любой странице) дополнительных рёбер между любыми двумя последовательными вершинами вдоль корешка, если они ещё не соединены ребром, а также между первой и последней вершиной корешка. Граф Голднера–Харари даёт пример планарного графа, не имеющего книжной толщины два — это Шаблон:Не переведено 5, так что невозможно добавить никакое ребро, сохраняя планарность, и граф не имеет гамильтонова циклаШаблон:Sfn. Ввиду требования наличия гамильтоновых циклов графы, позволяющие двухстраничное вложение, известны как подгамильтоновы графыШаблон:Sfn.
Все планарные графы с максимальной степенью, не превышающей четырёх, имеют толщину книжного вложения, не превышающую двух.Шаблон:Sfn. Шаблон:Не переведено 5 имеют максимальную толщину книги, равную трём[14]. Все планарные графы имеют книжную толщину, не превышающую четырёхШаблон:SfnШаблон:Sfn. Как утверждал Михалис Яннакакис в 1986Шаблон:Sfn, существуют планарные графы с толщиной книжного вложения, в точности равной четырём, однако детальное доказательство этого утверждения, анонсированного в статьеШаблон:Sfn, так и не было опубликовано. По этой причине ДуймовичШаблон:Sfn обозначил задачу определения максимальной толщины книжного вложения планарных графов как нерешённуюШаблон:Sfn.
Связь с другими инвариантами графов
Толщина книги связана с толщиной графа, числом планарных графов, которые необходимы для покрытия рёбер заданного графа. Граф G имеет толщину θ, если его можно вложить в плоскость, и при этом рёбра можно раскрасить в θ цветов таким образом, что рёбра одного цвета не пересекаются. Аналогично граф G имеет книжную толщину θ, если его можно нарисовать в полуплоскости с вершинами на границе полуплоскости и раскрасить рёбра в θ цветов без пересечений рёбер одного цвета. При такой формулировке рёбра одного цвета соответствуют страницам книжного вложения. Однако толщина графа и толщина книги могут существенно различаться — существуют подразделения полных графов, имеющие неограниченную книжную толщинуШаблон:SfnШаблон:SfnШаблон:Sfn, несмотря на то, что толщина графа равна двумШаблон:Sfn.
Графы с древесной шириной k имеют книжную толщину, не превосходящую k + 1Шаблон:Sfn[15] и эта граница достигается для k > 2.Шаблон:Sfn. Графы с m рёбрами имеют книжную толщину O(√m)[16], а графы с родом g — книжную толщину O(√g)[17]. Более обще, любое Шаблон:Не переведено 5 имеет ограниченную книжную толщинуШаблон:Sfn[18].
Любой стягивающий минор графа ограниченной книжной толщины является разреженным графом, у которого отношение рёбер к вершинам ограничено константной, которая зависит только от глубины минора и книжной толщины. То есть, в терминологии НешетрилаШаблон:Sfn, графы с ограниченной книжной толщиной имеют ограниченный ростШаблон:Sfn. Однако даже графы с ограниченной степенью графа существенно более сильное требование ограничения роста, может иметь неограниченную книжную толщину[19].
Поскольку графы с книжной толщиной два являются планарными графами, они удовлетворяют теореме о планарном разбиении — они имеют сепараторы, подмножества вершин, удаление которых делит граф на части с максимум 2n/3 вершинами в каждой части, только с O(√n) вершинами в сепараторе. Здесь n означает число вершин графа. Однако существуют графы с книжной толщиной три, не имеющие сепараторы сублинейного размера[20].
Рёбра на одной странице книжного вложения ведут себя подобно стеку. Это можно формализовать, если рассмотреть произвольную последовательность операций push и pop (засылка и извлечение) на стеке и сформировать граф, в котором стековые операции соответствуют вершинам графа, расположенным на корешке книжного вложения в порядке выполнения операций. Если теперь нарисовать ребро от каждой операции pop, извлекающей объект x из стека к операции push, заславшей этот элемент в стек, полученный граф будет иметь автоматически одностраничное вложение. По этой причине число страниц графа называют также его стековым числом. По аналогии исследователи определяют очередное вложение графа как рисунок графа в книге, в котором любые два ребра на странице либо пересекаются, либо покрывают непересекающиеся интервалы на корешке. Такие вложения соответствуют некоторым образом очередям и минимальное число страниц, необходимых для очередного вложения графа, называется его числом очередейШаблон:Sfn[21][22].
Вычислительная сложность
Определение толщины книжного вложения является NP-трудной задачей. Это следует из факта, что нахождение гамильтонова цикла в максимальных планарных графах является NP-полной задачей. Толщина книжного вложения максимального планарного графа равна двум тогда и только тогда, когда гамильтонов путь существует. Поэтому определение, что толщина книжного вложения заданного максимального планарного графа равна двум, также является NP-полной задачей.Шаблон:Sfn
Если порядок расположения вершин вдоль корешка при книжном вложении предопределён, двухстраничное вложение (если такое существует) может быть найдено за линейное время как вариант проверки планарности для графа, полученного расширением заданного графа путём создания цикла, соединяющего вершины вдоль корешкаШаблон:Sfn. Унгер утверждал, что нахождение трёхстраничного вложения с предопределённым порядком вершин может быть осуществлено за полиномиальное время, хотя в его описании этого результата отсутствует ряд существенных деталей[2]. Однако для графов, которые требуют четыре и более страниц, задача нахождения вложения с минимально возможным числом страниц остаётся NP-трудной ввиду эквивалентности NP-трудной задаче раскраски круговых графов, графов пересечений хорд окружности. Если задан граф G с фиксированным порядком вершин на корешке, расположение этих вершин в том же порядке на окружности и представление рёбер графа G в виде отрезков даёт набор хорд, представляющих граф G. Можно теперь образовать круговой граф, имеющий хорды этой диаграммы в качестве вершин, а пересекающиеся пары хорд в качестве рёбер. Раскраска кругового графа даёт разбиение рёбер графа G на подмножества, которые могут быть нарисованы без пересечений на одной странице. Таким образом, оптимальная раскраска эквивалентна оптимальному книжному вложению. Поскольку раскраска кругового графа в четыре и более цветов является NP-трудной задачей, и поскольку любой круговой граф может быть образован таким образом из некоторой задачи нахождения книжного вложения, нахождение оптимального книжного вложения является также NP-трудной задачейШаблон:SfnШаблон:Sfn[23]. Для фиксированного порядка вершин на корешке при двухстраничном вложении является NP-трудной задачей минимизация числа пересечений, если это число не равно нулюШаблон:Sfn.
Если порядок вершин на корешке неизвестен, но разбиение рёбер по страницам задано, возможно нахождение 2-страничного вложения (если такое существует) за линейное время путём применения алгоритма, основанного на SPQR-деревьяхШаблон:Sfn[24]. Однако нахождение 2-страничного вложения является NP-полной задачей, если ни порядок вершин на корешке, ни разбиение рёбер по страницам не известно. Нахождение книжного числа пересечений графа является также NP-трудной задачей ввиду NP-полноты задачи проверки, является ли двухстраничное книжное число пересечений нулём.
Задача Шаблон:Не переведено 5, заключающаяся в определении, находится ли ограниченный в размере граф некоторого вида в качестве подграфа большего графа, может быть решена за линейное время, если больший граф имеет ограниченную толщину книжного вложения. То же самое верно и для определения, является ли граф некоторого вида порождённым подграфом большего графа, или он имеет гомеоморфизм с большим графомШаблон:SfnШаблон:Sfn. По той же причине задача проверки, удовлетворяет ли граф с ограниченной книжной толщиной заданной формуле логики первого порядка, является Шаблон:Не переведено 5Шаблон:Sfn.
Приложения
Отказоустойчивые мультипроцессорные вычисления
Одним из основных поводов изучения книжного вложения (согласно Чангу, Ляйтону и РозенбергуШаблон:Sfn) является его использование в разработке СБИС для создания отказоустойчивых многопроцессорных систем. В системе DIOGENES, разработанной этими авторами, процессоры многопроцессорной системы организованы в логическую цепочку, соответствующую корешку книги (хотя они не обязательно должны располагаться по прямой Шаблон:Не переведено 5). Коммуникационные связи этих процессоров группируются в «пучки», которые соответствуют страницам книги и работают подобно стекам — соединение одного из процессоров с началом коммуникационной линии толкает вверх все предыдущие соединения в пучке, а соединение другого процессора с концом коммуникационной линии соединяет его с одним из нижних процессоров в пучке и толкает все оставшиеся вниз. Ввиду такого стекового поведения отдельный пучок может обслуживать набор коммуникационных линий, которые образуют рёбра отдельной страницы книжного вложения. При расположении связей таким образом можно имплементировать широкий набор топологических схем, при которых неважно, какой из процессоров даст сбой, пока достаточно много процессоров остаются в сети. Сетевые топологии, которые можно организовать такой системой — это в точности те, которые имеют книжную толщину, не превосходящую числа пучков, которые следует сделать доступнымиШаблон:Sfn.
Стековая сортировка
Другое приложение, указанное Чангом, Ляйтоном и РозенбергомШаблон:Sfn, касается сортировки перестановок с использованием стеков. Кнут показал, что система, обрабатывающая поток данных путём заталкивания входных элементов в стек, а затем, в нужное время, выталкивающая их в выходной поток, может сортировать данные тогда и только тогда, когда в исходном порядке элементов нет перестановок с Шаблон:Не переведено 5 231.[25]. С тех пор было множество работ по поводу этой и похожих проблем сортировки потока данных более общими системами стеков и очередей. В системе, рассматриваемой Чангом, Ляйтоном и Розенбергом, каждый элемент из входного потока должен быть заслан в один из стеков. После того, как все данные будут засланы в стеки, элементы выталкиваются из этих стеков (в подходящем порядке) в выходной поток. Как заметил Чанг и др., заданная перестановка может быть отсортирована такой системой тогда и только тогда, когда некоторый граф, полученный из перестановки, имеет книжное вложение с фиксированным порядком вершин вдоль корешка и числом страниц, не превосходящим числа стековШаблон:Sfn.
Контроль движения
Как описывает КайненШаблон:Sfn, книжное вложение может быть использовано для описания фаз светофоров на управляемом перекрёстке. На перекрёстке входящие и исходящие ряды движения (включая концы пешеходных переходов и велосипедные линии) можно представить как вершины графа, расположенные на корешке книжного вложения в порядке, соответствующем порядку входов/выходов движения по перекрёстку (по часовой стрелке). Пути через перекрёсток, по которому движется транспорт, и пешеходы от точки входа к точке выхода, можно представить как рёбра ненаправленного графа. Например, этот граф может иметь ребро от входного ряда движения в выходной ряд, принадлежащие одному сегменту дороги, представляя тем самым разворот, если только разворот разрешён на перекрёстке. Заданное подмножество таких рёбер представляет набор путей, по которым может осуществляться движение без пересечений, в том и только в том случае, когда подмножество не содержит пары пересекающихся рёбер, находящихся на одной странице книжного вложения. Таким образом, книжное вложение графа описывает деление путей на подмножества, в которых движение не пересекается, и книжная толщина этого графа (с фиксированным вложением на корешке) даёт минимальное число различных фаз светофора, необходимых для расписания светофора, которые включают все возможные пути через перекрёстокШаблон:Sfn. Однако эта модель неприменима к более сложным системам регулировки движения, которые не имеют фиксированного расписания.
Визуализация графов
Книжное вложение часто применяется также для визуализации сетевого потока данных. Две стандартных схемы визуализации графов, дуговые диаграммыШаблон:Sfn и круговые диаграммыШаблон:Sfn, можно рассматривать как книжные вложения. Книжное вложение можно использовать также для построения кластерных схемШаблон:Sfn, одновременных вложенийШаблон:Sfn и трёхмерных рисунков графовШаблон:Sfn.
Дуговая диаграммаШаблон:Sfn или линейное вложениеШаблон:Sfn располагает вершины графа на прямой, а рёбра графа рисуются как полуокружности над и под этой прямой, иногда позволяя рёбрам быть отрезками прямой. Такой стиль рисования соответствует книжному вложению с одной страницей (если все полуокружности находятся над прямой) или с двумя страницами (если используются обе стороны от прямой) и был первоначально введён как способ изучения числа пересечений графов.[26][27] Планарные графы, не имеющие двухстраничного книжного вложения, могут быть нарисованы подобным образом путём разрешения рёбрам быть представленными двумя полуокружностями сверху и снизу прямой линии. Такие рисунки не являются книжными вложениями с точки зрения обычного определения и называются топологическими книжными вложениями[28]. Для любого планарного графа всегда можно найти такое вложение, которое пересекает корешок максимум один раз.[29].
При другом стиле рисования, круговом расположении, вершины графа располагаются на окружности, а рёбра рисуются внутри или снаружи окружностиШаблон:Sfn. Снова расположение рёбер внутри окружности (например, как отрезки) соответствуют одностраничному книжному рисованию, в то время как расположение рёбер по обе стороны от окружности соответствует двухстраничному книжному рисованию[30].
Для одностраничных рисований любого стиля важно сохранять число пересечений малым, чтобы уменьшить визуальный хаос рисунка. Минимизация числа пересечений является NP-полной задачейШаблон:Sfn, но задача может быть аппроксимирована с отношением O(log2 n), где n является числом вершин[31]. Минимизация одностраничного или двухстраничного числа пересечений является Шаблон:Не переведено 5, когда параметризуется цикломатическим числом заданного графа[32]. Разрабатывались также эвристические методы уменьшения сложности пересечений, основанные, например, на аккуратном порядке вставки вершин и на локальной оптимизацииШаблон:Sfn.
Двухстраничное книжное вложение с фиксированным распределением рёбер по страницам может быть представлено как вид Шаблон:Не переведено 5, в которой заданный граф должен быть нарисован так, что части графа (два подмножества рёбер) располагаются на рисунке так, чтобы отразить их кластеризациюШаблон:Sfn. Двухстраничное книжное вложение используется также для поиска одновременного вложения графов, при котором два графа заданы на одном множестве вершин, и нужно найти расположение вершин, при котором оба графа рисуются планарно с помощью прямых отрезковШаблон:Sfn.
Книжные вложения, имеющие более двух страниц, используются для построения трёхмерных рисунков графов. В частности, Вуд использовал построение книжных вложений, сохраняющих низкую степень каждой вершины внутри каждой страницы, как метод вложения графов в трёхмерную решётку малого объёмаШаблон:Sfn.
Фолдинг РНК
При изучении, каким образом молекулы РНК складываются при образовании структуры РНК, стандартный вид Шаблон:Не переведено 5 можно описать с помощью диаграммы как цепочка оснований (последовательность РНК), нарисованных вдоль прямой вместе с набором дуг сверху линии, которые описывают спаренные основания структуры. То есть, хотя эта структура имеет сложный трёхмерный вид, её связи (если вторичная структура существует) можно описать более абстрактной структурой, одностраничным книжным вложением. Однако не все РНК ведут себя таким простым образом. Хаслингер и Стадлер предложили так называемую «бивторичную структуру» для определённых псевдоузлов РНК, которые принимают вид двухстраничного книжного вложения — последовательность РНК снова рисуется вдоль прямой, но спаренные основания рисуются как дуги сверху и снизу этой линии. Для образования бивторичной структуры граф должен иметь степень, не превосходящую трёх — каждое основание может быть только в одном ребре диаграммы, а также в двух связях с соседними основаниями в последовательности. Преимущество такой формулировки включает факты, что она исключает структуры, которые, фактически, завязаны в узлы в пространстве, и то, что она покрывает большинство известных псевдоузлов РНКШаблон:Sfn.
Поскольку порядок на корешке известен изначально, проверка существования бивторичной структуры для заданных спаренных оснований осуществляется напрямую. Задача распределения рёбер по двум страницам может быть сформулирована как частный случай задачи Шаблон:Не переведено 5 или как задача проверки двудольности кругового графа, вершины которого являются спаренными основаниями, а рёбра описывают скрещивание между спаренными основаниямиШаблон:Sfn. Другим и более эффективным способом, как показали Хаслингер и СтадлерШаблон:Sfn, определения, что бивторичная структура существует, является факт, что это случается в том и только в том случае, когда входной граф (граф, образованный соединением оснований в цикл в порядке их следования и добавления спаренных оснований в качестве рёбер) является планарнымШаблон:Sfn. Этот факт позволяет распознать бивторичную структуру за линейное время как частный случай проверки планарности.
Блин, Фертин, Русу и Синоквет использовали связь между вторичными структурами и книжными вложениями как часть доказательства NP-трудности некоторых задач сравнения вторичных структур РНК[33]. И если структура РНК скорее третичная, чем бивторичная, (то есть, если требуется более двух страниц на её диаграмме), то определение числа страниц снова NP-трудная задача[34].
Теория вычислительной сложности
Паиан, Тевари и Винодсоандран использовали книжное вложение для изучения вычислительной сложности задачи достижимости в ориентированных графах. Как они заметили, задача достижимости для двухстраничных ориентированных графов может быть решена в однозначном логарифмическом пространстве (аналоге детерминированной логарифмической сложности по памяти задач класса Шаблон:Не переведено 5). Однако задача определения достижимости для трёхстраничных ориентированных графов даёт недетерминированную логарифмическую сложность по памяти. Таким образом, книжное вложение, похоже, тесно связано с различиями между этими двумя классами сложности[35].
Существование экспандеров с постоянным числом страниц[20] является ключевым шагом для доказательства, что не существует подквадратичного по времени моделирования двухленточных недетерминированных машин Тьюринга с помощью одноленточных недетерминированных машин[36].
Другие области математики
Макензи и ОвербейШаблон:Sfn изучали приложение книжной толщины в общей алгебре с помощью графов, полученных из делителей нуля конечного локального кольца путём создания вершины для каждого делителя нуля и ребра для каждой пары значений, произведение которых равно нулюШаблон:Sfn.
В последовательности статей Дынников изучал топологические книжные вложения узлов и зацеплений, показывая, что эти вложения могут быть описаны комбинаторной последовательностью символов и что топологическая эквивалентность двух зацеплений может быть показана последовательностью локальных изменений во вложенияхШаблон:SfnШаблон:Sfn.
Примечания
Литература
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- ↑ Шаблон:Книга.
- ↑ 2,0 2,1 Шаблон:Книга.
- ↑ Шаблон:Статья.
- ↑ Шаблон:Книга.
- ↑ Шаблон:Книга.
- ↑ Шаблон:Статья.
- ↑ В оригинале — spine или back
- ↑ Шаблон:Статья.
- ↑ Шаблон:Статья.
- ↑ Шаблон:Статья.
- ↑ Шаблон:Книга.
- ↑ For additional results on the book thickness of Полный двудольный графs, see Шаблон:Статья.
- ↑ Шаблон:Статья Шаблон:Статья См. также Шаблон:Статья.
- ↑ Шаблон:Книга
- ↑ Шаблон:Статья.
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья.
- ↑ Шаблон:Книга. Как цитировано у Нешетри.
- ↑ Шаблон:Статья.
- ↑ 20,0 20,1 Шаблон:Статья, улучшение более раннего результата Шаблон:Статья; Шаблон:Статья. См. также Шаблон:Статья; Шаблон:Статья.
- ↑ Шаблон:Статья.
- ↑ Шаблон:Статья.
- ↑ Шаблон:Статья.
- ↑ Шаблон:Книга.
- ↑ Шаблон:Книга.
- ↑ Шаблон:Статья.
- ↑ Шаблон:Статья.
- ↑ Шаблон:Статья
- ↑ Шаблон:Книга.
- ↑ Шаблон:Книга.
- ↑ Шаблон:Книга.
- ↑ Шаблон:Книга.
- ↑ Шаблон:Книга.
- ↑ Шаблон:Статья.
- ↑ Шаблон:Статья.
- ↑ Шаблон:Статья.
