Скрыть объявление
Гость отличная новость! Мы открыли доступ к ранее скрытому контенту.

Вам доступно более 44 000 видео уроков, книг и программ без VIP статуса. Более подробно ЗДЕСЬ.

книжный шаблон

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




n

/

2



{\displaystyle \lceil n/2\rceil }
. Эта граница близка для полных графов. Однако подразделение каждого ребра может сократить книжную толщину к величине, пропорциональной корню квадратному из n. Графы с книжной толщиной один являются внешнепланарными графами, а графы с книжной толщиной не более двух являются подгамильтоновыми, которые всегда планарны. Любой планарный граф имеет книжную толщину, не превышающую четырёх. Все минорно замкнутые семейства графов, и, в частности, графы с ограниченной древесной шириной или ограниченным родом, также имеют ограниченную книжную толщину. Определение точной книжной толщины заданного графа является NP-трудной задачи, независимо от того, известен или нет порядок вершин на корешке.
Одной из начальных поводов для изучения книжного вложения было применение его в разработке СБИС, где вершины книжного вложения представляют компоненты, а рёбра представляют соединения между компонентами. При визуализации графов два стандартных стиля представления графов, дуговые диаграммы и круговые размещения, можно построить с помощью книжного вложения. Различные начальные и конечные точки движения пешеходов и машин, которые регулируются светофором, могут быть смоделированы математически как вершины графа, а рёбра будут представлять пары начало-конец, книжное же вложение этого графа можно использовать для создания режима работы светофора, чтобы обеспечить регулировку движения с минимальным числом состояний светофора. В задачах биоинформатики, работающих со структурами РНК, одностраничное книжное вложение представляет классическую форму вторичной структуры нуклеиновой кислоты, а двухстраничное вложение представляет псевдоузлы. Книжное вложение используется также в общей алгебре и теории узлов.
Открытыми проблемами, касающимися книжного вложения, являются
Ограничена ли книжная толщина произвольного графа функцией его подразбиений
Достаточно ли знать порядок вершин на корешке, чтобы проверить, что граф имеет трёхстраничное вложение
Существует ли планарный граф, книжная толщина которого равна четырём
Сколько пересечений на корешке необходимо для трёхстраничного топологического вложения (в этом случае рёбра могут переходить со страницы на страницу через корешок) произвольного графа.

↑ 1 2 3
↑ 1 2




↑ 1 2 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..

↑ 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)..


↑ 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)..

↑ Thomas McKenzie, Shannon Overbay Book embeddings and zero divisors // Ars Combinatoria. — 2010. — Т. 95. — С. 55–63..
↑ 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..
↑ 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..





Узнать больше на Wikipedia.org

    Последнее содержимое с меткой книжный шаблон

  1. Train