Книжное вложение (Tun'uky flk'yuny)

Перейти к навигации Перейти к поиску
Вложение в книгу с тремя страницами полного графа K5. Поскольку этот граф не планарен, его невозможно вложить без пересечения в меньшее число страниц, так что книжная толщина графа равна трём.

Книжное вложение в теории графов — обобщение планарного вложения графа до вложения в книгу — набор полуплоскостей, имеющих одну и ту же прямую в качестве границы. Обычно требуется, чтобы вершины графа лежали на этой границе, а рёбра должны находиться внутри одной страницы. Книжная толщина (или число страниц) графа — наименьшее число полуплоскостей для всех книжных вложений графа.[1] Книжное вложение используется для некоторых других инвариантов графа, включая ширину страницы[2] и книжное число скрещиваний[3].

Любой граф с n вершинами имеет книжную толщину максимум . Эта граница близка для полных графов[1]. Однако подразделение каждого ребра может сократить книжную толщину к величине, пропорциональной корню квадратному из n.[4] Графы с книжной толщиной один являются внешнепланарными графами,[1] а графы с книжной толщиной не более двух являются подгамильтоновыми, которые всегда планарны[2]. Любой планарный граф имеет книжную толщину, не превышающую четырёх[5]. Все минорно замкнутые семейства графов, и, в частности, графы с ограниченной древесной шириной или ограниченным родом, также имеют ограниченную книжную толщину[6]. Определение точной книжной толщины заданного графа является NP-трудной задачи, независимо от того, известен или нет порядок вершин на корешке[7][8].

Одной из начальных поводов для изучения книжного вложения было применение его в разработке СБИС, где вершины книжного вложения представляют компоненты, а рёбра представляют соединения между компонентами[7][9]. При визуализации графов два стандартных стиля представления графов, дуговые диаграммы[10] и круговые расположения[11], можно построить с помощью книжного вложения. Различные начальные и конечные точки движения пешеходов и машин, которые регулируются светофором, могут быть смоделированы математически как вершины графа, а рёбра будут представлять пары начало-конец, книжное же вложение этого графа можно использовать для создания режима работы светофора, чтобы обеспечить регулировку движения с минимальным числом состояний светофора[12]. В задачах биоинформатики, работающих со структурами РНК, одностраничное книжное вложение представляет классическую форму вторичной структуры нуклеиновой кислоты[англ.], а двухстраничное вложение представляет псевдоузлы[13]. Книжное вложение используется также в общей алгебре[14] и теории узлов[15][16].

Открытыми проблемами, касающимися книжного вложения, являются

  • Ограничена ли книжная толщина произвольного графа функцией его подразбиений[17]
  • Достаточно ли знать порядок вершин на корешке, чтобы проверить, что граф имеет трёхстраничное вложение[18]
  • Существует ли планарный граф, книжная толщина которого равна четырём[19]
  • Сколько пересечений на корешке необходимо для трёхстраничного топологического вложения (в этом случае рёбра могут переходить со страницы на страницу через корешок) произвольного графа[20].

История

[править | править код]

Название «книга» было введено Персингером и Атнеосеном (C. A. Persinger, Gail Atneosen) в 1960-е годы[21][22][23]. Атнеосен уже использовал вложение графов в книги, но формальная концепция книжного вложения была сформулирована Кайненом и Оллманом (C. Kainen, L. Taylor Ollman) в начале 1970-х и были добавлены некоторые дополнительные ограничения на способ вложения — в их формулировке вершины графа должны лежать на корешке книги, каждое ребро должно лежать на одной странице (не пересекать корешок) и любые два ребра пересекаются только в общих конечных вершинах[24] [25].

Важными вехами в дальнейшем развитии книжного вложения является доказательство Михалисом Яннакакисом в конце 1980-х, что книжная толщина планарных графов не превосходит четырёх[26][5], и открытие в конце 1990-х тесной связи между книжным вложением и биоинформатикой.[13]

Определения

[править | править код]

Книга является частным видом топологического пространства (называемого также веером[англ.] полуплоскостей)[21][27]. Оно состоит из одной прямой ℓ, называемой корешком[28] книги, вместе с набором одной или более полуплоскостей, называемых страницами или листами книги. Каждая полуплоскость должна иметь одну и ту же прямую ℓ в качестве границы. Книги с конечным числом (k) страниц могут быть вложены в трёхмерное пространство, например, посредством выбора в качестве прямой ℓ оси z прямоугольной системы координат, а в качестве i-ой страницы (из k) можно взять множество точек p, таких что кратчайший отрезок, соединяющий p с осью z, имеет угол 2πi/k по отношению к плоскости xz[1].

Визуализация книги конечного графа G в книгу B есть рисунок графа G в B, так что любая вершина графа G рисуется на корешке B, а любое ребро G рисуется в виде кривой, лежащей внутри одной страницы B. k-страничное книжное число пересечений графа G — это минимальное число пересечений в рисунке на k-страничной книге[3].

Книжное вложение графа G в B — это вложение графа G в пространство B. То есть это рисунок графа G в B, при котором рёбра не пересекаются. Любой конечный граф имеет книжное вложение в книгу с достаточно большим числом страниц. Например, всегда есть возможность вложить каждое ребро на свою собственную страницу. Толщина книги, число страниц, или стэковое число графа G — это минимальное число страниц, которое требуется для книжного вложения графа G. Другой параметр, измеряющий качество книжного вложения, кроме числа страниц, — это ширина страницы. Это максимальное число рёбер, которое пересекает луч, перпендикулярный корешку внутри отдельной страницы. Эквивалентно (для книжных вложений, в которых каждое ребро нарисовано как монотонная кривая), это максимальный размер подмножества рёбер, таких что интервалы, определённые на корешке конечными точками рёбер, все пересекаются[2][29][30].

Существенно для этих определений, что рёбра могут лежать только на одной странице. Как заметил уже Амеозен, если рёбра могут переходить со страницы на страницу (через корешок), то любой граф можно вложить в трёхстраничную книгу[22][31][20]. Однако для трёхстраничного топологического книжного вложения, в котором пересечение корешка разрешено, остаётся интересной задача определения наименьшего числа пресечения корешка, позволяющего вложить граф в книгу[20][32].

Конкретные графы

[править | править код]

Как показано на первом рисунке, книжная толщина полного графа равна трём. Поскольку он непланарен, его книжная толщина больше двух, но существует книжное вложение с тремя страницами. Книжная толщина любого полного графа с вершинами равна в точности . Этот результат даёт верхнюю границу[англ.] максимальной книжной толщины любых графов с вершинами[1]. Двухстраничное число пересечений полного графа равно

что соответствует недоказанной гипотезе Энтони Хилла. То есть, если гипотеза Хилла верна, то рисунком этого графа, минимизирующего число пересечений, является двухстраничный рисунок[33].

Толщина книги полного двудольного графа почти равна  — для каждой вершины меньшей доли можно расположить рёбра, инцидентные этим вершинам, на собственной странице. Эта граница не всегда строгая. Например, имеет толщину книги три, а не четыре. Однако, когда две стороны графа сильно разбалансированы, с , толщина книги равна в точности .[1][34] Толщина книг двоичных графов де Брёйна, графов тасованного обмена, и кубических сетей с циклами[англ.] (когда эти графы достаточно велики, чтобы не быть планарными) равна в точности трём.[35]

Свойства

[править | править код]

Поведение при подразбиениях

[править | править код]
Нерешённые проблемы математики: Может ли книжная толщина графа быть ограничена функцией от книжной толщины подразбиений?

Разбиение каждого ребра графа на двухрёберные пути путём добавления новых вершин для каждого ребра может иногда увеличить толщину книги (например, алмаз имеет книжную толщину один, но его подразбиение имеет книжную толщину два). Однако такое подразбиение может также существенно уменьшить книжную толщину графа после разбиения. Например, книжная толщина полного графа Kn is Θ(n) пропорциональна числу его вершин, но разбиение каждого ребра на два даёт подразбиение с много меньшей книжной толщиной, лишь O(√n).[4]. Несмотря на существование примеров, подобных вышеприведённому, Бланкеншип и Опоровски[31] высказали гипотезу, что книжная толщина подразбиений не может быть существенно меньше, чем у исходного графа. В частности, они предположили, что существует некая функция f, что для любого графа G и графа H, полученного заменой каждого ребра G путём из двух рёбер, если книжная толщина графа H равна t, то книжная толщина графа G не превышает f(t).[31] К 2013 гипотеза Бланкеншипа-Опоровски оставалась недоказанной.[17]

Планарность и внешняя планарность

[править | править код]
Граф Голднера–Харари, a планарный граф с книжной толщиной два

Книжная толщина данного графа G не превышает 1 тогда и только тогда, когда G внешнепланарен. Внешнепланарный граф — это граф, имеющий планарное вложение, в котором все вершины принадлежат внешней грани вложения. Для таких графов расположение вершин в том же порядке вдоль корешка, в котором они появляются на внешней грани (при повторном появлении вершины на внешней грани берётся только одна копия вершины) даёт одностраничное вложение графа. И наоборот, одностраничное книжное вложение является автоматически внешенпланарным — если граф вложен в одну страницу, присоединение второй полуплоскости даёт полную плоскость, а внешняя грань будет содержать всю добавленную полуплоскость, при этом все вершины будут лежать на этой внешней грани[1][2].

Любое книжное вложение с двумя страницами является специальным случаем планарного вложения, поскольку объединение двух страниц книги является пространством, топологически эквивалентным плоскости. Таким образом, любой граф с книжной толщиной два автоматически является планарным. Точнее, книжная толщина графа G не больше двух тогда и только тогда, когда G является подграфом планарного графа, который имеет гамильтонов цикл[1]. Если дан граф с книжным вложением в две страницы, граф может быть расширен до планарного гамильтонова графа путём добавления (на любой странице) дополнительных рёбер между любыми двумя последовательными вершинами вдоль корешка, если они ещё не соединены ребром, а также между первой и последней вершиной корешка. Граф Голднера–Харари даёт пример планарного графа, не имеющего книжной толщины два — это максимальный планарный граф[англ.], так что невозможно добавить никакое ребро, сохраняя планарность, и граф не имеет гамильтонова цикла[1]. Ввиду требования наличия гамильтоновых циклов графы, позволяющие двухстраничное вложение, известны как подгамильтоновы графы[2].

Все планарные графы с максимальной степенью, не превышающей четырёх, имеют толщину книжного вложения, не превышающую двух.[36]. Планарные 3-деревья[англ.] имеют максимальную толщину книги, равную трём[37]. Все планарные графы имеют книжную толщину, не превышающую четырёх[26][5]. Как утверждал Михалис Яннакакис в 1986[26], существуют планарные графы с толщиной книжного вложения, в точности равной четырём, однако детальное доказательство этого утверждения, анонсированного в статье[5], так и не было опубликовано. По этой причине Дуймович[19] обозначил задачу определения максимальной толщины книжного вложения планарных графов как нерешённую[19].

Связь с другими инвариантами графов

[править | править код]

Толщина книги связана с толщиной графа, числом планарных графов, которые необходимы для покрытия рёбер заданного графа. Граф G имеет толщину θ, если его можно вложить в плоскость, и при этом рёбра можно раскрасить в θ цветов таким образом, что рёбра одного цвета не пересекаются. Аналогично граф G имеет книжную толщину θ, если его можно нарисовать в полуплоскости с вершинами на границе полуплоскости и раскрасить рёбра в θ цветов без пересечений рёбер одного цвета. При такой формулировке рёбра одного цвета соответствуют страницам книжного вложения. Однако толщина графа и толщина книги могут существенно различаться — существуют подразделения полных графов, имеющие неограниченную книжную толщину[31][20][4], несмотря на то, что толщина графа равна двум[4].

Графы с древесной шириной k имеют книжную толщину, не превосходящую k + 1[19][38] и эта граница достигается для k > 2.[19]. Графы с m рёбрами имеют книжную толщину O(√m)[39], а графы с родом g — книжную толщину O(√g)[40]. Более обще, любое минорно-замкнутое семейство графов[англ.] имеет ограниченную книжную толщину[6][41].

Любой стягивающий минор графа ограниченной книжной толщины является разреженным графом, у которого отношение рёбер к вершинам ограничено константной, которая зависит только от глубины минора и книжной толщины. То есть, в терминологии Нешетрила[6], графы с ограниченной книжной толщиной имеют ограниченный рост[6]. Однако даже графы с ограниченной степенью графа существенно более сильное требование ограничения роста, может иметь неограниченную книжную толщину[42].

Поскольку графы с книжной толщиной два являются планарными графами, они удовлетворяют теореме о планарном разбиении — они имеют сепараторы, подмножества вершин, удаление которых делит граф на части с максимум 2n/3 вершинами в каждой части, только с O(√n) вершинами в сепараторе. Здесь n означает число вершин графа. Однако существуют графы с книжной толщиной три, не имеющие сепараторы сублинейного размера[43].

Рёбра на одной странице книжного вложения ведут себя подобно стеку. Это можно формализовать, если рассмотреть произвольную последовательность операций push и pop (засылка и извлечение) на стеке и сформировать граф, в котором стековые операции соответствуют вершинам графа, расположенным на корешке книжного вложения в порядке выполнения операций. Если теперь нарисовать ребро от каждой операции pop, извлекающей объект x из стека к операции push, заславшей этот элемент в стек, полученный граф будет иметь автоматически одностраничное вложение. По этой причине число страниц графа называют также его стековым числом. По аналогии исследователи определяют очередное вложение графа как рисунок графа в книге, в котором любые два ребра на странице либо пересекаются, либо покрывают непересекающиеся интервалы на корешке. Такие вложения соответствуют некоторым образом очередям и минимальное число страниц, необходимых для очередного вложения графа, называется его числом очередей[6][44][45].

Вычислительная сложность

[править | править код]
Круговой граф, граф пересечений хорд окружности. Для книжного вложения с фиксированным порядком вершин нахождение книжной толщины эквивалентно раскраске соответствующего кругового графа.

Определение толщины книжного вложения является NP-трудной задачей. Это следует из факта, что нахождение гамильтонова цикла в максимальных планарных графах является NP-полной задачей. Толщина книжного вложения максимального планарного графа равна двум тогда и только тогда, когда гамильтонов путь существует. Поэтому определение, что толщина книжного вложения заданного максимального планарного графа равна двум, также является NP-полной задачей.[7]

Если порядок расположения вершин вдоль корешка при книжном вложении предопределён, двухстраничное вложение (если такое существует) может быть найдено за линейное время как вариант проверки планарности для графа, полученного расширением заданного графа путём создания цикла, соединяющего вершины вдоль корешка[13]. Унгер утверждал, что нахождение трёхстраничного вложения с предопределённым порядком вершин может быть осуществлено за полиномиальное время, хотя в его описании этого результата отсутствует ряд существенных деталей[18]. Однако для графов, которые требуют четыре и более страниц, задача нахождения вложения с минимально возможным числом страниц остаётся NP-трудной ввиду эквивалентности NP-трудной задаче раскраски круговых графов, графов пересечений хорд окружности. Если задан граф G с фиксированным порядком вершин на корешке, расположение этих вершин в том же порядке на окружности и представление рёбер графа G в виде отрезков даёт набор хорд, представляющих граф G. Можно теперь образовать круговой граф, имеющий хорды этой диаграммы в качестве вершин, а пересекающиеся пары хорд в качестве рёбер. Раскраска кругового графа даёт разбиение рёбер графа G на подмножества, которые могут быть нарисованы без пересечений на одной странице. Таким образом, оптимальная раскраска эквивалентна оптимальному книжному вложению. Поскольку раскраска кругового графа в четыре и более цветов является NP-трудной задачей, и поскольку любой круговой граф может быть образован таким образом из некоторой задачи нахождения книжного вложения, нахождение оптимального книжного вложения является также NP-трудной задачей[8][46][47]. Для фиксированного порядка вершин на корешке при двухстраничном вложении является NP-трудной задачей минимизация числа пересечений, если это число не равно нулю[46].

Если порядок вершин на корешке неизвестен, но разбиение рёбер по страницам задано, возможно нахождение 2-страничного вложения (если такое существует) за линейное время путём применения алгоритма, основанного на SPQR-деревьях[48][49]. Однако нахождение 2-страничного вложения является NP-полной задачей, если ни порядок вершин на корешке, ни разбиение рёбер по страницам не известно. Нахождение книжного числа пересечений графа является также NP-трудной задачей ввиду NP-полноты задачи проверки, является ли двухстраничное книжное число пересечений нулём.

Задача изоморфизма подграфа[англ.], заключающаяся в определении, находится ли ограниченный в размере граф некоторого вида в качестве подграфа большего графа, может быть решена за линейное время, если больший граф имеет ограниченную толщину книжного вложения. То же самое верно и для определения, является ли граф некоторого вида порождённым подграфом большего графа, или он имеет гомеоморфизм с большим графом[50][51]. По той же причине задача проверки, удовлетворяет ли граф с ограниченной книжной толщиной заданной формуле логики первого порядка, является разрешимой относительно фиксированного параметра[англ.][52].

Приложения

[править | править код]

Отказоустойчивые мультипроцессорные вычисления

[править | править код]

Одним из основных поводов изучения книжного вложения (согласно Чангу, Ляйтону и Розенбергу[7]) является его использование в разработке СБИС для создания отказоустойчивых многопроцессорных систем. В системе DIOGENES, разработанной этими авторами, процессоры многопроцессорной системы организованы в логическую цепочку, соответствующую корешку книги (хотя они не обязательно должны располагаться по прямой физически на схеме[англ.]). Коммуникационные связи этих процессоров группируются в «пучки», которые соответствуют страницам книги и работают подобно стекам — соединение одного из процессоров с началом коммуникационной линии толкает вверх все предыдущие соединения в пучке, а соединение другого процессора с концом коммуникационной линии соединяет его с одним из нижних процессоров в пучке и толкает все оставшиеся вниз. Ввиду такого стекового поведения отдельный пучок может обслуживать набор коммуникационных линий, которые образуют рёбра отдельной страницы книжного вложения. При расположении связей таким образом можно имплементировать широкий набор топологических схем, при которых неважно, какой из процессоров даст сбой, пока достаточно много процессоров остаются в сети. Сетевые топологии, которые можно организовать такой системой — это в точности те, которые имеют книжную толщину, не превосходящую числа пучков, которые следует сделать доступными[7].

Стековая сортировка

[править | править код]

Другое приложение, указанное Чангом, Ляйтоном и Розенбергом[7], касается сортировки перестановок с использованием стеков. Кнут показал, что система, обрабатывающая поток данных путём заталкивания входных элементов в стек, а затем, в нужное время, выталкивающая их в выходной поток, может сортировать данные тогда и только тогда, когда в исходном порядке элементов нет перестановок с шаблоном[англ.] 231.[53]. С тех пор было множество работ по поводу этой и похожих проблем сортировки потока данных более общими системами стеков и очередей. В системе, рассматриваемой Чангом, Ляйтоном и Розенбергом, каждый элемент из входного потока должен быть заслан в один из стеков. После того, как все данные будут засланы в стеки, элементы выталкиваются из этих стеков (в подходящем порядке) в выходной поток. Как заметил Чанг и др., заданная перестановка может быть отсортирована такой системой тогда и только тогда, когда некоторый граф, полученный из перестановки, имеет книжное вложение с фиксированным порядком вершин вдоль корешка и числом страниц, не превосходящим числа стеков[7].

Контроль движения

[править | править код]
Перекрёсток. Четыре входящих и исходящих пар рядов движения, два кармана для поворота и четыре пешеходных перехода можно представить как 14 вершин на корешке книжного вложения, а рёбра задают соединения (направления движения) между этими точками.

Как описывает Кайнен[12], книжное вложение может быть использовано для описания фаз светофоров на управляемом перекрёстке. На перекрёстке входящие и исходящие ряды движения (включая концы пешеходных переходов и велосипедные линии) можно представить как вершины графа, расположенные на корешке книжного вложения в порядке, соответствующем порядку входов/выходов движения по перекрёстку (по часовой стрелке). Пути через перекрёсток, по которому движется транспорт, и пешеходы от точки входа к точке выхода, можно представить как рёбра ненаправленного графа. Например, этот граф может иметь ребро от входного ряда движения в выходной ряд, принадлежащие одному сегменту дороги, представляя тем самым разворот, если только разворот разрешён на перекрёстке. Заданное подмножество таких рёбер представляет набор путей, по которым может осуществляться движение без пересечений, в том и только в том случае, когда подмножество не содержит пары пересекающихся рёбер, находящихся на одной странице книжного вложения. Таким образом, книжное вложение графа описывает деление путей на подмножества, в которых движение не пересекается, и книжная толщина этого графа (с фиксированным вложением на корешке) даёт минимальное число различных фаз светофора, необходимых для расписания светофора, которые включают все возможные пути через перекрёсток[12]. Однако эта модель неприменима к более сложным системам регулировки движения, которые не имеют фиксированного расписания.

Визуализация графов

[править | править код]
Дуговая диаграмма графа Голднера-Харари. Для создания планарной диаграммы два треугольника графа разделены на четыре с помощью пунктирной красной линии, что приводит к тому, что одно из рёбер графа находится как выше, так и ниже этой линии.

Книжное вложение часто применяется также для визуализации сетевого потока данных. Две стандартных схемы визуализации графов, дуговые диаграммы[10] и круговые диаграммы[11], можно рассматривать как книжные вложения. Книжное вложение можно использовать также для построения кластерных схем[48], одновременных вложений[54] и трёхмерных рисунков графов[55].

Дуговая диаграмма[10] или линейное вложение[46] располагает вершины графа на прямой, а рёбра графа рисуются как полуокружности над и под этой прямой, иногда позволяя рёбрам быть отрезками прямой. Такой стиль рисования соответствует книжному вложению с одной страницей (если все полуокружности находятся над прямой) или с двумя страницами (если используются обе стороны от прямой) и был первоначально введён как способ изучения числа пересечений графов.[56][57] Планарные графы, не имеющие двухстраничного книжного вложения, могут быть нарисованы подобным образом путём разрешения рёбрам быть представленными двумя полуокружностями сверху и снизу прямой линии. Такие рисунки не являются книжными вложениями с точки зрения обычного определения и называются топологическими книжными вложениями[58]. Для любого планарного графа всегда можно найти такое вложение, которое пересекает корешок максимум один раз.[59].

Круговая схема графа Хватала

При другом стиле рисования, круговом расположении, вершины графа располагаются на окружности, а рёбра рисуются внутри или снаружи окружности[11]. Снова расположение рёбер внутри окружности (например, как отрезки) соответствуют одностраничному книжному рисованию, в то время как расположение рёбер по обе стороны от окружности соответствует двухстраничному книжному рисованию[60].

Для одностраничных рисований любого стиля важно сохранять число пересечений малым, чтобы уменьшить визуальный хаос рисунка. Минимизация числа пересечений является NP-полной задачей[46], но задача может быть аппроксимирована с отношением O(log2 n), где n является числом вершин[61]. Минимизация одностраничного или двухстраничного числа пересечений является разрешимой относительно фиксированного параметра[англ.], когда параметризуется цикломатическим числом заданного графа[62]. Разрабатывались также эвристические методы уменьшения сложности пересечений, основанные, например, на аккуратном порядке вставки вершин и на локальной оптимизации[11].

Двухстраничное книжное вложение с фиксированным распределением рёбер по страницам может быть представлено как вид кластерной планарности[англ.], в которой заданный граф должен быть нарисован так, что части графа (два подмножества рёбер) располагаются на рисунке так, чтобы отразить их кластеризацию[48]. Двухстраничное книжное вложение используется также для поиска одновременного вложения графов, при котором два графа заданы на одном множестве вершин, и нужно найти расположение вершин, при котором оба графа рисуются планарно с помощью прямых отрезков[54].

Книжные вложения, имеющие более двух страниц, используются для построения трёхмерных рисунков графов. В частности, Вуд использовал построение книжных вложений, сохраняющих низкую степень каждой вершины внутри каждой страницы, как метод вложения графов в трёхмерную решётку малого объёма[55].

Фолдинг РНК

[править | править код]
Фрагмент человеческой теломеразы в виде псевдоузла. Если фрагмент растянуть вдоль корешка книжного вложения, голубые связи могут быть нарисованы в виде двух непересекающихся подмножеств сверху и снизу корешка, что показывает, что этот псевдоузел образует би-вторичную структуру.

При изучении, каким образом молекулы РНК складываются при образовании структуры РНК, стандартный вид вторичной структуры нуклеиновой кислоты[англ.] можно описать с помощью диаграммы как цепочка оснований (последовательность РНК), нарисованных вдоль прямой вместе с набором дуг сверху линии, которые описывают спаренные основания структуры. То есть, хотя эта структура имеет сложный трёхмерный вид, её связи (если вторичная структура существует) можно описать более абстрактной структурой, одностраничным книжным вложением. Однако не все РНК ведут себя таким простым образом. Хаслингер и Стадлер предложили так называемую «бивторичную структуру» для определённых псевдоузлов РНК, которые принимают вид двухстраничного книжного вложения — последовательность РНК снова рисуется вдоль прямой, но спаренные основания рисуются как дуги сверху и снизу этой линии. Для образования бивторичной структуры граф должен иметь степень, не превосходящую трёх — каждое основание может быть только в одном ребре диаграммы, а также в двух связях с соседними основаниями в последовательности. Преимущество такой формулировки включает факты, что она исключает структуры, которые, фактически, завязаны в узлы в пространстве, и то, что она покрывает большинство известных псевдоузлов РНК[13].

Поскольку порядок на корешке известен изначально, проверка существования бивторичной структуры для заданных спаренных оснований осуществляется напрямую. Задача распределения рёбер по двум страницам может быть сформулирована как частный случай задачи выполнимости булевых формул в 2-конъютктивной нормальной форме[англ.] или как задача проверки двудольности кругового графа, вершины которого являются спаренными основаниями, а рёбра описывают скрещивание между спаренными основаниями[13]. Другим и более эффективным способом, как показали Хаслингер и Стадлер[13], определения, что бивторичная структура существует, является факт, что это случается в том и только в том случае, когда входной граф (граф, образованный соединением оснований в цикл в порядке их следования и добавления спаренных оснований в качестве рёбер) является планарным[13]. Этот факт позволяет распознать бивторичную структуру за линейное время как частный случай проверки планарности.

Блин, Фертин, Русу и Синоквет использовали связь между вторичными структурами и книжными вложениями как часть доказательства NP-трудности некоторых задач сравнения вторичных структур РНК[63]. И если структура РНК скорее третичная, чем бивторичная, (то есть, если требуется более двух страниц на её диаграмме), то определение числа страниц снова NP-трудная задача[64].

Теория вычислительной сложности

[править | править код]

Паиан, Тевари и Винодсоандран использовали книжное вложение для изучения вычислительной сложности задачи достижимости в ориентированных графах. Как они заметили, задача достижимости для двухстраничных ориентированных графов может быть решена в однозначном логарифмическом пространстве (аналоге детерминированной логарифмической сложности по памяти задач класса UP[англ.]). Однако задача определения достижимости для трёхстраничных ориентированных графов даёт недетерминированную логарифмическую сложность по памяти. Таким образом, книжное вложение, похоже, тесно связано с различиями между этими двумя классами сложности[65].

Существование экспандеров с постоянным числом страниц[43] является ключевым шагом для доказательства, что не существует подквадратичного по времени моделирования двухленточных недетерминированных машин Тьюринга с помощью одноленточных недетерминированных машин[66].

Другие области математики

[править | править код]

Макензи и Овербей[14] изучали приложение книжной толщины в общей алгебре с помощью графов, полученных из делителей нуля конечного локального кольца путём создания вершины для каждого делителя нуля и ребра для каждой пары значений, произведение которых равно нулю[14].

В последовательности статей Дынников изучал топологические книжные вложения узлов и зацеплений, показывая, что эти вложения могут быть описаны комбинаторной последовательностью символов и что топологическая эквивалентность двух зацеплений может быть показана последовательностью локальных изменений во вложениях[15][16].

Примечания

[править | править код]
  1. ↑ 1 2 3 4 5 6 7 8 9 Bernhart, Kainen, 1979, pp. 320–331.
  2. ↑ 1 2 3 4 5 Heath, 1987, pp. 198–218.
  3. ↑ 1 2 Shahrokhi et al, 1996, pp. 413–424.
  4. ↑ 1 2 3 4 Eppstein, 2001.
  5. ↑ 1 2 3 4 Yannakakis, 1989, pp. 36–67.
  6. ↑ 1 2 3 4 5 Nešetřil, Ossona de Mendez, 2012, pp. 321–328.
  7. ↑ 1 2 3 4 5 6 7 Chung et al, 1987, pp. 33–58.
  8. ↑ 1 2 Unger, 1988, pp. 61–72.
  9. ↑ Arnold L. Rosenberg. Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986). — 1986. — Т. 54. — С. 217–224. — (Congressus Numerantium)..
  10. ↑ 1 2 3 Wattenberg, 2002, pp. 111–116.
  11. ↑ 1 2 3 4 Baur, Brandes, 2005, pp. 332–343.
  12. ↑ 1 2 3 Kainen, 1990, pp. 127–132.
  13. ↑ 1 2 3 4 5 6 7 Haslinger et al, 1999, pp. 437–467.
  14. ↑ 1 2 3 McKenzie, Overbay, 2010, pp. 55–63.
  15. ↑ 1 2 Dynnikov, 1999, pp. 25–37, 96.
  16. ↑ 1 2 Dynnikov, 2001, pp. 243–283.
  17. ↑ 1 2 Blankenship, Oporowski, 2009.
  18. ↑ 1 2 Walter Unger. STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13–15, 1992, Proceedings. — Berlin: Springer, 1992. — Т. 577. — С. 389–400. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-55210-3_199..
  19. ↑ 1 2 3 4 5 Dujmović, Wood, 2007, pp. 641–670.
  20. ↑ 1 2 3 4 Enomoto, Miyauchi, 1999, pp. 337–341.
  21. ↑ 1 2 Persinger, 1966, pp. 169–173.
  22. ↑ 1 2 Atneosen, 1968, p. 79.
  23. ↑ Gail H. Atneosen. One-dimensional n-leaved continua // Fundamenta Mathematicae. — 1972. — Т. 74, вып. 1. — С. 43–45..
  24. ↑ Paul C. Kainen. Graphs and Combinatorics (Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University June 18–22, 1973) / Ruth A. Bari, Frank Harary. — 1974. — Т. 406. — С. 76–108. — (Lecture Notes in Mathematics)..
  25. ↑ L. Taylor Ollmann. Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing / Frederick Hoffman, Roy B. Levow, Robert S. D. Thomas. — 1973. — Т. VIII. — С. 459. — (Congressus Numerantium)..
  26. ↑ 1 2 3 Yannakakis, 1986, pp. 104–108.
  27. ↑ T. C. Hales. Sphere packings. II // Discrete & Computational Geometry. — 1997. — Т. 18, вып. 2. — С. 135–149. — doi:10.1007/PL00009312..
  28. ↑ В оригинале — spine или back
  29. ↑ Elena Stöhr. A trade-off between page number and page width of book embeddings of graphs // Information and Computation. — 1988. — Т. 79, вып. 2. — С. 155–162. — doi:10.1016/0890-5401(88)90036-3..
  30. ↑ Elena Stöhr. The pagewidth of trivalent planar graphs // Discrete Mathematics. — 1991. — Т. 89, вып. 1. — С. 43–49. — doi:10.1016/0012-365X(91)90398-L..
  31. ↑ 1 2 3 4 Blankenship, Oporowski, 1999.
  32. ↑ Hikoe Enomoto, Miki Shimabara Miyauchi, Katsuhiro Ota. Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph // Discrete Applied Mathematics. — 1999. — Т. 92, вып. 2—3. — С. 149–155. — doi:10.1016/S0166-218X(99)00044-X..
  33. ↑ Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Pedro Ramos, Gelasio Salazar. Proceedings of the 28th Annual Symposium on Computational Geometry (SCG'12). — ACM, New York, 2012. — С. 397–403. — doi:10.1145/2261250.2261310..
  34. ↑ For additional results on the book thickness of Полный двудольный графs, see Etienne de Klerk, Dmitrii V. Pasechnik, Gelasio Salazar. Book drawings of complete bipartite graphs // Discrete Applied Mathematics. — 2014. — Т. 167. — С. 80–93. — doi:10.1016/j.dam.2013.11.001..
  35. ↑ Toru Hasunuma, Yukio Shibata. Embedding de Bruijn, Kautz and shuffle-exchange networks in books // Discrete Applied Mathematics. — 1997. — Т. 78, вып. 1—3. — С. 103–116. — doi:10.1016/S0166-218X(97)00009-7. Yuuki Tanaka, Yukio Shibata. On the pagenumber of the cube-connected cycles // Mathematics in Computer Science. — 2010. — Т. 3, вып. 1. — С. 109–117. — doi:10.1007/s11786-009-0012-y. См. также Bojana Obrenić. Embedding de Bruijn and shuffle-exchange graphs in five pages // SIAM Journal on Discrete Mathematics. — 1993. — Т. 6, вып. 4. — С. 642–654. — doi:10.1137/0406049..
  36. ↑ Bekos et al, 2014, pp. 137–148.
  37. ↑ Lenny Heath. Proceedings of the 25th Annual Symposium on Foundations of Computer Science. — 1984. — С. 74–83. — doi:10.1109/SFCS.1984.715903.
  38. ↑ Joseph L. Ganley, Lenwood S. Heath. The pagenumber of k-trees is O(k) // Discrete Applied Mathematics. — 2001. — Т. 109, вып. 3. — С. 215–221. — doi:10.1016/S0166-218X(00)00178-5..
  39. ↑ Seth M. Malitz. Graphs with E edges have pagenumber O(√E) // Journal of Algorithms : журнал. — 1994. — Июль (т. 17, вып. 1). — С. 71–84. — doi:10.1006/jagm.1994.1027.
  40. ↑ Seth M. Malitz. Genus g graphs have pagenumber O(√g) // Journal of Algorithms. — 1994. — Т. 17, вып. 1. — С. 85–109. — doi:10.1006/jagm.1994.1028..
  41. ↑ R. Blankenship. Book Embeddings of Graphs. — Department of Mathematics, Louisiana State University, 2003.. Как цитировано у Нешетри.
  42. ↑ János Barát, Jiří Matoušek, David R. Wood. Bounded-degree graphs have arbitrarily large geometric thickness // Electronic Journal of Combinatorics. — 2006. — Т. 13, вып. 1. — С. R3..
  43. ↑ 1 2 Vida Dujmović, Anastasios Sidiropoulos, David R. Wood. 3-Monotone Expanders. — arXiv:1501.05020., улучшение более раннего результата Jean Bourgain. Expanders and dimensional expansion // Comptes Rendus Mathématique. — 2009. — Т. 347, вып. 7—8. — С. 357–362. — doi:10.1016/j.crma.2009.02.009.; Jean Bourgain, Amir Yehudayoff. Expansion in and monotone expanders // Geometric and Functional Analysis. — 2013. — Т. 23, вып. 1. — С. 1–41. — doi:10.1007/s00039-012-0200-9.. См. также Zvi Gali, Ravi Kannan, Endre Szemerédi. On 3-pushdown graphs with large separators // Combinatorica. — 1989. — Т. 9, вып. 1. — С. 9–19. — doi:10.1007/BF02122679.; Zeev Dvir, Avi Wigderson. Monotone expanders: constructions and applications // Theory of Computing. — 2010. — Т. 6. — С. 291–308. — doi:10.4086/toc.2010.v006a012..
  44. ↑ Lenwood S. Heath, Arnold L. Rosenberg. Laying out graphs using queues // SIAM Journal on Computing. — 1992. — Т. 21, вып. 5. — С. 927–958. — doi:10.1137/0221055..
  45. ↑ Vida Dujmović, David R. Wood. On linear layouts of graphs // Discrete Mathematics & Theoretical Computer Science. — 2004. — Т. 6, вып. 2. — С. 339–357..
  46. ↑ 1 2 3 4 Masuda et al, 1990, pp. 124–127.
  47. ↑ M. R. Garey, D. S. Johnson, G. L. Miller, C. H. Papadimitriou. The complexity of coloring circular arcs and chords // SIAM Journal on Algebraic and Discrete Methods. — 1980. — Т. 1, вып. 2. — С. 216–227. — doi:10.1137/0601025..
  48. ↑ 1 2 3 Hong, Nagamochi, 2009.
  49. ↑ Patrizio Angelini, Marco Di Bartolomeo, Giuseppe Di Battista. Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19–21, 2012, Revised Selected Papers. — Springer, 2013. — Т. 7704. — С. 79–89. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-36763-2_8..
  50. ↑ Nešetřil, Ossona de Mendez, 2008, pp. 777–791.
  51. ↑ Nešetřil, Ossona de Mendez, 2012, Corollary 18.1, p. 401.
  52. ↑ Nešetřil, Ossona de Mendez, 2012, Theorem 18.7, p. 405.
  53. ↑ Donald E. Knuth. The Art Of Computer Programming Vol. 1. — Boston: Addison-Wesley, 1968. — ISBN 0-201-89683-4..
  54. ↑ 1 2 Angelini et al, 2012, pp. 150–172.
  55. ↑ 1 2 Wood, 2002, pp. 312–327.
  56. ↑ Thomas L. Saaty. The minimum number of intersections in complete graphs // Proceedings of the National Academy of Sciences of the United States of America. — 1964. — Т. 52. — С. 688–690. — doi:10.1073/pnas.52.3.688..
  57. ↑ T. A. J. Nicholson. Permutation procedure for minimising the number of crossings in a network // Proceedings of the Institution of Electrical Engineers. — 1968. — Т. 115. — С. 21–26. — doi:10.1049/piee.1968.0004..
  58. ↑ Miki Miyauchi. Topological book embedding of bipartite graphs (англ.) // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. — 2006. — Vol. E89-A, iss. 5. — P. 1223–1226. — doi:10.1093/ietfec/e89-a.5.1223.
  59. ↑ Francesco Giordano, Giuseppe Liotta, Tamara Mchedlidze, Antonios Symvonis. Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17–19, 2007, Proceedings. — Springer, 2007. — Т. 4835. — С. 172–183. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-77120-3_17..
  60. ↑ Hongmei He, Ondrej Sykora. Proceedings of the Workshop on Information Technologies – Applications and Theory (ITAT), Slovakia, September 15–19, 2004. — 2004..
  61. ↑ Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrt'o. Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Germany, June 16–18, 1994, Proceedings. — Springer, 1995. — Т. 903. — С. 256–268. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-59071-4_53..
  62. ↑ Michael J. Bannister, David Eppstein, Joseph A. Simons. Graph Drawing: 21st International Symposium, GD 2013, Bordeaux, France, September 23–25, 2013, Revised Selected Papers. — 2013. — Т. 8242. — С. 340–351. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-319-03841-4_30..
  63. ↑ Guillaume Blin, Guillaume Fertin, Irena Rusu, Christine Sinoquet. Combinatorics, Algorithms, Probabilistic and Experimental Methodologies: First International Symposium, ESCAPE 2007, Hangzhou, China, April 7-9, 2007, Revised Selected Papers. — 2007. — Т. 4614. — С. 140–151. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-74450-4_13..
  64. ↑ Peter Clote, Stefan Dobrev, Ivan Dotu, Evangelos Kranakis, Danny Krizanc, Jorge Urrutia. On the page number of RNA secondary structures with pseudoknots // Journal of Mathematical Biology. — 2012. — Т. 65, вып. 6–7. — С. 1337–1357. — doi:10.1007/s00285-011-0493-6..
  65. ↑ A. Pavan, Raghunath Tewari, N. V. Vinodchandran. On the power of unambiguity in log-space // Computational Complexity. — 2012. — Т. 21, вып. 4. — С. 643–670. — doi:10.1007/s00037-012-0047-3..
  66. ↑ Zvi Galil, Ravi Kannan, Endre Szemerédi. On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines // Journal of Computer and System Sciences. — 1989. — Т. 38, вып. 1. — С. 134–149. — doi:10.1016/0022-0000(89)90036-6..

Литература

[править | править код]
  • C. A. Persinger. Subsets of n-books in E3 // Pacific Journal of Mathematics. — 1966. — Т. 18. — С. 169–173. — doi:10.2140/pjm.1966.18.169.
  • Gail Adele Atneosen. On the embeddability of compacta in n-books: intrinsic and extrinsic properties. — Michigan State University, 1968. — С. 79. — (Ph.D. thesis).
  • Frank R. Bernhart, Paul C. Kainen. The book thickness of a graph // Journal of Combinatorial Theory. — 1979. — Т. 27, вып. 3. — С. 320–331. — doi:10.1016/0095-8956(79)90021-2.
  • Mihalis Yannakakis. Proceedings of the 18th ACM Symposium on Theory of Computing (STOC '86). — 1986. — С. 104–108. — ISBN 0-89791-193-8. — doi:10.1145/12130.12141.
  • Lenwood S. Heath. Embedding outerplanar graphs in small books // SIAM Journal on Algebraic and Discrete Methods. — 1987. — Т. 8, вып. 2. — С. 198–218. — doi:10.1137/0608018.
  • Fan R. K. Chung, Frank Thompson Leighton, Arnold L. Rosenberg. Embedding graphs in books: A layout problem with applications to VLSI design // SIAM Journal on Algebraic and Discrete Methods. — 1987. — Т. 8, вып. 1. — С. 33–58. — doi:10.1137/0608002.
  • Walter Unger. Proceedings of the 5th Symposium on Theoretical Aspects of Computer Science (STACS '88). — Springer-Verlag, 1988. — Т. 294. — С. 61–72. — (Lecture Notes in Computer Science). — doi:10.1007/BFb0035832.
  • Mihalis Yannakakis. Embedding planar graphs in four pages // Journal of Computer and System Sciences. — 1989. — Т. 38. — С. 36–67. — doi:10.1016/0022-0000(89)90032-9.
  • Paul C. Kainen. Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989). — 1990. — Т. 71. — С. 127–132. — (Congressus Numerantium).
  • Sumio Masuda, Kazuo Nakajima, Toshinobu Kashiwabara, Toshio Fujisawa. Crossing minimization in linear embeddings of graphs // IEEE Transactions on Computers. — 1990. — Т. 39, вып. 1. — С. 124–127. — doi:10.1109/12.46286.
  • Farhad Shahrokhi, László A. Székely, Ondrej Sýkora, Imrich Vrťo. The book crossing number of a graph // Journal of Graph Theory. — 1996. — Т. 21, вып. 4. — С. 413–424. — doi:10.1002/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.3.CO;2-5.
  • Hikoe Enomoto, Miki Shimabara Miyauchi. Embedding graphs into a three page book with O(M log N) crossings of edges over the spine // SIAM Journal on Discrete Mathematics. — 1999. — Т. 12, вып. 3. — С. 337–341. — doi:10.1137/S0895480195280319.
  • Christian Haslinger, Peter F. Stadler. RNA structures with pseudo-knots: Graph-theoretical, combinatorial, and statistical properties // Bulletin of Mathematical Biology. — 1999. — Т. 61, вып. 3. — С. 437–467. — doi:10.1006/bulm.1998.0085.
  • I. A. Dynnikov. Three-page approach to knot theory. Coding and local motions // Rossiĭskaya Akademiya Nauk. — 1999. — Т. 33, вып. 4. — С. 25–37, 96. — doi:10.1007/BF02467109.
  • Robin Blankenship, Bogdan Oporowski. Drawing Subdivisions Of Complete And Complete Bipartite Graphs On Books. — Department of Mathematics, Louisiana State University, 1999. — (Technical Report 1999-4).
  • David Eppstein. Separating geometric thickness from book thickness (англ.). — 2001. — P. 20. — arXiv:math.CO/0109195.
  • I. A. Dynnikov. A new way to represent links, one-dimensional formalism and untangling technology // Acta Applicandae Mathematicae. — 2001. — Т. 69, вып. 3. — С. 243–283. — doi:10.1023/A:1014299416618.
  • Martin M. Wattenberg. Proceedings of IEEE Symposium on Information Visualization (INFOVIS 2002). — 2002. — С. 110–116. — doi:10.1109/INFVIS.2002.1173155.
  • David R. Wood. Graph Drawing: 9th International Symposium, GD 2001, Vienna, Austria, September 23–26, 2001, Revised Papers. — Berlin: Springer, 2002. — Т. 2265. — С. 312–327. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-45848-4_25.
  • Michael Baur, Ulrik Brandes. Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers / van Leeuwen. — Springer, 2005. — Т. 3353. — С. 332–343. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-30559-0_28.
  • Vida Dujmović, David R. Wood. Graph treewidth and geometric thickness parameters // Discrete and Computational Geometry. — 2007. — Т. 37, вып. 4. — С. 641–670. — doi:10.1007/s00454-007-1318-7.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Grad and classes with bounded expansion. II. Algorithmic aspects // European Journal of Combinatorics. — 2008. — Т. 29, вып. 3. — С. 777–791. — doi:10.1016/j.ejc.2006.07.014.
  • Robin Blankenship, Bogdan Oporowski. Book Thickness of Subdivisions (англ.) // Open Problem Garden : сайт / David Wood. — 2009. — 19 January.
  • Seok-Hee Hong, Hiroshi Nagamochi. Two-page book embedding and clustered graph planarity. — Technical report 2009-004. — Dept. of Applied Mathematics and Physics, University of Kyoto, Japan, 2009. — (Technical report).
  • Thomas McKenzie, Shannon Overbay. Book embeddings and zero divisors // Ars Combinatoria. — 2010. — Т. 95. — С. 55–63.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — С. 321–328. — (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4.
  • Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter. Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph // Journal of Discrete Algorithms. — 2012. — Т. 14. — С. 150–172. — doi:10.1016/j.jda.2011.12.015.
  • Michael A. Bekos, Martin Gronemann, Chrysanthi N. Raftopoulou. Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science. — 2014. — С. 137–148. — doi:10.4230/LIPIcs.STACS.2014.137.
Источник — https://ru.wikipedia.org/w/index.php?title=Книжное_вложение&oldid=117124984